首页 > 代码库 > PKU 2184 Cow Exhibition 01背包
PKU 2184 Cow Exhibition 01背包
题意：
有一些牛，每头牛有一个Si值，一个Fi值，选出一些牛，使得max( sum(Si+Fi) ) 并且 sum(Si)>=0, sum(Fi)>=0
思路：
随便选一维做容量(比如Fi)，另一维做价值，然后直接做01背包。
做的时候注意一下方向。
最后，在合法解里面找一下最优解就好了。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <functional>#include <cctype>#include <time.h>using namespace std;typedef pair<int, int> PII;const int INF = 1e6;const int MAXM = 1e5+5;const int MAXN = 111;PII a[MAXN];int dp[MAXM];int n;int main() { #ifdef Phantom01 freopen("PKU2184.txt", "r", stdin); #endif //Phantom01 while (scanf("%d", &n)!=EOF) { int sum = 0; for (int i = 0; i < n; i++) { scanf("%d%d", &a[i].first, &a[i].second); if (a[i].first>0) sum += a[i].first; } sort(a, a+n); for (int i = 0; i <= sum; i++) dp[i] = -INF; dp[0] = 0; for (int i = n-1; i >= 0; i--) { int f = a[i].first, s = a[i].second; if (f<0 && s<0) continue; if (f>=0) { for (int j = sum-f; j >= 0; j--) { dp[j+f] = max(dp[j+f], dp[j]+s); } } else { for (int j = -f; j <= sum; j++) { dp[j+f] = max(dp[j+f], dp[j]+s); } } } int ans = 0; for (int i = 0; i <= sum; i++) if (dp[i]>=0) { ans = max(ans, i+dp[i]); } printf("%d\n", ans); } return 0;}
写的时候又一次为了剪枝，不小心删掉了一些合法解，甚至是最优解，然后wa了两发……真是伤心
PKU 2184 Cow Exhibition 01背包
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。