这是一道有依赖的背包的经典题目，考虑到每个物品最多有两个子物品，最多会有四种状态，所以可以转化为01背包进行枚举状态
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #define N 3250 4 #define M 65 5 int a[N]; 6 int s[M][4]; 7 int v[M][3]; 8 int max(int a,int b) 9 { 10 return a>b?a:b; 11 } 12 int main() 13 { 14 int n,m; 15 int i,j,k; 16 int f; 17 int pri,sta; 18 while(scanf("%d%d",&n,&m)!=EOF) 19 { 20 memset(s,0,sizeof(s)); 21 memset(v,0,sizeof(v)); 22 memset(a,0,sizeof(a)); 23 int t=1; 24 for(i=1;i<=m;i++) 25 { 26 scanf("%d%d%d",&pri,&sta,&f); 27 pri/=10; 28 if(!f) 29 { 30 s[t][0]=pri; 31 v[t][0]=sta*pri; 32 s[t++][3]=i; 33 } 34 else 35 { 36 for(j=0;j<t;j++) 37 if(s[j][3]==f) 38 break; 39 if(s[j][1]==0) 40 { 41 s[j][1]=pri; 42 v[j][1]=sta*pri; 43 } 44 else 45 { 46 s[j][2]=pri; 47 v[j][2]=sta*pri; 48 } 49 } 50 } 51 n/=10; 52 for(i=1;i<t;i++)//01背包的状态转移 53 for(j=n;j>=s[i][0];j--) 54 { 55 if(j>=s[i][0]) 56 a[j]=max(a[j],a[j-s[i][0]]+v[i][0]); 57 if(j>=s[i][0]+s[i][1]) 58 a[j]=max(a[j],a[j-s[i][0]-s[i][1]]+v[i][0]+v[i][1]); 59 if(j>=s[i][0]+s[i][2]) 60 a[j]=max(a[j],a[j-s[i][0]-s[i][2]]+v[i][0]+v[i][2]); 61 if(j>=s[i][0]+s[i][2]+s[i][1]) 62 a[j]=max(a[j],a[j-s[i][0]-s[i][2]-s[i][1]]+v[i][0]+v[i][2]+v[i][1]); 63 } 64 printf("%d\n",a[n]*10); 65 } 66 return 0; 67 }