问题引入
有n种物品，每种只有一个。第i种物品的体积为vi，价值为wi。选一些物品装入到一个容量为C的背包中，使得在总体积不超过m的情况下使得背包内物体总价值尽量大
状态转移
首先我们不难发现影响决策的因素有两个：
第i个物品装或者不装
使用j(j<=C)容量后得到的最大价值
实际上容量是一个有序的枚举过程，但是每个物品选或不选是影响决策的主要因素，下面有两种对称的状态定义：
逆序枚举
设dp(i,j)表示将第i,i+1,i+2,…,n个物品装入容量为j的背包中的最大价值，则：
dp(i,j) = dp(i+1,j)
dp(i,j) = max { dp(i,j)，dp(i+1,j-v[i
- 1
- 2
前往页