文章目录
- 一、完全背包问题的特征
- 二、定义状态
- 三、状态转移
- 四、降维优化
- 五、参考例题
- 5.1、Acwing:3.完全背包问题
- 5.2、Acwing:900. 整数划分
一、完全背包问题的特征
完全背包问题是动态规划中的一种经典问题,它的主要特征可以总结如下:
-
无限使用物品:与0-1背包问题不同,其每种物品只能使用一次,而完全背包问题允许每种物品被无限次选取。
-
背包容量限制:存在一个容量限制
W
,所有选取的物品总重量不能超过这个限制。 -
目标函数:目标是在不超过背包容量的前提下,最大化背包内物品的总价值。
-
复杂度:完全背包问题的时间复杂度和空间复杂度取决于具体的实现方法,通常时间复杂度为
O(NW)
,其中N
是物品数量,W
是背包容量。通过优化,空间复杂度可以降低到O(W)
。
二、定义状态
- 定义
dp[i][j]
表示,考虑前i
个物品且背包容量为j
时的最大价值。
三、状态转移
dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+price[i])
- 即背包容量为
j
时,考虑前i
个物品的最大价值从两个方面转移而来:dp[i-1][j]
:不加入物品i
时,容量为j
的背包利益最大值。dp[i][j-weight[i]]+price[i]
:加入物品i
时,容量为j
的背包利益最大值。
我们需要特别注意这里和0-1背包的区别,
0-1背包:dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+price[i])
,因为0-1背包每个物品要么放要么不放,而完全背包问题每个物品可以放置多次,因此转移时是从考虑物品i
的情况下转移的。
for(int j=weight[0];j<=V;++j)
dp[0][j]=dp[0][j-weight[0]]+price[0];
for(int i=1;i<N;++i)
for(int j=weight[i];j<=V;++j)
dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+price[i]);
四、降维优化
考虑到状态转移的时候,我们是一个物品一个物品考虑的,相当于二维数组中一行一行考虑的,当前状态只需要用到之前的状态,因此我们可以进行降维优化。将空间降低到一维:
dp[0]=0;
for(int i=0;i<N;++i){//考虑第i个物品
for(int j=weight[i];j<=V;++j){
dp[j]=max(dp[j],dp[j-weight[i]]+price[i]);
}
}
五、参考例题
5.1、Acwing:3.完全背包问题
模板题
3.完全背包问题
#include<bits/stdc++.h>
using namespace std;
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N,V;
cin>>N>>V;
vector<int> volume(N);
vector<int> price(N);
for(int i=0;i<N;++i){
cin>>volume[i]>>price[i];
}
vector<int> dp(V+1);
dp[0]=0;
for(int i=0;i<N;++i){//考虑第i个物品
for(int j=volume[i];j<=V;++j){
dp[j]=max(dp[j],dp[j-volume[i]]+price[i]);
}
}
cout<<dp[V];
return 0;
}
5.2、Acwing:900. 整数划分
900.整数划分
整数划分问题可以转换成,完全背包问题。即:
对于体积为n的背包,有1~n ,n个物品,每个物品的体积为其编号大小,求体积为n的背包能被装满的不同物品放置种类数。
整数划分问题解析