定义：题目中的物品不可以分割，要么装进包⾥，要么不装， 不能说切成两块装⼀半。——– 0-1 背包
题目：
给你⼀个可装载N 个物品和重量为 W 的背包 ，每个物品有重量和价值两个属性。其中第 i 个物品的重量为wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
限定的就是容量，求的就是价值！
如：即背包可放三个物品，最大容量为4，求最大重量？
限定的是容量即W，求的是重量即val ；
N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]
-
状态和选择：
1.状态：
状态有两个，就是「可选择的物品 N(i) 」和「背包的容量 W」；
2.选择：
选择就是「装进背包」或者「不装进背包」； -
dp数组定义：
dp[i][w] 的定义如下：对于前 i 个物品进行选择，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]，根据这个定义，所求的最终答案就是 dp[N][W]。
如：dp[3][5] = 6，其含义为：对于给定的⼀系列物品中，若只对前 3 个物品进⾏选择，【当背包容量为 5 时】，最多可以装下的价值为 6。 -
basecase：
base case 就是 dp[0][…] = dp[…][0] = 0，即没有物品和没有容量时，背包装的价值为0； -
状态转移：
第一层for：遍历每个物品 i ，判断是否装入
第二层for：遍历每种w容量约束的；
状态转移：
1.如果没有把这第 i 个物品装入背包，那么最大价值 dp[i][w] = dp[i-1][w]，继承上次的结果；
2.如果把这第 i 个物品装入了背包，那么 dp[i][w] =val[i-1] + dp[i-1][w – wt[i-1]]， 即容量减少，价值可能增加；
即前i-1个物品相当于放到了容量为 w – wt[i-1]]的背包里！
注意：由于wt[] 和 val[ ] 数组索引从 0 开始，⽽定义dp数组中的 i 是从 1 开始计数的，所以 val[i-1] 和 wt[i-1] 表示第 i 个物品的价值和重量;
框架：
选择：放进背包和不放进背包 ；
如果当前容量w小于当前 i 物品所需的容量wt[i]，则一定不放入背包；
注意：
- dp的物品数量N和当前容量W是从1开始记数！ 而wt[ ] 和val[ ] 是从0开始记数的！所以 遍历状态时，物品个数 i 从1开始到 N， 容量 w 从1开始到W；
- dp[][]中，i=0是base case，dp[0][…]和dp[…][0]必须为0，所以 i 从1 开始；
- 初始化dp 是dp[N+1][W+1] !
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89204.html
