You are given N stones, labeled from 1 to N. The i-th stone has the weight W[i]. There are M colors, labeled by integers from 1 to M. The i-th stone has the color C[i] (of course, an integer between 1 to M, inclusive). You want to fill a Knapsack with these stones. The Knapsack can hold a total weight of X. You want to select exactly M stones; one of each color. The sum of the weights of the stones must not exceed X. Since you paid a premium for a Knapsack with capacity X (as opposed to a Knapsack with a lower capacity), you want to fill the Knapsack as much as possible.
Write a program that takes all the above values as input and calculates the best way to fill the Knapsack – that is, the way that minimizes the unused capacity. Output this unused capacity.
Input
The first line of input contains the integer T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains three integers, N, M and X, separated by singlespace. The next line contains N integers, W[1], W[2], W[3] … W[N], separated by single space. The next line contains N integers C[1], C[2], C[3] … C[N], separated by single space.
Output
An optimal way of filling the Knapsack minimizes unused capacity. There may be several optimal ways of filling the Knapsack. Output the unused capacity of the Knapsack (a single integer on a line by itself) for an optimal way. If there is no way to fill the Knapsack, output -1. Output T lines, one for each test case.
We were asked the same problem in the online coding round. I solved it using dynamic programming.
Let dp[i][j] denote the maximum possible weight you can fill in the bag with total capacity of j using exactly one stone of each colour from 1 to i.
Now you can club all same coloured stones in a vector. Then this problem becomes more like a classical knapsack problem. Try thinking of transition now and if you still aren’t able to figure out, let me know
To do this question one needs to know how to solve classical 0/1 Knapsack problem. We will be using 2-D array for our DP solution. dp[i][j] will store the maximum possible weight when we have to choose exactly i stones of each different color and our knapsack weight is assumed to be of j weight. To get optimal value at dp[i][j] we will iterate through all available weights of color i. If we can choose weights from all colors dp[i][j] won’t be -1.
Here is the psuedo code:
for j from 1 to x:
dp[1][j]=-1
for weight in vector(1):
if weight<=j:
dp[1][j]=max(dp[1][j],weight)
for i from 2 to m:
for j from 1 to x:
dp[i][j]=-1
if i>x:
break
for weight in vector(m):
if j>weight && dp[i-1][j-weight]>0:
dp[i][j]=max(dp[i][j],dp[i-1][j-weight]+weight)
For 9 3 10
2 3 4 2 3 4 2 3 4
1 1 1 2 2 2 3 3 3
1
2
3
4
5
6
7
8
9
10
1
-1
2
3
4
5
5
5
5
5
5
2
-1
-1
-1
4
5
6
7
8
8
8
3
-1
-1
-1
-1
-1
6
7
8
9
10
For 9 3 10
1 3 5 1 3 5 1 3 5
1 1 1 2 2 2 3 3 3
1
2
3
4
5
6
7
8
9
10
1
1
1
3
3
5
5
5
5
5
5
2
-1
2
2
4
4
6
6
6
6
6
3
-1
-1
3
3
5
5
7
7
9
9
Note: We can reduce some computations by observations.
Ok, so you can firstly fill the dp table with 0 value. After that, filling up the first row is trivial as well.
Now, you can iterate over all possible stones of all colour one by one and fill the table as :
for j = 1 to x:
for i = 2 to colour_max:
for weight_of_stone in stones_of_colour[i]:
if(j > weight_of_stone && dp[i - 1][j - weight_of_stone] > 0)
dp[i][j] = max(dp[i][j], dp[i - 1][j - weight_of_stone] + weight_of_stone);
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
int colorfulKnapsack(int w[], int c[], int n, int m, int x){
VVI dp(m+1, VI (x+1, 0));
VVI v(m+1);
for(int i=0;i<n;i++){
v[c[i]].push_back(w[i]);
}
for(int i=0;i<=x;i++){
dp[0][i] = 1;
}
for(int i=1;i <= m;i++){
for(int z=0;z <= x;z++){
if(i == 1){
for(int j=0;j<(int)v[i].size();j++){
if(v[i][j] <= x) dp[i][v[i][j]]=1;
}
//continue;
}
else{
for(int j=0;j<(int)v[i].size();j++){
if(z-v[i][j] >= 0 && z-v[i][j] <= x ){
if(dp[i-1][z - v[i][j]] == 1){
dp[i][z]=1;
break;
}
}
}
}
//cout<<dp[i][z]<<" ";
}
//cout<<endl;
}
//search for first 1 from right in mth row
//if no 1 then no solution is not found
int ans=-1;
for(int i=x;i>=0;i--){
if(dp[m][i] == 1){
ans=i;
break;
}
}
return ans == -1 ? -1 : x - ans;
}
This code works and give right answer. But the time complexity can be optimized further.
We can use a map and store the true values for the previous row. So complexity can be reduced to O(max_sum * n).
we can map each color with all weights with same color
eg : use Map<int, vector> mp
8 3 13
2 3 4 2 4 5 2 3
1 1 1 2 2 2 3 3
map
col--> list of weight is same color
1 -> [2 3 4]
2 -> [2 4 5]
3 -> [2 3]
now we can think of Dynamic Programming
for each color we we have only one choice to pick it and but which one to be picked it may differ
so calculate max answer will give us minimum unused capacity
Code
#include <bits/stdc++.h>
int cnt = 1e9;
int solve(int idx , int target , int m , map<int, vector<int>>&mp
,map<pair<int,int> , int>&dp ){
//base
if(idx == m){
cnt = min(cnt , target);
return target;
}
if(target <= 0 ){
return 1e9;
}
if(dp.find({idx , target})!= dp.end())return dp[{idx,target}];
//pick 1 from one color
int curr = 1e9;
for(auto j : mp[idx+1]){
if (target >= j) {
int temp = j + solve(idx + 1, target - j , m ,mp , dp );
curr = min(curr , temp);
}
}
return dp[{idx , target}] = curr;
}
int colorfulKnapsack(int w[], int c[], int n, int m, int x)
{
map<int, vector<int>>mp;
map<pair<int,int> , int>dp;
for(int i =0 ; i < n ; i++){
mp[c[i]].push_back(w[i]);
}
solve(0 , x , m , mp , dp);
return cnt==1e9 ? -1 : cnt;
}