01背包-一维dp数组学习笔记
01背包-一维dp数组学习笔记
https://blog.csdn.net/qq_44653420/article/details/126973071?spm=1001.2014.3001.5501
一、一维dp数组概述
在使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j],dp[i][j - weight[i]] + value[i]);
如果把dp[i - 1]层拷贝到dp[i]上,表达式变成:dp[i][j] = max(dp[i][j],dp[i][j - wight[i]] + value[i]);
如果使用一维数组dpj:表示上一层可以重复利用,直接拷贝到当前层
二、动态规划实现
- 确定dp数组的含义
在一维dp数组中,dp[j]表示容量为j的背包所容纳物品的最大价值
- 确定一维dp数组的递推公式
dp[j]此时由两种状态推导出来:不放物品i,放物品i
对于不放物品i,那么此时的dp[j]直接就是上一层的dp[j]拷贝而来,如果存放物品i,那么此时的dp[j]表示为dp[j - weight[i]] + value[i],意思就是容量为j -物品i重量的背包中的价值加上物品i的价值
dp[j] = max(dp[j],dp[j - weight[i]] + value)
-
初始化一维数组
dp[j]表示的是容量为j的背包所具有的最大价值,那么dp[0] = 0,对于非0下标的dp数组如何初始化:每次dp[i]缺的是最大的价值,所以每一个dp[i]初始化成所有物品的最小价值,由于每一个物品的价值都是大于0的,所以干脆全部初始化为0
-
确定一维dp数组的遍历顺序
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]); } }
二维dp数组遍历背包的时候,背包的容量是从小到大开始遍历的,但是一维dp数组遍历背包的时候,背包容量是从大到小遍历的。
倒序遍历的目的是为了物品i只被放入背包一次.
另外,一维dp数组必须先遍历物品,在遍历背包,每一个dp[j]就只会放入一个物品,也就是背包中只放入一个物品。
-
代码实现
void func()
{
vector<int> weight = {1,3,4};
vector<int> value = {15,20,30};
int bagWeight = 4;
// 初始化dp数组
vector<int> dp(bagWeight + 1,0);// 全部初始化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;
}