logo CodeStepByStep logo

knapsack01

Language/Type: C++ dynamic programming

Write a function named knapsack01 that solves the classic "0-1 knapsack problem" using dynamic programming. The idea is that given a collection of items of given weights and values, and a knapsack of a given capacity, you must find the optimal way to place items into the knapsack without exceeding its weight capacity that produces the maximal total value. Your function accepts three parameters: a reference to a Vector of integers representing the items' weights, a reference to a Vector of integers representing the items' values, and an integer value W representing the total weight that can fit in the knapsack. Your function should return the largest value we can make using elements in the vector without exceeding the total weight of W. For example, if the vector contains weights of {10, 20, 30, 40} and values of {60, 100, 120, 150}, and the knapsack's max weight W is 50, the optimal subset is {20, 30} having a total value of 100 + 120 = 220, so your function should return 220. You may assume that no item in the vector has a negative weight or value.

You must solve this problem using a bottom-up dynamic programming approach. Do not use recursion. You are allowed to construct any data structures (array, vector, set, map, etc.) necessary to store the data for your dynamic programming algorithm.

Type your C++ solution code here:


This is a function exercise. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

Need help?

If you do not understand how to solve an exercise or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect tests, etc.), please

Is there a problem? Contact a site administrator.

©, all rights reserved.