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 !

Thanks a lot buddy it helped me a lot :)