Ouaoan @ 2016-06-30 17:30:39
#include<stdio.h>
#include<iostream>
using namespace std;
int m,n,s=0;
int w[61]= {0},c[61]= {0};
int a[61][4]= {0},b[61]= {0};
int f[32002]= {0};
int ji[3]= {0};
int main() {
int i,j,k;
cin>>m>>n;
for(i=1; i<=n; i++) { //输入,变形
int q;
cin>>w[i]>>c[i]>>q;
c[i]*=w[i];
if(q==0) {
s++;
b[s]=i;
} else {
a[q][0]++;
a[q][a[q][0]]=i;
}
}
cout<<"\n-----------\n\n";
for(i=1; i<=n; i++) {
cout<<w[i]<<' '<<c[i]<<endl;
}
cout<<"\n-----------\n\n";
for(i=1; i<=s; i++) {
cout<<b[i]<<' ';
for(j=1; j<=a[i][0]; j++) {
cout<<a[i][j]<<' ';
}
cout<<endl;
}
cout<<"\n-----------\n\n";
getchar();
for(i=1; i<=s; i++) {
for(j=m; j>=10; j-=10) {
int tmp1=a[i][1],tmp2=a[i][2];
if(j>=w[b[i]])
f[j]=max(f[j],f[j-w[b[i]]]+c[b[i]]);
if(j>=w[b[i]]+w[tmp1])
f[j]=max(f[j],f[j-w[b[i]]-w[tmp1]]+c[tmp1]+c[b[i]]);
if(j>=w[b[i]]+w[tmp2])
f[j]=max(f[j],f[j-w[b[i]]-w[tmp2]]+c[tmp2]+c[b[i]]);
if(j>=w[b[i]]+w[tmp1]+w[tmp2])
f[j]=max(f[j],f[j-w[b[i]]-w[tmp1]-w[tmp2]]+c[tmp1]+c[tmp2]+c[b[i]]);
printf("%5d",f[j]);
}
cout<<endl;
getchar();
}
cout<<f[m];
return 0;
}
/* 10 5 8 2 0 4 5 1 3 5 1 4 3 0 5 2 0
10 6 8 2 0 4 5 1 3 5 1 4 3 0 1 3 2 5 2 0
200 10 50 1 0 40 4 0 30 5 1 40 5 1 20 5 0 50 4 5 40 4 0 32 2 0 41 3 0 40 3 5
1000 5 500 4 2
400 4 0
320 2 0
410 3 0
400 3 2
*/
by joyemang33 @ 2016-06-30 22:56:00
数组可以开大一点