题目描述
经典的多重背包问题
算法1
(朴素的做法) $O(n^2)$
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int f[maxn][maxn];
int v[maxn];
int w[maxn];
int l[maxn];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i];
cin>>w[i];
cin>>l[i];
}
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
for(int k=0;k*v[i]<=j&&k<=l[i];k++)
{
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
printf("%d\n",f[n][m]);
return 0;
}
算法2
(二进制优化) $O(n^2)$
思路:在于将一个整数拆分,任何一个整数,可有log(n)个数组合起来
时间复杂度(nnlog(n))
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int dp[maxn];
vector<pair<int,int>> goods;
int main()
{
int n,v;
cin>>n>>v;
for(int i=1;i<=n;i++)
{
int vol,val,s;
scanf("%d%d%d",&vol,&val,&s);
for(int k=1;k<=s;k<<=1){
s-=k;
goods.push_back({k*vol,k*val});
}
if(s>0) goods.push_back({s*vol,s*val});//注意一下这边,边界的判断
}
for(auto good:goods)
{
for(int j=v;j>=good.first;j--)
dp[j]=max(dp[j],dp[j-good.first]+good.second);
}
cout<<dp[v]<<endl;
return 0;
}