背包九讲(1)——01背包

问题引入 有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-