01背包 完全背包 多重背包 二维费用背包

时间:2021-08-04 18:41:27

 每种物品只有一件的是01背包

每种物品有无限件的是完全背包

每种物品有有限件的是多重背包 (利用二进制思想,转化为01背包)

每种物品有多重价值的是二维费用背包

这几种背包基本的动态转移方程

      dp[i][j] 从前i件物品选择若干物品装到容量为j的背包中产生的最大价值

     dp[i][j] = max{ dp[i-1][j] , dp[i][j - c[i] ] + w[i] }