This blog entry is regarding a doubt in a problem from hackerearth.
I need help regarding my solution as I am getting wrong answer verdict for all testfiles(except one), I am unable to understand what is going wrong in my code, any sort of help is highly appreciated.
Problem description in brief:
Given an integer N denoting the number of elements, an integer W denoting the maximum capacity of the bag and a set of elements with their respective value and weights.
The problem is to find the maximum value that can be achieved by choosing some elements(if possible all), similar to the Knapsack problem, the only difference is that we can either multiply the value of any element by any of the first 10 prime numbers (Note: if a prime number is chosen once then it can not be chosen for any other number) or we don't.
For example:
Let N = 3(number of elements) and W = 4(maximum capacity of bag) and element's value and weight respectively are
1 1
2 1
3 1
then answer will be 152 i.e. (3 * 29) + (2 * 23) + (1 * 19) = 152
My approach :
My approach consisted of firstly sorting all the elements according to their given value in ascending order and then making a 3 state dp array i.e. dp[N][P][W] where dp [i][j][k] will denote the maximum value by using first i elements with first j primes and having a total weight equal to k.
Memory optimization:
To optimize memory I tried to toggle state of N between 0 and 1 as in knapsack we need the answers for previous state to compute the current state, therefore my dp array size became 2 * 10 * 2000.
Recurrence relation that I formulated:
Note: Here i, j and k are used for number of elements, number of primes and total weight till now respectively.
dp[i][j][k] = dp[i - 1][j][k];
if(k >= element[i].weight)
{
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - element[i].weight] + element[i].value);
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - element[i].weight] + (element[i].value * primes[j]));
}
In my code I am finding the answer of the current state by toggling the value of i(the index used for number of elements) between 0 and 1.
Can anyone help in telling what is the ambiguity in my code or where my logic is failing?
