Where i am doing wrong in colorful knapsack ? [dp]
Hi Dhruv
I have acknowledged your doubt
Can you please post the link to the question as well?
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. See the explanation of the sample test cases for clarity
Input Format
The first line contains three integers, N, M and X, separated by single space. 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.
Constraints
1 ≤ M ≤ 100 M ≤ N ≤ 100 1 ≤ W[i] ≤ 100 1 ≤ C[i] ≤ M 1 ≤ X ≤ 10000
Output Format
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.
Sample Input
9 3 10
1 3 5 1 3 5 1 3 5
1 1 1 2 2 2 3 3 3
Sample Output
1
Explanation
You cannot select stones such that the knapsack is completely full. You can select stones {1, 4, 9}, such that the unused capacity is 10-1-1-5 = 3. But there is a better way. Select stones {2, 5, 8}. The unused capacity is 10-3-3-3 = 1. This is the optimal way. There is another way that is optimal. Select stones {1, 5, 9}. The unused capacity is 10-1-3-5 = 1.
Hi just checked your code. Algorithm wise it should not produce any errors as the algorithm is to group the stones color wise and then apply 0/1 knapsack with the dp element storing the maximum weight possible. That means the problem is in implementation.
After line 51 of your code, you have missed a condition of if (i > X) break; apart from that rest everything is fine
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
i did that but still it can’t pass last test case
Your dp part is fault-proof that was the only part missing in it. Still add the line to the code as that is correct
Apart from that can you explain how you have allocated your color groups, specifically the if(colors[i] != alist.size() part as I think that could be a potential point of error. Rest is the input output part and no errors in it.
ok got it. i found the error.