The Knapsack Problem A hiker has a knapsack which will hold

The Knapsack Problem: A hiker has a knapsack which will hold a total of N pounds. The hiker has a number of objects weighing w1 pounds, w2 pounds, . . ., wr pounds which he wishes to take with him. He wants to fill the knapsack as full as possible, that is, to pack it with objects having the maximum total weight. You will implement a program to help him figure this out. To make this problem simpler, we fix the number of objects to be 4.

Follow the steps below in your program flow. It is required that you use the for loop for this exercise.

1. Prompt the user and input the maximum number of pounds that the hiker can carry.

2. Prompt the user and input the weights of the 4 objects that the hiker can choose from to take with him.

3. Find the best solution, and print which objects should be taken by the hiker. (Hint: you will need to use a series of nested loops). The best solution is the combination with the highest total that does not exceed the maximum that the hiker can carry.

The name of your class should be KnapsackProblem.

To help you test your code, here are some test cases:

Max Weight 24: 5, 7, 13, 17        Best Combo: 7, 17

Max Weight 25: 5, 10, 13, 9        Best Combo: 5, 10, 9

Max Weight 18: 4, 7, 9, 13           Best Combo: 4, 13

The solution to this problem will require 4 nested for loops. HINT: consider the output of the following code. what does the value of i and j signify? Think about how this could be extended to four numbers? Try to extend this to 4 nested loops, with the indices going only up to 2. What is the significance of the 0 in the print out?

int a = 3;

int b = 5;

for(int i = 0; i <2; i++){

for(int j = 0; j < 2; j++){

System.out.println((i*a) + \" \" +(j*b));

}

}

The specifications for this program deal with the display of the results.

1. You MUST use 4 nested for loops.

2. Only the weights to be included in the knapsack should be shown.

3. Show the total weight carried.

4. The lbs. unit indicator should be added to each weight when displayed.

5. The display should be as shown below, for the input of maximum weight of 50 lbs., and individual weights of 10, 13, 17, 25 pounds.

Solution

#include <iostream>
using namespace std;

int main()
{
   int n;
   int w[4];
   cout<<\"Enter the maximum weight the hiker can carry:\";
   cin>>n;
   cout<<\"Enter the weights of four objects separated by spaces:\";
   for(int i=0;i<4;i++)
   {
       cin>>w[i];
   }
   int max=0,temp;
   int ans[] = {0,0,0,0};
   for(int p=0;p<2;p++)
   {
       for(int q=0;q<2;q++)
       {
           for(int r=0;r<2;r++)
           {
               for(int s=0;s<2;s++)
               {
                   temp = p*w[0]+q*w[1]+r*w[2]+s*w[3];
                   if(temp>max && temp<=n)
                   {
                       max = temp;
                       ans[0]=p;
                       ans[1]=q;
                       ans[2]=r;
                       ans[3]=s;
                   }  
               }
           }
       }
   }
   cout<<\"For a maximum weight of \"<<n<<\" pounds\ \";
   cout<<\"For the objects of following weights:\ \";
   for(int i=0;i<4;i++)
   {
       cout<<w[i]<<\" lbs\";
       if(i<3)
       {
           cout<<\", \";
       }
       if(i==2)
       {
           cout<<\"and \";
       }
   }
   cout<<endl;
   cout<<\"The hiker can carry the following weights:\ \";
   int hat=0,total=0;
   for(int i=0;i<4;i++)
   {
       if(ans[i]==1)
       {
           if(hat==1)
           {
               cout<<\", \";
           }
           cout<<w[i]<<\" lbs\";
           total = total+w[i];
           hat=1;
       }  
   }
   cout<<\" for a total of \"<<total<<\" lbs.\ \";
   return 0;
}