赞
踩
零:背包物品的含义
一:dp数组的含义
dp数组的含义灵活多变,在不同题目中有不同的含义
dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]
在遍历过程中,dp数组的含义也不断改变,第一次遍历第一个for,即 i 首先为0时,对应现有物品0时,不同重量背包最大价值,第二次遍历第一个for,即 i 为1时,对应现有物品0,1,不同重量背包最大价值,第二次遍历for就会对数组中的数据进行覆盖(第一次遍历for的操作形成的)。
有两个for,第一个for是 决定选择哪些物品即 0~i类似于选定行,第二个for是依次给数组中的元素赋值 类似于选定列。
for i{
for j{
}
}
二:dp数组的递归公式
通过动态规划的含义即当前值可由前一个值推导出,此时就可以联想到,通过是否将最后一个物品添加到背包中进而实现递归公式。
所以递归公式为:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
三:一维dp数组的初始化
通过递归公式来判断应该怎样初始化才能达成目的,举例子模拟完整实现过程,进而反推出应该如何初始化。
看一下递归公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp【j】要么选择原先的dp【j】(即初始化的dp【j】)要么选择新计算的值,会选择两者中较大的那一个。
如果dp【j】选择的是新计算的值,dp【j】是从二者中选择更大的值,那么这个初始化的dp【j】就不能够大于新计算的值,新计算的值恒大于0。所以初始化的dp【j】为0即可。
若dp【j】选择的是dp【j】(初始化的值)即没有加入物品,初始化后所进行的是第一个物品放入大小为 j 的背包的最大价值,表示的是不加入物品,即一个物品也不加入,那么其价值为0,初始化也应该为0。
四:一维dp数组遍历顺序及i 的含义,j的含义及i,j范围
二维dp遍历的时候,背包容量是从小到大,而一维dp遍历的时候,背包是从大到小。
顺序遍历:
顺序遍历会使本层的dp【i】【j】被覆盖,当前值为上方的一个值和左上方的一个值决定。一维会实现覆盖,顺序遍历时,此时判断物品1在各种背包重量下是否放入的情况,当背包容量为2的时候物品若能放入此时的价值即dp【2】加上了物品1的价值,当背包容量为3的时候物品若能放入此时的价值是dp【2】+value【1】(此时并不一定是dp【2】但一定比3小此时假设为dp【2】),此时的dp【2】是已经覆盖了的dp【2】(添加了物品1的dp【2】)并不是原先那个dp【2】(没有添加物品1的dp【2】)了,此时即表示加入了两次物品1。
逆序遍历:
逆序遍历,是背包容量从大到小遍历,此时判断物品1在各种背包重量下是否放入的情况,当背包容量为3的时候物品若能放入此时的价值是dp【x】+value【1】,x = 3-weight【i】因此x肯定是比3小的,又因为是从后往前遍历的,前面的值是原来的值是没有被覆盖的,覆盖的是当前值后面的值。
两个嵌套for循环的顺序
从尾到头遍历,同时应该背包重量大于物品重量才进入这个for,即 结束条件 j >= nums[i]而不是j >= 0
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]);
}
}
一维dp01背包完整C++测试代码
void test_1_wei_bag_problem() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; // 初始化 vector<int> dp(bagWeight + 1, 0); 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]); } } cout << dp[bagWeight] << endl; } int main() { test_1_wei_bag_problem(); }
适用题型:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。