背包问题求方案和费用
作者:
骏杰
,
2022-05-11 09:26:57
,
所有人可见
,
阅读 127
二维费用的背包问题:
有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。
#include <iostream>
#include <iostream>
using namespace std;
const int N=1010;
int f[N][N];
int main()
{
int n,V,M;
cin>>n>>V>>M;
for(int i=0;i<n;i++)
{
int v,m,w;
cin>>v>>m>>w;
for(int j=V;j>=v;j--)
{
for(int k=M;k>=m;k--)
{
f[j][k]=max(f[j][k],f[j-v][k-m]+w);
}
}
}
cout<<f[V][M]<<endl;
}
背包问题求方案数:
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出 最优选法的方案数
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1010,INF=1e9+7;
int f[N];
int n,m;
int g[N];
int main()
{
cin>>n>>m;
memset(f,-0x3f,sizeof f);
f[0]=0;
g[0]=1;
for(int i=0;i<n;i++)
{
int v,w;
cin>>v>>w;
for(int j=m;j>=v;j--)
{
int maxv=max(f[j],f[j-v]+w);
int cnt=0;
if(f[j]==maxv) cnt+=g[j];
if(f[j-v]+w==maxv) cnt+=g[j-v];
g[j]=cnt%INF;
f[j]=maxv;
}
}
int res=0;
for(int i=0;i<=m;i++)
{
res=max(res,f[i]);
}
int cnt=0;
for(int i=0;i<=m;i++)
{
if(res==f[i])
{
cnt=(cnt+g[i])%INF;
}
}
cout<<cnt<<endl;
}
背包问题求具体方案:
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出 字典序最小的方案
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int f[N][N];//要求方案,要用二维数组储存方案
int w[N],v[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=n;i>=1;i--)//类似于最短路径,从后(n)往前推,判断选没选i
{
for(int j=m;j>=0;j--)//二维,可前可后
{
f[i][j]=f[i+1][j];//注意:i+1:从后往前推
if(j>=v[i])
{
f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
}
}
}
//int j=m;可加,f[i][m]储存最大容量方案,后面就可以f[i][j];
for(int i=1;i<=n;i++)
{
if(m>=v[i]&&f[i][m]==f[i+1][m-v[i]]+w[i])//题中问字典序,例如123<31,从第一位向后比较。假如可选1可不选,选了最好,1就小
{
cout<<i<<" ";
m-=v[i];
}
}
return 0;
}