Problem $1$ Dynamic Programming

Knapsack Problem: Given a set of five items, with each item having a positive benefit and a positive weight. Use the dynamic programming method to select items from the set to maximize the total benefit while keeping the total weight at $W=11$ lbs or less. $(15$ pts $)$

Items:

Weight:

$4$ lbs

$3$ lbs

$2$ lbs

$5$ ILs

$3$ lbs

Benefit:

$$20$

$$18$

$$12$

$$24$

$530$

Weight limit $W=11$ Ibs

The DP solution is given as:

$Tk,w$

The best subset of $S_k$ with weight at most $w$ is either the best subset of $S_{k-1}$ with weight at most $w$ or the best subset of $S_{k-1}$ with weight at most $w-w_k$ plus item $k.$ Let $T_k$ denote the total benefit of $S_k.$ Determine each value of $T_k$ with weight at most each $w.$

$\backslash$table$[[$Name$,$Weight,Benefit,$0,1,2,3,4,5,6,7,8,9,10,11],[$A$,,,,,,,,,,,,,,],[$B$,,,,,,,,,,,,,,],[$C$,,,,,,,,,,,,,,],[$D$,,,,,,,,,,,,,,],[$E$,,,,,,,,,,,,,,]]$