Question 1308

Ascending Buys Three Copies

0/1 knapsack, space-optimised to one array. Two items, capacity 6.

int w[] = {0, 2, 3};      // 1-indexed
int v[] = {0, 3, 4};
int W = 6;
int f[7] = {0};

for (int i = 1; i <= 2; i++)
    for (int j = w[i]; j <= W; j++)          // ascending
        f[j] = max(f[j], f[j - w[i]] + v[i]);

cout << f[W];

What does this print?

A

6, from two copies of item 1 with capacity 2 unused

B

9, because f[j - w[i]] may already contain item i, so item 1 gets taken three times

C

7, the correct 0/1 answer; loop direction changes only which intermediate values appear

D

8, from two copies of item 2 with capacity 6