E knapsack 2 Atcoder

#1

Hello i didn’t got how does the change of state works and how to visualize where the change of state is needed if possible explain with example

#2

Okay I’ll share my approach along with the code.
This is the code https://ideone.com/B0Joub

Now I’ll try to explain the logic.

Given the constraints we can see that the only thing we can form a dp for is the value we get, because vi<=1000 and n<=100, so the total possible value we could gain would be 1000*100.
SO we form a dp array of dp[100005][100];

here dp[i][j] denotes the minimum cost to get value i using items from given index to the last index.

       for (int i = 100000; i >= 0; i--) {
              if (solveDp(i, 0, item, n) <= cap)       return i;
       }

Here we are simply running a loop to find the max value we can get by spending only the amount we are allowed to spend. Cap is the amount we can spend.

       dp[val][index] = min(item[index][0] + solveDp(val - item[index][1], index + 1, item, n),
                            solveDp(val, index + 1, item, n));

This is the normal recurrence that we use in knapsack, i.e., if we pick the current item or we don’t pick the current item.

       if (val <= 0)    return 0;
       if (index == n)  return INTMAX;
       if (dp[val][index] != -1)       return dp[val][index];

And these are our normal base conditions.