Dynamic Programming $($DP$)$ can provide optimal solution of the knapsack problem. In DP$,$ we compute the solutions to the smaller problems and store them in a table, to be reused later repeatedly to solve a larger problem.

For the knapsack problem given in Fig. $1,$ a typical DP table is shown below. We start with $0$ items and $0$ capacity of the knapsack and keep increasing them along rows and columns respectively. The first non$-$zero row is constructed assuming that only item $1$ is available, while the next row assumes that items $1$ and $2$ are available, and so on$.$ Similarly, the first non$-$zero column is filled assuming that the knapsack capacity is only $1$ Kg$,$ and so on$.$

Construct the DP table for the problem given in Fig. $1.$ Then use backtracking technique learned in the class, starting from the last cell, to determine which items shall be placed in the knapsack.

Solution:

Capacity $($Kg$)$

Number of items $0123456789101112131415$

$00000000000000000$

$10000000000044444$

$20222222222246666$

$30224444444446688$

$40234555555556789$

$50234101213141515151515151515$ solve in java