正确结果应为:7430
测试结果4: 测试结果错误.错误结果为:16100
正确结果应为:16700
测试结果5: 测试结果错误.错误结果为:23700
正确结果应为:26400
测试结果6: 测试结果错误.错误结果为:33190
正确结果应为:36400
测试结果7: 测试结果错误.错误结果为:52190
正确结果应为:59350
测试结果8: 测试结果错误.错误结果为:72500
正确结果应为:75800
测试结果9: 测试结果错误.错误结果为:89400
正确结果应为:96000
测试结果10: 测试结果错误.错误结果为:109500
正确结果应为:120800
提交代码：
#include"stdio.h"
#define max(a,b)((a)>(b)?(a):(b))
int dp[3201]={0},n,m;
struct cs
{
int num;
int v[5];
int p[5];
}a[61];
main()
{
int i=0,j=0,k=0,k1;
int qq,ww,ee;
scanf("%d%d",&n,&m);
n/=10;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&qq,&ww,&ee);
qq/=10;
ww=qq*ww;
if(ee==0)
{
k++;
a[k].num=1;
a[k].v[1]=qq;
a[k].p[1]=ww;
}
else
{
a[ee].num++;
a[ee].v[a[ee].num]=qq+a[ee].v[1];
a[ee].p[a[ee].num]=ww+a[ee].p[1];
}
}
for(i=1;i<=k;i++)
{
if(a[i].num==3)
{
a[i].num=4;
a[i].v[4]=a[i].v[2]+a[i].v[3]-a[i].v[1];
a[i].p[4]=a[i].p[2]+a[i].p[3]-a[i].p[1];
}
} /* 以上是压缩分组 测试过 貌似没什么错误*/
for(i=1;i<=k;i++)
for(j=n;j>=0;j--)
for(k1=1;k1<=a[i].num;k1++)
if(a[i].v[k1]<=j)
dp[j]=max(dp[j],dp[j-a[i].v[k1]]+a[i].p[k1]);
printf("%d",dp[n]*10);
}
一直不知道原因，很纠结 有好心的童鞋 帮我指正一下错误 在此谢过
#include <stdio.h>
long V ; //总钱数
int M ; //要购买的物品个数
struct ing
{
int m; //物品个数
int number; //此主件出现的序号 用来使附件找到主件
int c[5]; //每个物品的价值
int w[5]; //每个物品的代价
}a[61];
int h=0; //主件个数 也就是物品组个数
long best[61][3201]; //这里可以用滚动数组 把best数组的空间复杂度降到2*V
int max2( long a , long b ) //2个数求最大
{
if( a>b )return a;
return b;
}
int max3( long a , long b , long c ) //3个数求最大
{
if( a>=b && a>=c )return a;
if( b>=a && b>=c )return b;
if( c>=a && c>=b )return c;
}
int main()
{
int vv,cc,num;
long i,j,x;
// 初始化
for( i=0 ; i<=60 ; i++ )
for( j=0 ; j<=3200 ; j++ )
best[i][j]=0;
scanf( "%ld %d" , &V , &M );
V/=10;
// 输入数据
for( i=1 ; i<=M ; i++ )
{
scanf( "%d %d %d" , &vv , &cc , &num );
if( num==0 ) //遇到主件
{
h++;
a[h].m=1;
a[h].number=i;
a[h].c[1]=vv*cc/10;
a[h].w[1]=vv/10;
}
else //遇到附件
{
for( j=1 ; j<=h ; j++ )
if( num==a[j].number ) //确定是哪个主件的附件
{
a[j].m++;
a[j].c[a[j].m]=vv*cc/10+a[j].c[1];
a[j].w[a[j].m]=vv/10+a[j].w[1];
break;
}
}
}
// 当一个主件有2个附件时 生成第4个物品 为主件与两个附件的和
for( i=1 ; i<=h ; i++ )
if( a[i].m==3 )
{
a[i].m++;
a[i].c[4]=a[i].c[2]+a[i].c[3]-a[i].c[1];
a[i].w[4]=a[i].w[2]+a[i].w[3]-a[i].w[1];
}
// DP主过程
for( i=1 ; i<=h ; i++ ) //所有的组数 h
for( j=1 ; j<=a[i].m ; j++ ) //每个组里的物品数 a[].m
for( x=V ; x>=0 ; x-- ) //倒序 求解每个best[] 这里与0/1背包一样
if( x>=a[i].w[j] ) best[i][x]=max3( best[i][x] , best[i-1][x] , best[i-1][x-a[i].w[j]]+a[i].c[j] );
else best[i][x]=max2( best[i-1][x] , best[i][x] );
// 输出
printf( "%ld" , best[h][V]*10 );
//system("pause");
return 0;
}