This is a modified 0/1 knapsack problem. The first line contains n, the number of array elements. The next n lines contain the array elements. There are three things given for each element. 1) Type 2) Weight 3) Value and W which is the maximum limit of total weight. So, here we have to maximize the total value, by taking each type of element atmost one time. The constraints are 1<=W,Type,Weight,Value<= 5000. How to solve this problem? What would be the states?
Table: Dp[count of different types][W]
Transitions: dp[i+1][j]=max(dp[i][j], dp[i+1][j])
dp[i+1][j+WEIGHT_k]=max(dp[i][j]+VALUE_k, dp[i+1][j+WEIGHT_k]) where WEIGHT_k is weight of kth item and VALUE_k is value of kth item, but look only at items that have type==i
But here three things are changing: type, weight used and index. I am not able to understand how are you managing that. Can you elaborate a little?
Let's see this from the forward direction.
Imagine that dp[i][j] is telling you "The optimal value if I am only using the first i types of items, and my knapsack weighs exactly j"
Now let's think about state. Naturally from state [i][j] you consider the next type of items which is type (i+1). Well, for every k such that TYPEk=i+1, consider what state you end up in, if you add it to your current state. Once you add it, you cannot use anything else with type i+1, and your weight increases with WEIGHTk. So there is a transition from (i,j) to (i+1,j+WEIGHTk) with value VALUEk. What about if you decide to not pick anything at all from type i+1? Well then it's just a transition from (i,j) to (i+1,j) with a value of 0.
Now you can use this directly to write a recursive implementation with memoization, or you can inverse the transitions to get the DP described by the original comment.
You have O(MAXTYPE∗W) different states. Naively it seems like each might take up to O(N), but a more careful inspection shows that for any fixed j in the second dimension, the total number of items you'll consider across all possible i's is O(N) since each item is of exactly one type, so computation actually amortizes to O(N∗W), so O((MAXTYPE+N)∗W) time complexity and O(MAXTYPE∗W) space complexity, both comfortably work for 5000.
P.S.
Since MAXTYPE≤N (otherwise you can compress the types initially), it's easier to think of it as time and space complexity as O(N∗W)
How much would you rate this problem?
I do not do enough Codeforces to be able to rate it within the Codeforces system, but it is generally a somewhat easy dynamic programming problem. It is only "one logical step above" the classic knapsack which itself is introductory.
If you found it difficult then it's just a matter of practicing dynamic programming a lot more. Once it becomes intuitive to manipulate the states, problems like this one are pretty straightforward.
To illustrate further why there is nothing particularly complicated about setting up the state and transitions here, if you were to set the problem with N≤20, you can imagine the bruteforce that a lot of people would write will actually be having exactly the state described above, so making it a DP would be trivially adding memoization. Problems in which you can derive the state and transitions in such a simple way without further optimizations eventually become trivial if you're comfortable with DP.