-
多重背包问题Ⅰ
原题链接
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
数据范围:
0< N , V ≤100
0< vi , wi , si ≤100
//朴素版多重背包问题≈朴素版完全背包问题,只不过加了物品数量的限定条件
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int n,m;
int s[N],w[N],v[N];
int dp[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<dp[n][m]<<endl;
return 0;
}
-
多重背包问题Ⅱ
原题链接
数据范围:
0< N ≤1000
0< V ≤2000
0< vi , wi , si ≤2000
最主要的思想是二进制优化,把问题转化为01背包问题
int k=1;
while(k<=s)//类似于将s[i]=16,拆成一堆二进制后1 2 4 8 1,与体积,质量乘积打包成一份一份
{
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
//如果s[i]没用连续的二进制打包完
if(s>0)
{
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
n=cnt;//这是新的物品数量
优化成简短点的代码
for(int i=0;i<n;i++)
{
for(int k=1;k<=s;k*=2)//多重背包二进制优化
{
for(int j=m;j>=k*v;j--)
dp[j]=max(dp[j],dp[j-k*v]+k*w);
s-=k;
}
}
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=12010;
int dp[N];
int v[N],w[N];
int n,m;
int main()
{
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
//对每个s[i]二进制打包
int k=1;
while(k<=s)//类似于将s[i]=16,拆成一堆二进制后1 2 4 8 1,与体积,质量乘积打包成一份一份
{
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
//如果s[i]没用连续的二进制打包完
if(s>0)
{
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
n=cnt;//这是新的物品数量
//因为经过上述操作后,每个物品的数量都来变成了1,于是转变成01背包问题,O(nvlogs)
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
cout<<dp[m]<<endl;
return 0;
}
-
分组背包
原题链接
由当前物品的类型去判断属于哪一类背包问题,做出第i号物品在该类背包模型下的最优决策
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+10;
int dp[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
int v,w,s;
cin>>v>>w>>s;
if(s==0)//完全背包
{
for(int j=v;j<=m;j++)
dp[j]=max(dp[j],dp[j-v]+w);
}
else
{
if(s==-1)s=1;//01背包
for(int k=1;k<=s;k*=2)//多重背包二进制优化
{
for(int j=m;j>=k*v;j--)
dp[j]=max(dp[j],dp[j-k*v]+k*w);
s-=k;
}
if(s)//剩余s去做01背包
{
for(int j=m;j>=s*v;j--)
{
dp[j]=max(dp[j],dp[j-s*v]+s*w);
}
}
}
}
cout<<dp[m]<<endl;
return 0;
}
网友评论