讨论 / 就是01背包的一个扩展
360736293 2018-05-14 17:31:53
点我顶贴 收藏 删除
此方法再输入数值应该注意一点,将属于某主件的附件放到该主件的后面(可以不用紧挨)

比如样例的

800 2 0

400 5 1

300 5 1

而不能这样输入

400 5 1

800 2 0

300 5 1

或者别的,但是此法成功AC,算是巧了,巧了人家给的例子输入都按这种格式

#include<stdio.h>

#define max(a,b) (a>b?a:b)

int main()//由题知道最多两个附件

{

int n,m,i,j,k;

int k1=0,k2=0;

int t1=0,t2=0;

int v[200]={0},p[200]={0},q[200]={0},dp[32005]={0};

scanf("%d %d",&n,&m);

for(i=1;i<=m;i++)

{

scanf("%d %d %d",&v[i],&p[i],&q[i]);

}

for(i=1;i<=m;i++)

{

k1=0;

k2=0;

t1=0;

t2=0;

if(q[i]==0)//确定主件

{

for(k=i+1;k<=m;k++)//找到附件1

{

if(q[k]==i)

{

t1=k;

k1=1;

break;

}

}

for(k=t1+1;k<=m;k++)//找到附件2

{

if(q[k]==i)

{

t2=k;

k2=1;

break;

}

}

for (j = n; j >= v[i]; j--) //遍历找出价值最大

{

dp[j] = max(dp[j - v[i]] + v[i] * p[i], dp[j]);//放主

//如果存在附件,比较放不放附件的价值

if (j-v[i]-v[t1]>=0 && k1==1)//放附1

dp[j] = max(dp[j - v[i]-v[t1]] + v[i] * p[i]+v[t1]*p[t1],dp[j]);

if (j - v[i] - v[t2] >= 0 && k2 == 1)//放附2

dp[j] = max(dp[j - v[i] - v[t2]] + v[i] * p[i] + v[t2] * p[t2], dp[j]);

if (j - v[i] - v[t1] - v[t2] >= 0 && k1 == 1 && k2 == 1)//都放

dp[j] = max(dp[j - v[i] - v[t1]-v[t2]] + v[i] * p[i] + v[t1] * p[t1] + v[t2] * p[t2], dp[j]);

}

}

}

printf("%d",dp[n]);

return 0;

}

#1 fnoichzhe@2018-05-27 16:08:42
回复 删除
重复背包而已
查看更多回复
提交回复