Reference no: EM132494204

Question 1 You are carrying a backpack that can only hold a limited amount of weight. Journeying through a cave you discover a pile of hidden treasure. Unfortunately, you can't carry it all with you. Select the items that have the greatest value such that the items you choose don't exceed a specified weight limit.

(a) You might consider a solution to the problem based on dynamic programming. An example of what your driver code *might* look like in your main function follows. You may choose how to format your output.

//Main program C++
int main()
{
//How many rupees is each treasure worth
int value [] = {210,220,180,120,160,170,90,40,60,10};

//How heavy is each piece of treasure
int weight [] = {15,12,10,9,8,7,5,4,3,1};

//How strong are you
// i . e. how much weight can you carry?
int W =26;
int n =10;

//Output the value in rupees of what you're able to carry
//Your output for this example should be 520
std :: cout << knapsack (weight, value, n, W) << std::endl;
return 0;
}