Finding the Max Sum less than or equal a fixed number using Dynamic Programming

I have an array of category Name and it’s weight, fixed number W, I need to get the sequence of categories that gives me the Max weight <= W.

I Can solve it recursively by maximizing between (take the category or leave it) but i don’t know how to switch this approach to the Dynamic programming 2D table.

For example:


w: 50

A: [{c1,51},{c2,30},{c3,15},{c4,10},{c5,10}]

Output: [c2,c4,c5]

The total weight of (c2+c4+c5) = (30 + 10 + 10) = 50


w: 50

A: [{c1,50},{c2,30},{c3,15},{c4,10}]

Output: [c1]

The total weight of c1 = 50


w: 50

A: [{c1,30},{c2,10},{c3,15},{c5,15}]

Output: [c1,c3]

The total weight of (c1+c3) = (30 + 15) = 45