囧雪诺 @ 2020-01-19 16:36:26
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct wp{
int p;
int v;
int zt;
}it[65];
int main()
{
int money,item,tem1,tem2,tem3,mone[65][6],monev[65][6],num=0,f[33000],cs[4]={1,2,4},sss[65];
for(int i=1;i<=32100;i++) f[i]=0;
cin>>money>>item;
//money=/10;
for(int i=1;i<=item;i++)
{
cin>>tem1>>tem2>>it[i].zt;
it[i].p=tem1;
it[i].v=it[i].p*tem2;
if(it[i].zt==0)
{
num++;
mone[num][0]=i;
sss[num]=i;
}
}
for(int i=1;i<=num;i++)
{
int fj[5];
tem3=0;
for(int j=1;j<=item;j++)
{
if(i==it[j].zt)
{
tem3++;
fj[tem3]=j;
}
if(tem3>=2||j==item)
mone[i][0]=tem3;
}
if(mone[i][0]==0)
{
mone[i][1]=it[sss[i]].p;
monev[i][1]=it[sss[i]].v;
}
if(mone[i][0]==1)
{
mone[i][1]=it[sss[i]].p;
monev[i][1]=it[sss[i]].v;
mone[i][2]=it[sss[i]].p+it[fj[1]].p;
monev[i][2]=it[sss[i]].v+it[fj[1]].v;
}
if(mone[i][0]==2)
{
mone[i][1]=it[sss[i]].p;
monev[i][1]=it[sss[i]].v;
mone[i][2]=it[sss[i]].p+it[fj[1]].p;
monev[i][2]=it[sss[i]].v+it[fj[1]].v;
mone[i][3]=it[sss[i]].p+it[fj[2]].p;
monev[i][3]=it[sss[i]].v+it[fj[2]].v;
mone[i][4]=it[sss[i]].p+it[fj[1]].p+it[fj[2]].p;
monev[i][4]=it[sss[i]].v+it[fj[1]].v+it[fj[2]].v;
}
}
//以上是把每个主件及其附件录入到数组里进行分组背包,反复检查过没有错误
for(int i=1;i<=num;i++)
{
for(int k=money;k>0;k--)
{
for(int w=1;w<=cs[mone[i][0]];w++)
{
if(k>=mone[i][w])
f[k]=max(f[k],f[k-mone[i][w]]+monev[i][w]);
}
}
}
cout<<f[money];
return 0;
}
这是第3点数据: 2000 10 500 1 0 400 4 0 300 5 1 400 5 1 200 5 0 500 4 5 400 4 0 320 2 0 410 3 0 400 3 5 答案是7430 但是我输出7200 求助aaaa
by xbybshd @ 2020-01-25 23:56:44
主件在第几行,行号减一就是其序号,并不是把附件全部去除之后的序号