Question

Consider the following variant of the knapsack problem. Given are n items with costs ci and volumes vi, and a lower bound on the volume V . Find a minimum cost set of items, such that the total volume is at least V. you should solve it it's the normal knapsack problem, but with an additional lowerbound that the knapsack should be filled AT LEAST

here are some test cases that you can use:

Example: In normal Knapsack, the solution would be Item A, because of the 100 profit.

* However, because of the lowerbound of 85, Item A cannot be chosen.

* The solution here is therefore Item B + Item C */

where item A = (cost: 100, volume:80)

item B = (cost: 40, volume:45)

item C = (cost: 40, volume:45)

Answer 1

Like normal knapsack, this too is a dynamic programming problem. The code above solves it in top down manner with memoization. To accommodate for the lowerbound, we need to change the base case a little and add an extra condition to invalidate some paths.

C++ Code With Comments:

#include <bits/stdc++.h>
using namespace std;

int n, lowerbound, cost[100], weight[100], dp[100][100];

int solve(int index, int filled) // recursive fn to calculate minimum cost
{
if(index == n && filled >= lowerbound) return 0; // base case
if(index == n) return 100000; // return high value because invalid path

if(dp[index][filled] != -1) return dp[index][filled]; // if this path is already calculated
// before no need to calculate it again

return dp[index][filled] =
min(cost[index] + solve(index + 1, filled + weight[index]), solve(index + 1, filled));
// two choices, whether to take the object at current index or not
// recursively trying all paths and storing in dp table to avoid repeated calculations
}

int main()
{
memset(dp, -1, sizeof dp); // setting dp table to one
cin >> n; // number of objects
for(int i = 0 ; i < n ; i++){
cin >> cost[i] >> weight[i]; // cost of item i and value of item i
}
cin >> lowerbound; // lowerbound weight
cout << solve(0, 0); // call function and output
}