动态规划

2024-07-11 14:59| 来源: 网络整理| 查看: 265

动态规划---完全背包问题详解

鸣谢：本次的学习是跟着Carl的笔记来的，原创作者为Carl，可以在b站或者公众号关注Carl，搜索代码随想录。

完全背包理论基础

1、问题

背包最大容量为4，现有下面的物品各无限个。

重量价值物品0 1 15 物品1 3 20 物品2 4 30

问：背包能背的最大物品价值是多少？

2、与01背包的区别

01背包遍历顺序的核心思路

for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }

内层的循环，从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包中的物品是可以添加多次的，所以需要我们从小到大去遍历。即：

// 先遍历物品，再遍历背包 for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }

3、一维dp和二维dp 01背包中⼆维dp数组的两个for遍历的先后循序是可以颠倒了，⼀位dp数组的两个for循环先后循序⼀定是先遍历物品，再遍历背包容量。

在完全背包中，对于⼀维dp数组来说，其实两个for循环嵌套顺序同样无所谓！

因为dp[j] 是根据下标j之前所对应的dp[j]计算出来的。只要保证下标j之前的dp[j]都是经过计算的就可以了

// 先遍历背包，再遍历物品 for(int j = 0; j = 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }

二维dp的话，其实和之前01背包是一样的

// 初始化 // 当j=0时，背包容量为0，最大价值为0；当i=0时，也就是前0件物品，也就是没有物品，最大价值也是0 for (int i = 1; i

【本文地址】

公司简介

联系我们