首页 > 代码库 > Codeforces 336C 0-1背包

Codeforces 336C 0-1背包

题意:每个水果有两个值,一个美味度 a,一个卡路里 b,从中挑选一些,要求 sum(aj) / sum(bj) = k,使得 sum(a) 最大。

分析:没有那个条件就是一个01背包,可以转换,对公式变形,每个水果的重量为 a[i] - b[i] *k ,那么无论怎么挑选,都满足那个条件,价值是 a[i] 

但是,a[i] - b[i] *k 可能为负,那么可以分类讨论,背包容量10000即可,最后枚举背包容量,能够达到的值是两个部分的和。

 

技术分享
#include <bits/stdc++.h>using namespace std;const int maxn = 105;int a[maxn];int b[maxn];int c[maxn];int dp[100000];int pp[100000];int main(){   // freopen("in.txt","r",stdin);    int n,k;    scanf("%d%d",&n,&k);    for(int i=0;i<n;i++)        scanf("%d",&a[i]);    for(int i=0;i<n;i++) {        scanf("%d",&b[i]);        c[i] = a[i] - b[i]*k;    }    memset(dp,-0x3f3f3f3f,sizeof(dp));    memset(pp,-0x3f3f3f3f,sizeof(pp));    dp[0] = pp[0] = 0;    int V = 10000;    for(int i=0;i<n;i++) {        if(c[i]>=0) {            for(int j=V;j>=0;j--) {                if(j>=c[i])                    dp[j] = max(dp[j],dp[j-c[i]]+a[i]);            }        }        else {            c[i]=-c[i];            for(int j=V;j>=0;j--) {                if(j>=c[i]) {                    pp[j] = max(pp[j],pp[j-c[i]]+a[i]);                }            }        }    }    int ans =-1;    for(int i=0;i<=10000;i++) {        ans = max(dp[i]+pp[i],ans);    }    if(ans==0) ans =-1;    printf("%d\n",ans);    return 0;}
View Code

 

Codeforces 336C 0-1背包