题目链接:点击进入
题目分析:
简单的组合背包模板题,但是递推的同时要刷新这种情况使用了哪些物品
ac代码:
#include<bits/stdc++.h>
using namespace std;
int weigh[],zhu[],t[];
struct student
{
int s;
int number;
int a[];
}f[][];
int main()
{
std::ios::sync_with_stdio(false);
int m,v,n;//m总重量，v总阻力，n物品数
cin>>m>>v>>n;
for(int i=;i<=n;i++)
{
cin>>weigh[i]>>zhu[i]>>t[i];//weigh个体重量，zhu个体阻力,t个体价值
}
for(int i=;i<=n;i++)
for(int mi=m;mi>=weigh[i];mi--)
for(int vi=v;vi>=zhu[i];vi--)
{
//printf("\nnumber=%d\n",f[0][0].number);
if(f[mi][vi].s<f[mi-weigh[i]][vi-zhu[i]].s+t[i])
{
f[mi][vi].s=f[mi-weigh[i]][vi-zhu[i]].s+t[i];
if(f[mi-weigh[i]][vi-zhu[i]].number==)
{
f[mi][vi].a[]=i;
f[mi][vi].number=;
}
else
{
for(int x=;x<=f[mi-weigh[i]][vi-zhu[i]].number;x++)
{
f[mi][vi].a[x]=f[mi-weigh[i]][vi-zhu[i]].a[x];
}
f[mi][vi].number=f[mi-weigh[i]][vi-zhu[i]].number+;
f[mi][vi].a[f[mi][vi].number]=i;
}
}
}
int maxn=f[m][v].s,last_i=m,last_j=v;
printf("%d\n",maxn);
for(int i=m;i>=;i--)
for(int j=v;j>=;j--)
{
if(f[i][j].s!=maxn&&f[last_i][last_j].s==maxn)
{
for(int x=;x<=f[last_i][last_j].number;x++)
{
printf("%d ",f[last_i][last_j].a[x]);
}
//printf("%d",f[last_i][last_j].number);
return ;
}
last_i=i;last_j=j;
}
return ;
}
然后最后在找到相同时间下使用的最少物品情况就好了
对于f数组可以用结构体存,这样更方便,顶多不好写,可是思路清晰
我对于当前已经存了多少个数是从一开始记,所以用了if,else的分类讨论,防止出查错