首页 > 代码库 > POJ 1015 Jury Compromise 2个月后重做,其实这是背包题目
POJ 1015 Jury Compromise 2个月后重做,其实这是背包题目
http://poj.org/problem?id=1015
题目大意:在遥远的国家佛罗布尼亚,嫌犯是否有罪,须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人,然后再从这n个人中选m人组成陪审团。选m人的办法是:控方和辩方会根据对候选人的喜欢程度,给所有候选人打分,分值从0到20。为了公平起见,法官选出陪审团的原则是:选出的m个人,必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同,那么选辩控双方总分之和最大的方案即可。
其实学DP首先要从背包开始,学了背包后,看这题就是一个背包 + 记录路径的问题
设dp[m][k] = max表示,选了m个数,产生的和差值是k的时候,的最大和值。
但是,这个背包是不能记录路径的,
因为
2 2
1 2
3 4
这组数据,生成和差值是-1的时候有两个,这样会存在路径覆盖问题。
所以要这样做,暴力枚举m组,对于每一次,都在1---n中选一个,然后选的时候看看是否存在于这条路径就行了。
也就是对于上面的数据,一开始选解出选出1个的时候的最优值,那自然是选第二个数,然后,再解出选出两个数的时候的最优解。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> int n, m; const int fix = 20; const int maxn = 200 + 20; struct node { int b, c, dis, sum; }a[maxn]; const int up = 40 * 20 + 20; struct DP { int is, pre; int id, val; }dp[20 + 20][up]; set<int>ans; bool in(int go, int val, int cmp) { while (go > 0) { if (dp[go][val].is == -1) return false; if (dp[go][val].id == cmp) return true; val = dp[go][val].pre; assert(val <= up); assert(val >= 0); go--; } return false; } void work() { // init(); for (int i = 1; i <= n; ++i) { scanf("%d%d", &a[i].b, &a[i].c); a[i].dis = a[i].b - a[i].c + fix; a[i].sum = a[i].b + a[i].c; } memset(dp, -1, sizeof dp); dp[0][0].id = inf, dp[0][0].is = 0, dp[0][0].pre = inf, dp[0][0].val = 0; for (int i = 1; i <= m; ++i) { //选m个 for (int j = 1; j <= n; ++j) { for (int k = a[j].dis; k <= up - 20; ++k) { if (dp[i - 1][k - a[j].dis].is == -1) continue; if (dp[i][k].val < dp[i - 1][k - a[j].dis].val + a[j].sum && !in(i - 1, k - a[j].dis, j)) { // if (dp[i][k].id == j) continue; dp[i][k].val = dp[i - 1][k - a[j].dis].val + a[j].sum; dp[i][k].is = 0; dp[i][k].id = j; dp[i][k].pre = k - a[j].dis; } } } } int p1 = m * fix, p2 = m * fix; int id1 = -inf, id2 = -inf, idans = -inf; while (true) { if (dp[m][p1].is != -1) id1 = p1; if (dp[m][p2].is != -1) id2 = p2; if (id1 != -inf && id2 == -inf) { idans = id1; break; } else if (id1 == -inf && id2 != -inf) { idans = id2; break; } else if (id1 != -inf && id2 != -inf) { if (dp[m][id1].val > dp[m][id2].val) { idans = id1; } else idans = id2; break; } p1--; p2++; } // cout << idans << endl; ans.clear(); int go = m; while (dp[go][idans].id != inf) { assert(dp[go][idans].is != -1); ans.insert(dp[go][idans].id); idans = dp[go][idans].pre; go--; } static int f = 0; printf("Jury #%d\n", ++f); int ans1 = 0, ans2 = 0; for (set<int> :: iterator it = ans.begin(); it != ans.end(); ++it) { ans1 += a[*it].b; ans2 += a[*it].c; } // cout << endl; printf("Best jury has value %d for prosecution and value %d for defence:\n", ans1, ans2); for (set<int> :: iterator it = ans.begin(); it != ans.end(); ++it) { cout << " " << *it; } cout << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d%d", &n, &m) != EOF && (n + m)) { work(); printf("\n"); } return 0; }
POJ 1015 Jury Compromise 2个月后重做,其实这是背包题目
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。