4 5
1 2
2 4
3 4
4 5
就用这个测试数据testcase举个例子,可泛化到任意正整数。
n= 4, M=5. 四个物品,背包最大体积5.
公式:
$dp[i][j]=\max{(dp[i-1][j-v]+w, dp[i-1][j])}$
二维缩减
$dp[j]=\max{(dp[j-v]+w, dp[j])}$ (但是i-1)
初始化:
dp = [0 0 0 0 0]
随后第一轮
j=0;j<=5;j++ 升序遍历这个集合的话:(也就是升序递推构建/apply formula应用状态转移来覆盖整个状态空间dp[i][j]/dp[j]
dp[0]=dp[0-1]+2,dp[0]=0
dp[1]=dp[1-1]+2,dp[1]=dp[0],dp[1]=2 这时dp[0]是i轮的而不是i-1轮上一轮的,所以违背了定义。
dp[2]同理=dp[2-1]+2,dp[2]=2 dp[1]2是i轮的
----
或者用j=1 来演绎一样的
dp[1]=dp[1-1]+2,dp[1]=2
dp[2]=dp[2-1]+2,dp[2]=dp[1]+2,dp[2]=4 这时dp[1]用的不是上一轮i-1的而是i的了。
所以:倒序遍历刚好满足i-1的定义
j = 5; i>=0; j–
dp[5] = dp[5-1]+2,dp[5]=dp[4]+2,dp[5]=2 (这时dp里五项都是0)
dp[4] = dp[4-1]+2,dp[4]=dp[3]+2,dp[4]=2
QED 证毕