基础01背包问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
我们用dp[i][j]表示前i个物品中容量为j的情况下的最大价值
若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
由此可以得出状态转移方程

dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])

这个算法的时空复杂度均为O(N*V），时间复杂度已经基本不能再优化了，但是空间复杂度还可以再优化一下
考虑到第i个物品的状态只与第i-1个物品的状态有关，我们能不能在枚举 i 的时候，直接通过dp[j]来转移得到最后的答案呢？答案是可以的
只需要稍微修改一下内层的循环即可
原来的循环：
rep(i,1,n)
rep(j,0,v)
{
if(j>=c[i] dp[i][j] = max(dp[i-1][j-1],dp[i-1][j-c[i]]+w[i])
else dp[i][j]=dp[i-1][j-1]
}

优化之后
rep(i,1,n)
...rep(j,v,c[i])
......dp[j]=max(dp[j],dp[j-c[i]]+w[i])

关于为什么要逆序，我们可以举个例子来证明顺序是不可行的
设有3件物品 ,背包能容纳的总重量为10
i=1,2,3

物品号重量(c) 价值(w)
i=1 4 5

i=2 7 9

i=3 5 6

f[v]=max{ f[v],f[v-c[i]]+w[i] }

如果v是顺序递增 i=1时，v=4~10 （因为v要至少大于等于c[i]嘛不然减出个负数没意义）
原先的: f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=0 f[5]=0 f[6]=0 f[7]=0 f[8]=0 f[9]=0 f[10]=0
------------------- i=1 --------------- 后来的： f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=5 f[8]=0 f[9]=0 f[10]=0
v=4:
f[4]=max{f[4],f[0]+5} max{0,5}=5 f[4]=5

v=5:
f[5]=max{f[5],f[1]+5} max{0,5}=5 f[5]=5

v=6:
f[6]=max{f[6],f[2]+5} max{0,5}=5 f[6]=5

v=7:
f[7]=max{f[7],f[3]+5} max{0,5}=5 f[7]=5

v=8:
f[8]=max{f[8],f[4]+5} max{0,10}=10 f[8]=10 (这里显然不对,这时i=1，只能放一件物品,然而没有一个物品的价值为10的，但是给了我们完全背包的提示)

v=9:
f[9]=max{f[9],f[5]+5} max(0,10}=10 f[9]=10

v=10:
f[10]=max{f[10],f[6]+5} max{0,10}=10 f[10]=10

--------------------------- i=1 --------------------------------
既然顺序 i=1都不对 i=2和3就不用看了由此看来顺序不行

===============================================

下面再来看看逆序的我为了方便看把上面的数据复制过来
设有3件物品 ,背包能容纳的总重量为10
i=1,2,3

物品号重量(c) 价值(w)
i=1 4 5

i=2 7 9

i=3 5 6

f[v]=max{ f[v],f[v-c[i]]+w[i] }

如果v是逆序,v=10~4
------------- i=1 ------------- f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=5 f[8]=5 f[9]=5 f[10]=5
v=10:
max{f[10],f[6]+5} max{0,5}=5 f[10]=5

v=9:
max{f[9],f[5]+5} max{0,5}=5 f[9]=5

v=8:
max{f[8],f[4]+5} max{0,5}=5 f[8]=5

v=7:
max{f[7],f[3]+5} max={0,5}=5 f[7]=5

v=6:
max{f[6],f[2]+5} max={0,5}=5 f[6]=5

v=5:
max{f[5],f[1]+5} max={0,5}=5 f[5]=5

v=4:
max{f[4],f[0]+5} max={0,5}=5 f[4]=5

--------------------------- i=1 --------------------------------
///////////////////////////////////////////////////////////

---------------- i=2 ------------ f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=9 f[8]=9 f[9]=9 f[10]=9
v=10:
max{f[10],f[3]+9} max{5,9}=9 f[10]=9

v=9:
max{f[9],f[2]+9} max{5,9}=9 f[9]=9

v=8:
max{f[8],f[1]+9} max{5,9}=9 f[8]=9

v=7:
max{f[7],f[0]+9} max{5,9}=9 f[7]=9

--------------------------- i=2 --------------------------------
///////////////////////////////////////////////////////////

----------- i=3 -------------- f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=9 f[8]=9 f[9]=9 f[10]=9
v=10:
max{f[10],f[5]+6} max{9,11}=11 f[10]=11

v=9:
max{f[9],f[4]+6} max{9,11}=11 f[9]=11

v=8:
max{f[8],f[3]+6} max{9,6}=9 f[8]=9

v=7:
max{f[7],f[2]+6} max{9,6}=9 f[7]=9

v=6:
max{f[6],f[1]+6} max{5,6}=6 f[6]=6

v=5:
max{f[5],f[0]+6} max{5,6}=6 f[5]=6

--------------------------- i=3 --------------------------------

由此看来逆序就是正常的