讨论 / 重复背包的经典题型
fnoichzhe 2018-05-27 16:15:34
点我顶贴 收藏 删除
其实jiushi01背包的拓展而已!

不过还是很难。

#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++){

if(q[k]==i){

t1=k;

k1=1;

break;

}

}

for(k=t1+1;k<=m;k++){

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) 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) 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;

}

查看更多回复
提交回复