poj 2184 Cow Exhibition 01背包

太过爱你忘了你带给我的痛 2022-05-17 00:38 140阅读 0赞

题目链接：[传送门][Link 1]

借鉴：http://www.cnblogs.com/andre0506/archive/2012/09/19/2694148.html  
用聪明值作为背包空间，另一个作为价值，但是空间不能为负数，只好将他全部加1000  
开一个数组记录一下最大值用了多少1000

#include<iostream>
    #include<sstream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    const int maxn =200010;
    using namespace std;
    const int INF =10000000;
    int a[105],b[105],sum;
    int dp[maxn],cnt[maxn];
    int main(){
    	int n;
    	while(scanf("%d",&n)!=EOF){
    		sum=0;
    		for(int i=0;i<n;i++){
    			scanf("%d %d",&a[i],&b[i]);
    			if(a[i]<=0&&b[i]<=0){
    				i--;n--;
    				continue;
    			}
    			a[i]+=1000;
    			sum+=a[i];//确保最大背包容量 
    		}
    		
    		for(int i=1;i<=sum;i++){
    			dp[i]=-INF;
    		}
            dp[0] = 0;//确保每种体积的背包都能够被装满 
            memset(cnt, 0, sizeof(cnt));
    		for(int i=0;i<n;i++){
    			for(int j=sum;j>=a[i];j--){
    				if(dp[j-a[i]]+b[i]-(cnt[j-a[i]]+1)*1000>dp[j]-cnt[j]*1000){
    					dp[j]=dp[j-a[i]]+b[i];
    					cnt[j]=cnt[j-a[i]]+1;
    				}
    			}
    		}
    		
    		int ans=0;
    		for(int i=0;i<=sum;i++){
    			if(i-cnt[i]*1000>=0&&dp[i]>=0){
    				ans=max(ans,dp[i]+i-cnt[i]*1000);
    			}
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[Link 1]: http://poj.org/problem?id=2184

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3624 （01背包一维求解）

Charm Bracelet <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000

左手的ㄟ右手/ 2024年02月17日 19:31/ 0 赞/ 62 阅读

相关 poj 3348 Cows

> 题目衔接：[http://poj.org/problem?id=3348][http_poj.org_problem_id_3348] > <table> > <tb

Bertha 。/ 2023年10月09日 12:40/ 0 赞/ 88 阅读

相关 poj 2484 Cow Exhibition 【变形0-1背包】

题目：[poj 2484 Cow Exhibition][] 题意：给出n头牛，每头牛有一个幸运值 si 和聪明值 ti ，现在要选出一些牛，让两个值的和最大，前提

妖狐艹你老母/ 2022年08月13日 13:50/ 0 赞/ 33 阅读

相关 pku 2184 Cow Exhibition

\include <iostream> using namespace std; \define BASE 100050 int c\[200100\]; bool flag\

r囧r小猫/ 2022年08月13日 12:56/ 0 赞/ 14 阅读

相关 POJ 1837-Balance（01背包-天平平衡）

Balance <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

朱雀/ 2022年07月12日 04:06/ 0 赞/ 155 阅读

相关 01背包变形 POJ - 2184 

"Fat and docile, big and dumb, they look so stupid, they aren't much fun..." \- C

野性酷女/ 2022年06月17日 09:26/ 0 赞/ 198 阅读

相关 01背包问题 poj 3624

理解01背包问题，首先要从二维数组的开始。二维数组的理解之后，优化成为一维，就是轻而易举的事了。 01背包动态规划的转移公式：当考虑第i件物品的时候，背包能装得下的话

落日映苍穹つ/ 2022年06月13日 10:50/ 0 赞/ 146 阅读

相关 POJ 3624 Charm Bracelet【01背包】

Charm Bracelet 题目链接：[https://vjudge.net/contest/209202\problem/L][https_vjudge.net_c

末蓝、/ 2022年06月01日 10:14/ 0 赞/ 126 阅读

相关 poj 2184 Cow Exhibition 01背包

题目链接：[传送门][Link 1] 借鉴：http://www.cnblogs.com/andre0506/archive/2012/09/19/2694148.html

太过爱你忘了你带给我的痛/ 2022年05月17日 00:38/ 0 赞/ 141 阅读

相关 POJ—— 3624 Charm Bracelet（01背包）

题目链接：[http://poj.org/problem?id=3624][http_poj.org_problem_id_3624] 题目： Charm

红太狼/ 2021年09月26日 11:36/ 0 赞/ 230 阅读