题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示:
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例
10
思路
通过二进制优化,将重复的背包进行打包后计算,有效降低复杂度
将s个物品拆分成s个1后,进行打包,打包成logs
个新的物品组,这几个物品组可以凑出0~s任意一个数
时间复杂度从o(s)
优化为o(log(s))
假设有7个物品
可以打包成1,2,4 1+2+4=2^0+2^1+2^2=7
这3个数可以凑出0~7
0
1
2
3=1+2
4
5=1+4
6=2+4
7=1+2+4
如果有10个物品
可以打包成1,2,4,3 1+2+4=2^0+2^1+2^2=7 10-7=3
如果打包成1,2,4,8的话有15种,多了
则只需10-7即可算出最后一种打包数
1,2,4可以凑出0~7
再多一个3即可凑出1~10中任意一个
C++ 代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
struct node{
int w;//体积
int v;//价值
};
const int N=2005; // 要比1005大,拆分打包后的数据范围
int dp[N]; // dp滚动数组
int cnt=0; // 标记vector中有几个数据,用于后面01背包的循环
int main()
{
vector<node>goods; // vector用来存打包后的物品的w,v
int n,c;
cin >> n >> c; // 物品数量和背包大小
for(int i=1;i<=n;i++){
int v,w,s;
cin >> w >> v >> s; // 重量、价值和每种物品的数量
//二进制打包物品
for(int k=1;k<=s;k=k*2){
s=s-k;
goods.push_back({w*k,v*k});
cnt++;
}
if(s>0){
goods.push_back({w*s,v*s});
cnt++;
}
}
//转化为01背包 (滚动数组)
for(int i=0;i<cnt;i++){
for(int j=c;j>=goods[i].w;j--){
dp[j]=max(dp[j],dp[j-goods[i].w]+goods[i].v);
}
}
cout << dp[c] << endl;
return 0;
}
01背包模板
算法一(滚动数组)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e3+5;
struct node{
int w;
int v;
}a[N];
int n,c;
int dp[N];
int main()
{
cin >> n >> c;
for(int i=1;i<=n;i++){
cin >> a[i].w >> a[i].v;
}
for(int i=1;i<=n;i++){
for(int j=c;j>=a[i].w;j--){ // 从后往前,否则前面的数据更新了,后面的就无法计算了
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v); // 选还是不选的最大价值
}
}
cout << dp[c] << endl;
return 0;
}
算法二(二维数组)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e3+5;
struct node{
int w;
int v;
}a[N];
int n,c;
int dp[N][N];
int main()
{
cin >> n >> c;
for(int i=1;i<=n;i++){
cin >> a[i].w >> a[i].v;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=c;j++){
if(a[i].w>j){//第i个物品太大装不下
dp[i][j]=dp[i-1][j];
}
else{//装得下
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].w]+a[i].v);
}
}
}
cout << dp[n][c] << endl;
return 0;
}