lokiii @ 2017-04-09 11:46:29
我想的是把 只取主,取主和附1,取主和附2,取主和附1附2各作为一个商品存在b里,b【】。a为价值乘价格,b【】。b为价格,这一步核对过了没有错
但是我01背包出来的结果价格总和大于额定价格是为什么QAQ
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct base
{
int v,p,q,f1,f2;
}a[61];
struct wu
{
int a,b; //v*p v
}b[200];
int main()
{
int n,m,j=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
if(a[i].q>=0)
{
if(a[a[i].q].f1==0)
a[a[i].q].f1=i;
else
a[a[i].q].f2=i;
}
}
for(int i=1;i<=m;i++)
{
if(a[i].q==0)
{
if(a[i].f1==0)
{
b[j].a=a[i].v*a[i].p/10;
b[j].b=a[i].v/10;
j++;
}
else if(a[i].f2==0)
{
b[j].a=a[i].v*a[i].p/10;
b[j].b=a[i].v/10;
j++;
b[j].a=(a[i].v*a[i].p+a[a[i].f1].v*a[a[i].f1].p)/10;
b[j].b=(a[i].v+a[a[i].f1].v)/10;
j++;
}
else
{
b[j].a=a[i].v*a[i].p/10;
b[j].b=a[i].v/10;
j++;
b[j].a=(a[i].v*a[i].p+a[a[i].f1].v*a[a[i].f1].p)/10;
b[j].b=(a[i].v+a[a[i].f1].v)/10;
j++;
b[j].a=(a[i].v*a[i].p+a[a[i].f2].v*a[a[i].f2].p)/10;
b[j].b=(a[i].v+a[a[i].f2].v)/10;
j++;
b[j].a=(a[i].v*a[i].p+a[a[i].f1].v*a[a[i].f1].p+a[a[i].f2].v*a[a[i].f2].p)/10;
b[j].b=(a[i].v+a[a[i].f1].v+a[a[i].f2].v)/10;
j++;
}
}
}
for(int i=1;i<j;i++)
printf("%d %d\n",b[i].a,b[i].b);
int con=j-1,d[61][3200]={0};
n=n/10;
for(int i=1;i<=con;i++)
for(int j=b[i].b;j<=n;j++)//在这里,背包放入物品后,容量不断的减少,直到再也放不进了
{
d[i][j]=(i==1?0:d[i-1][j]);
if(j>=b[i].b)
{
d[i][j]=max(d[i][j],d[i-1][j-b[i].b]+b[i].a);//no,put
}
//if(d[i][j]==d[i-1][j-b[i].b]+b[i].a)
//printf("%d %d ",d[i][j],i);
}
printf("%d",d[con][n]*10);
return 0;
}
by BFSBFSBFSBFS @ 2017-04-30 15:59:08
@木落汐loki 因为背包可能取完主+附1又取了主+附2......
by lokiii @ 2017-04-30 21:02:58
Σ(っ °Д °;)っ说的有道理!是我死心眼了。。。谢谢大神!@ BFSBFSBFSBFS