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?
I don't see anything wrong with the solution , can you give me the problem link , so i can try ?
Click on the "Problem Link" tag on the second line of my blog to open the question. Please help with a solution asap, I am really not able to find my mistake.
By the way I also shared the link to my solution at the bottom of my blog, please do check it once, thanks.
I fixed your solution , actually you didn't consider that 1 can be used as many times as possible , and you didn't update the dp array for the index 0 for the primes , that's why your solution always takes at maximum 10 products only , here is my try , it got accepted !