金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。
input：
输入文件的第1行，为两个正整数，用一个空格隔开：N m
其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q
(其中v表示该物品的价格(v<10000)，p表示该物品的重要度(1~5)，q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号)
output：
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<200000)。
【参考程序】：
#include<cstring>
#include<cstdio>
using namespace std;
struct node
{
int x;
int v[5],w[5];
} a[70];
int f[100][4000];
int n,m,k;
void dp()
{
memset(f,0,sizeof(f));
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j];
if (j-a[i].v[0]>=0)
{
if (f[i][j]<f[i-1][j-a[i].v[0]]+a[i].w[0])
f[i][j]=f[i-1][j-a[i].v[0]]+a[i].w[0];
}
if (j-a[i].v[0]-a[i].v[1]>=0)
{
if (f[i][j]<f[i-1][j-a[i].v[0]-a[i].v[1]]+a[i].w[0]+a[i].w[1])
f[i][j]=f[i-1][j-a[i].v[0]-a[i].v[1]]+a[i].w[0]+a[i].w[1];
}
if (j-a[i].v[0]-a[i].v[2]>=0)
{
if (f[i][j]<f[i-1][j-a[i].v[0]-a[i].v[2]]+a[i].w[0]+a[i].w[2])
f[i][j]=f[i-1][j-a[i].v[0]-a[i].v[2]]+a[i].w[0]+a[i].w[2];
}
if (j-a[i].v[0]-a[i].v[1]-a[i].v[2]>=0)
{
if (f[i][j]<f[i-1][j-a[i].v[0]-a[i].v[1]-a[i].v[2]]+a[i].w[0]+a[i].w[1]+a[i].w[2])
f[i][j]=f[i-1][j-a[i].v[0]-a[i].v[1]-a[i].v[2]]+a[i].w[0]+a[i].w[1]+a[i].w[2];
}
}
}
int main()
{
for (int i=1;i<=m;i++) a[i].x=0;
scanf("%d%d",&n,&m);
n/=10;
int v1,p1,q1;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&v1,&p1,&q1);
v1/=10;
if (q1==0)
{
a[i].v[0]=v1; a[i].w[0]=p1*v1;
}
else
{
a[q1].x++;
a[q1].v[a[q1].x]=v1;
a[q1].w[a[q1].x]=p1*v1;
}
}
dp();
printf("%d\n",f[m][n]*10);
return 0;
}
【参考程序】：//pascal
type tt=record
money,jia,zong:longint;
end;
var b:array[1..100] of longint;
a:array[1..100,1..3] of tt;
f:array[0..100,0..4000] of longint;
i,j,n,m,c,x,z:longint;
function findmax(a,b,c,d,e:integer):integer;
var max:longint;
begin
max:=a;
if b>max then max:=b;
if c>max then max:=c;
if d>max then max:=d;
if e>max then max:=e;
findmax:=max;
end;
procedure dp;
var i,j,max1,max2,max3,max4,max:longint;
begin
for i:=1 to m do
for j:=1 to n do
begin
max1:=0;max2:=0;max3:=0;max4:=0;
max:=f[i-1,j];
if (j-a[i,1].money)>=0 then
max1:=f[i-1,j-a[i,1].money]+a[i,1].zong;
if (j-a[i,1].money-a[i,2].money)>=0 then
max2:=f[i-1,j-a[i,1].money-a[i,2].money]+a[i,1].zong+a[i,2].zong;
if (j-a[i,1].money-a[i,3].money)>=0 then
max3:=f[i-1,j-a[i,1].money-a[i,3].money]+a[i,1].zong+a[i,3].zong;
if (j-a[i,1].money-a[i,2].money-a[i,3].money)>=0 then
max4:=f[i-1,j-a[i,1].money-a[i,2].money-a[i,3].money]+a[i,1].zong+a[i,2].zong+a[i,3].zong;
f[i,j]:=findmax(max1,max2,max3,max4,max);
end;
end;
begin
//while not eof do
//begin
readln(n,m);
n:=n div 10;
for i:=1 to 60 do
for j:=1 to 3 do
begin
a[i,j].money:=0;
a[i,j].jia:=0;
a[i,j].zong:=0;
end;
for i:=1 to m do b[i]:=1;
fillchar(f,sizeof(f),0);
for i:=1 to m do
begin
readln(z,x,c);
z:=z div 10;
if c=0 then
begin
a[i,1].money:=z;
a[i,1].jia:=x;
a[i,1].zong:=z*x;
end
else
begin
a[c,b[c]+1].money:=z;
a[c,b[c]+1].jia:=x;
a[c,b[c]+1].zong:=z*x;
inc(b[c]);
end;
end;
dp;
writeln(f[m,n]*10);
//end;
end.