gryql @ 2015-08-10 10:55:26
程序上有注解，应该比较好理解
var a,b:array[1..60,0..2] of longint;
//b[i,j]表示i的第j个孩子的重要性；a[i,j]表示i的第j个孩子的价值；a[i,0],b[i,0]表示的是自身;
v:array[1..60] of boolean;//是不是主件
f:array[-1000000..1000000] of longint;
n,m,i,x,y,z,j:longint;
function max(q,w,e,r,t:longint):longint;
begin
max:=0;
if q>max then max:=q;
if w>max then max:=w;
if e>max then max:=e;
if r>max then max:=r;
if t>max then max:=t;
end;
begin
readln(n,m);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(f,sizeof(f),0);
fillchar(v,sizeof(v),false);
for i:=1 to m do
begin
readln(x,y,z);
if z=0 then
begin
v[i]:=true;
a[i,0]:=x;
b[i,0]:=y;
continue;
end;
if z<>0 then
begin
if a[z,1]=0 then
begin
a[z,1]:=x;
b[z,1]:=y;
continue;
end;
if a[z,2]=0 then
begin
a[z,2]:=x;
b[z,2]:=y;
end;
end;
end;
for i:=1 to m do
if v[i] then
for j:=n downto a[i,0]+a[i,1]+a[i,2] do
f[j]:=max(
f[j],//不取
f[j-a[i,0]]+a[i,0]*b[i,0],//只取主件
f[j-a[i,0]-a[i,1]]+a[i,0]*b[i,0]+a[i,1]*b[i,1],//只取附件1
f[j-a[i,0]-a[i,2]]+a[i,0]*b[i,0]+a[i,2]*b[i,2],//只取附件2
f[j-a[i,0]-a[i,2]-a[i,1]]+a[i,0]*b[i,0]+a[i,2]*b[i,2]+a[i,1]*b[i,1]//全取
);
writeln(f[n]);
end.by gryql @ 2015-08-10 11:15:58
已解决，并发题解
by _bestknife @ 2015-09-04 17:23:35
#include<stdio.h>
#include<stdlib.h>
int n,m,w[61],d[61],r[61],f[32001],k,i,j;
struct node
{
int l,r;
node()
{
l=0;
r=0;
}
}s[61];
int max(int a,int b)
{
if(a>b)return a;else return b;
}
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&w[i],&k,&j);
d[i]=w[i]*k;
r[i]=j;
if(s[j].l==0)s[j].l=i;
else
if(s[j].r==0)s[j].r=i;
}
for(i=1;i<=m;i++)
for(j=n;j>=w[i];j--)
if(r[i]==0)
{
f[j]=max(f[j],f[j-w[i]]+d[i]);
if(s[i].l!=0)
{
if(j-w[i]-w[s[i].l]>=0)f[j]=max(f[j],f[j-w[i]-w[s[i].l]]+d[i]+d[s[i].l]);
}
if(s[i].r!=0)
{
if(j-w[i]-w[s[i].r]>=0)f[j]=max(f[j],f[j-w[i]-w[s[i].r]]+d[i]+d[s[i].r]);
}
if(j-w[i]-w[s[i].l]-w[s[i].r]>=0)f[j]=max(f[j],f[j-w[i]-w[s[i].r]-w[s[i].l]]+d[s[i].l]+d[i]+d[s[i].r]);
}
printf("%d",f[n]);
return 0;
}