完全背包
2026-08-29 12:02:16
发布于：上海
8阅读
0回复
0点赞
完全背包：与01背包唯一的区别是——每件物品有无限件，可以拿多个
01背包和完全背包的区别：
01背包：
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
if(j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
else dp[i][j] = dp[i - 1][j];
}
}
完全背包：
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
if(j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
else dp[i][j] = dp[i - 1][j];
}
}
滚动数组的写法：
01背包：
int dp[j];//表示容量为 j 时背包最大价值
for(int i = 1; i <= n; i++){
for(int j = m; j >= 0; j--){
if(j >= w[i]) dp[j] = max(dp[[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[m];
完全背包：
for(int i = 1; i <= n; i++){//遍历所有物品
for(int j = 0; j <= m; j++){//正序遍历容量，
if(j >= w[i]) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[m];
例题：[USACO14MAR] Mooo Moo S
求：每个牧场能发出总音量，所需要的最少奶牛数。
总音量 = 传过来的音量 + 奶牛自己发出的声音。
思路：
1.先把总音量减去传过来的音量。
2.计算最少需要多少头奶牛能凑出来这个音量。（奶牛看作是一个无限取的物品，看多少头奶牛凑到数字T）
#include<bits/stdc++.h>
using namespace std;
int n, b;
int v[25], p[105];
int dp[100005];//dp[j]：表示凑出音量 j 所需要的最少奶牛数
int main(){
cin >> n >> b;
for(int i = 1; i <= b; i++){
cin >> v[i];
}
for(int i = 1; i <= n; i++){
cin >> p[i];
}
//初始化
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= b; i++){
for(int j = v[i]; j <= 100000; j++){
dp[j] = min(dp[j], dp[j - v[i]] + 1);
}
}
int ans = 0;//总奶牛数
for(int i = 1; i <= n; i++){
int tran = 0;
if(i == 1) tran = 0;
else tran = max(p[i - 1] - 1, 0);
int c = p[i] - tran;
if(c < 0 || dp[c] == 0x3f3f3f3f){
cout << -1 << "\n";
return 0;
}
ans += dp[c];
}
cout << ans << "\n";
return 0;
}
例题：[USACO3.1] 邮票 Stamps（可行性背包）
求：能用邮票凑出的最大面值。
#include<bits/stdc++.h>
using namespace std;
int k, n;
int a[55];
int dp[20000005];
int main(){
cin >> k >> n;
for(int i = 1 ; i <= n; i++){
cin >> a[i];
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= n; i++){
for(int j = a[i]; j <= 20000000; j++){
dp[j] = min(dp[j], dp[j - a[i]] + 1);
}
}
int ans = 0;
for(int i = 1; i <= 20000000; i++){
if(dp[i] > k){
ans = i - 1;
break;
}
}
cout << ans << "\n";
return 0;
}
这里空空如也
有帮助，赞一个