Introduction

Pass, see Knapsack problem

0-1 Knapsack problem

This is the easist knapsack problem. There are $N$ items and the volume of your knapsack is $V$. The cost of the $i$ th item is $C_i$ and the value of that item is $W_i$. You need to find the best solution to get the max value.

We define $F[i, v]$ to store the max value of the first i items in the knapsack whose volume is v. Then we have

HDU 2602 is a nake problem of 0-1 knapsack:

Space optimization of HDU 2602:

Reference:

背包问题九讲

Wikipedia