How would you go about solving this variation of Knapsack?
You have n objects (x1,...xn), each with cost ci and value vi (1<=i<=n) and an additional constraint X, which is a lower bound on the value of the items selected.
Find a subset of x1,...,xn that minimizes the cost of the items with a value of at least X.
I am trying to solve this through Dynamic Programming, and what I thought of was to modify the usual table used into K[n,c,X] where X would be the minimum value I need to reach, but that seems to bring me nowhere. Any good ideas?
This can be done similarly like we do the knapsack problem, at each index we try to either put in a value inside the knapsack or not, and here the knapsack has no bound on the size hence we can put any no of elements inside the knapsack.
Then we just need to consider only those solutions that satisfy the condition that the size of the knapsack >= X.
The state of the knapsack is DP[i][j] where i is the index of the element and j is the size of the current knapsack, notice we only need to consider those solutions that have j >= X.
Below is a recursive Dynamic Programming solution in c++ :
#include <iostream>
#include <cstring>
#define INF 1000000000
using namespace std;
int cost[1000], value[1000], n, X, dp[1000][1000];
int solve(int idx, int val){
if(idx == n){
//this is the base case of the recursion, i.e when
//the value is >= X then only we consider the solution
//else we reject the solution and pass Infinity
if(val >= X) return 0;
else return INF;
}
//this is the step where we return the solution if we have calculated it previously
//when dp[idx][val] == -1, that means that the solution has not been calculated before
//and we need to calculate it now
if(dp[idx][val] != -1) return dp[idx][val];
//this is the step where we do not pick the current element in the knapsack
int v1 = solve(idx+1, val);
//this is the step where we add the current element in the knapsack
int v2 = solve(idx+1, val + value[idx]) + cost[idx];
//here we are taking the minimum of the above two choices that we made and trying
//to find the better one, i.e the one which is the minimum
int ans = min(v1, v2);
//here we are setting the answer, so that if we find this state again, then we do not calculate
//it again rather use this solution that we calculated
dp[idx][val] = ans;
return dp[idx][val];
}
int main(){
cin >> n >> X;
for(int i = 0;i < n;i++){
cin >> cost[i] >> value[i];
}
//here we are initializing our dp table to -1, i.e no state has been calculated currently
memset(dp, -1, sizeof dp);
int ans = solve(0, 0);
//if the answer is Infinity then the solution is not possible
if(ans != INF)cout << solve(0, 0) << endl;
else cout << "IMPOSSIBLE" << endl;
return 0;
}
Link to solution on ideone : http://ideone.com/7ZCW8z
Came up with an approach to boil this down to the original Knapsack problem.
First of all, suppose that you have included all the items in your solution.
Your cost is Cost_Max and achieved value is Val_Max (which should be >= X for a solution to exist).
Now, recall the original knapsack problem : Given a set of items with weights W(i) and values V(i), find maximum achievable value for weight limit = w.
Now, we'll use this knapsack problem to find all items not to include in our answer set
So after calculating the Cost_Max and Val_Max in your problem, you have to treat:
- costs(ci's) as values ( i.e V(i)'s )
- values(vi's) as weights( i.e W(i)'s )
- (Val_Max - X) as the weight limit w
This will give you the maximum cost you can remove while your value remains >= X.
So if the cost found from above step is Cost_Knapsack, your answer is Cost_Max - Cost_Knapsack.
