91 views
1 1 vote
There is an unlimited supply of three item types:

$$\begin{array}{|c|cc|}
\hline
\text{Item} & \text{Size} & \text{Value} \\
\hline
A & 1 & 2 \\
B & 2 & 6 \\
C & 3 & 9 \\
\hline
\end{array}$$

The knapsack capacity is $5$.

What is the maximum total value obtainable?

1 Answer

0 0 votes

Because items may be used repeatedly, this is an unbounded knapsack problem.

Let, 

$DP[w]=$ maximum value possible with capacity $w$

For each capacity:

$DP[w]=\max_i\{value_i+DP[w-size_i]\}$

Now calculate.


Capacity $\mathbf{1}$

Only A fits:

$DP[1]=2$


Capacity $\mathbf{2}$

Options:

$A+A=4$

$B=6$

$\therefore DP[2]=6$


Capacity $\mathbf{3}$

Options include:

$A+A+A=6$

$A+B=8$

$C=9$

$\therefore DP[3]=9$


Capacity $\mathbf{4}$

Best choice:

$B+B$

Value:

$6+6=12$

$\therefore DP[4]=12$
 

Capacity $\mathbf{5}$

Possible optimal combinations include:

$B+C$

Weight:

$2+3=5$

Value:

$6+9=15$

$\therefore DP[5]=15$

 

Answer : $\boxed{15}$

Answer:
Position:
Show:

Related questions

2 2 votes
1 1 answer
138
138 views
GO Classes asked Aug 22
138 views
True or False:In every dynamic-programming solution, the asymptotic space requirement must be at least as large as the total number of distinct subproblems.True False
0 0 votes
1 1 answer
87
87 views
GO Classes asked Aug 22
87 views
The following function $\texttt{CalcEditDistance}$ computes the edit distance between two strings.For this problem:Inserting one character has cost $1$.Deleting one chara...
2 2 votes
1 1 answer
95
95 views
0 0 votes
1 1 answer
77
77 views
GO Classes asked Aug 22
77 views
An instance of Subset Sum contains:$n$ positive integersa positive target value $m$What is the running time of the standard dynamic-programming solution?$\Theta(m+n)$ $\T...