Using bestTwo() as reference, write the code for bestThree() to select 3 items.

Question

Using bestTwo() as reference, write the code for bestThree() to select 3 items.

I have bolded the refrence

#include <iostream>
#include <fstream>

using namespace std;

int factorial(int n) {
    if (n>1)
        return n * factorial(n-1);
    else
        return 1;
}

int factNonRec(int n) {
    int result = 1;
    for(int i=1; i<=n ; i++)
        result *= i;
    return result;
}

int fib(int n) {
    if (n>1)
        return fib(n-1) + fib(n-2);
    else
        return 1;
}

int fibNonRec(int n) {
    int *temp = new int [n+1];

    temp[0] = temp[1] = 1;

    for (int i=2 ; i<=n ; i++)
        temp[i] = temp[i-1] + temp[i-2];

    return temp[n];
}

const int MAX = 10;
int weights[MAX] = {19, 23, 7, 56, 32, 89, 13, 94, 11, 41};
//Extreme subsets: {}, {everything}.
int goal;
int maxSoFar = 0;
void knapsack(int index, int totalSoFar) {
    //current configuration/subset invalid?
    if (totalSoFar > goal)
        return;
    //current subset better than what we have?
    if (totalSoFar > maxSoFar) {
        maxSoFar = totalSoFar;
    }
    //did we reach the end of array?
    if (index == MAX)
        return;
    //we need to consider weights[index]
    //include case
    knapsack(index+1, totalSoFar + weights[index]);
    //exclude case
    knapsack(index+1, totalSoFar);
}

//can we find a subset of items with max total weight, but below or equal to target
int bestSubset(int target) {
    goal = target;
    maxSoFar = 0;
    knapsack(0, 0);
    return maxSoFar;
}

//find one item with max weight, but below or equal to target
int bestOne(int target) {
    int maxSoFar = 0;
    for(int i=0 ; i<MAX ; i++)
        //    is weights[i] higher?     is weights[i] valid?
        if ((maxSoFar < weights[i]) && (weights[i] <= target))
            maxSoFar = weights[i];

    return maxSoFar;
}

//find exactly 2 items with max total weight, but below or equal to target
int bestTwo(int target) {
    int maxSoFar = 0;
    for(int i=0 ; i<MAX ; i++)
        for(int j=i+1 ; j<MAX ; j++) {
            int total = weights[i] + weights[j];
            if ((maxSoFar < total) && (total <= target))
                maxSoFar = total;
        }

    return maxSoFar;
}





main() {
    for(int i=1; i<=100; i++)
        cout << i << ": " << bestOne(i) << " " << bestTwo(i)
             << " " << bestSubset(i) << endl;
}

Explanation / Answer

int bestTwo(int target) {
int maxSoFar = 0;
for(int i=0 ; i<MAX ; i++)
for(int j=i+1 ; j<MAX ; j++)

for(int k=j+1; k<MAX ;k++)

{
int total = weights[i] + weights[j]+weights[k];
if ((maxSoFar < total) && (total <= target))
maxSoFar = total;
}

return maxSoFar;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.