问题 A(1135): 【基础算法】0-1背包问题
时间限制:1 Sec 内存限制:64 MB提交:777 解决:211
题目描述
有 n 件物品, 每件物品有一个价值和一个重量，分别记为： b1,b2, …bn w1,w2, …wn 其中所有的 重量wi 均为整数。 现有一个背包，其最大载重量为W，要求从这n件物品中任取若干件（这些物品要么被装入要么被留下）。问背包中装入哪些物品可使得所装物品的价值和最大？
输入
第1行：2个整数n(1<=n<=1000)和W(1<=W<=10000)，分别表示物品的件数和背包的最大载重量。
第2-n+1行：每行2个用空格分开的整数，第i+1行的整数表示第i件物品的重量wi和价值bi(1<=bi,wi<=10000)。
输出
第1行：1个整数，表示背包所能装下的物品的最大总价值。
第2-？行：每行3个用空格分开的整数，i, wi, bi，分别表示最优解中的物品的编号、重量和价值。
样例输入
(如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)
4 5
2 3
3 4
4 5
5 6
样例输出
7
1 2 3
2 3 4
要看分析就去采药里看吧，这道题与采药唯一的不同点就是采药不输出方案，而这道题要。
————————————————分析———————————————————
如果要输出方案，那么我们就要另开一个数组。
假设我们已经求出来了能装下物品的最大总值(再申明一遍，没有看过采药的童鞋戳我查看)，那么假设我们开了一个path数组。f[i][j]=f[i-1][j],那么就说明
f[i-1][j]没有用，所以我们标记一下。按照如此下去，就可以表示出所有装了的物品。
-----------------------------代码实现----------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node
{
int w,v;
}a[1005];
int n,W,f[1005][10005],path[1005];
void huisu(int i,int j)
{
if(i>0)
{
if(f[i][j]==f[i-1][j])
{path[i]=0;huisu(i-1,j);
}
else
if(j>=a[i].w&&f[i][j]==f[i-1][j-a[i].w]+a[i].v)
{
path[i]=1;
huisu(i-1,j-a[i].w);
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&W);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].w,&a[i].v);
for(int i=1;i<=n;i++)
{
memcpy(f[i],f[i-1],sizeof(f[i]));
for(int j=a[i].w;j<=W;j++)
f[i][j]=max(f[i-1][j],f[i-1][j-a[i].w]+a[i].v);
}
printf("%d\n",f[n][W]);
huisu(n,W);
for(int i=1;i<=n;i++)
if(path[i]==1)
printf("%d %d %d\n",i,a[i].w,a[i].v);
return 0;
}