差異只在「拿商品」時看上一列,還是看同一列。
建議先用 5~12,表格比較好看。
目前計算
正在計算 dp[i][j]
不拿:dp[i-1][j]
拿:0/1 看 dp[i-1][j-w];完全看 dp[i][j-w]
本格最後結果
白話解釋
商品資料
DP 表格
橫軸是容量
j,縱軸是「只考慮前 i 個商品」。灰色代表還沒算到。
核心差異整理
0/1 背包:拿第 i 個商品後,不能再拿同一個,所以資料從上一列來:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + val[i])
完全背包:拿第 i 種商品後,還可以繼續拿同一種,所以資料從同一列來:
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + val[i])
你可以把它想成:0/1 背包是「拿一次就往下一個商品走」;完全背包是「拿了之後還站在同一種商品旁邊,可以再拿一次」。