题目描述
有 N种物品和一个容量是V 的背包。
第 i 种物品最多有 s[i] 件,每件体积是 v[i],价值是 w[i]。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N行,每行三个整数 v[i],w[i],s[i],用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100
样例
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
我们来连接上文(强烈建议同志们先去看看背包问题1)
根据我们01背包问题引出的动态规划问题思路,先画出我们的“耶路撒冷”
由图可知,我们可以看出图片与完全背包问题十分相类似,so,我们先试试看相同的思路来解题。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N][N];
int w[N],v[N],s[N];
int main()
{
int n,m;
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++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
cout<<f[n][m]<<endl;
return 0;
}
讲解一下:根据题目描述,创建二维数组f[i][j],i表示体积,j表示物品类型,我们还是抓住“最后”这一关键字,针对i,分为两种大情况,不选i,或选i,不选的表达式写为f[i-1][j],选i的情况可以细分为选1个,2个.....s[i]个,(注意,我们这里的可选物品的最大数目看的是题目本身的条件,而不是和完全背包问题一样,看体积是否大于0),表达式写为f[i-1][j-v[i]k]+w[i]k。(Ps:我们的代码中没有f[i-1][j],因为当k=0时,式子就是f(i-1,j))。
但是,我们能用和完全背包问题一样的优化方法吗,答案是否,若将f(i,j-v)展开,因为不是根据体积判断个数的,所以会比完全背包问题多出来一个 。
我们引入一种新的优化方法:打包
我们看一组数据
我们可以根据这组有规律的数字得到任意一个数
假设s=200,我们可以把按之前的规律它分为相似的数据直到64,再加上它的最小大于0的余数73。如此一来,比将200分为1,2,3......200方便很多 。
这便是我们的优化方式,代码如下:
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int f[N];
int n,m;
int v[N],w[N];
int main()
{
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(k<=s)
{
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
if(s>0)
{
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
n=cnt;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[m]<<endl;
return 0;
}
我们将每个数据都按上面的规则分成一块一块的,不但分进v[cnt],w[cnt]中_,注意,此时的下表已经和表示物品种类的i没有关系,cnt仅仅作为计数作用不断扩大_。由此,我们减少的循环次数,节省了时间。