POJ 1015 Jury Compromise——01背包变形

POJ 1015 Jury Compromise——01背包变形

​

#include #include #include #include #include using namespace std;const int maxn = 210;int kase, n, m, d, p, add[maxn], sub[maxn], dp[30][maxn<<2];vector path[30][maxn<<2];int main() { while (~scanf("%d %d", &n, &m) && n && m) { for (int i = 1; i <= n; i++) { scanf("%d %d", &d, &p); add[i] = d + p, sub[i] = d - p; } int fix = 20 * m; memset(dp, -1, sizeof(dp)); dp[0][fix] = 0; for (int i = 1; i <= n; i++) { for (int j = m; j >= 1; j--) { for (int k = 0; k < 2 * fix; k++) { if (0 > k + sub[i] || k + sub[i] > 2 * fix) continue; if (dp[j - 1][k] == -1) continue; if (dp[j][k+sub[i]] < dp[j - 1][k] + add[i]) { dp[j][k+sub[i]] = dp[j - 1][k] + add[i]; path[j][k+sub[i]] = path[j - 1][k]; path[j][k+sub[i]].push_back(i); } } } } int ans = 0; while (dp[m][fix - ans] == -1 && dp[m][fix + ans] == -1) ans++; int temp = (dp[m][fix + ans] > dp[m][fix - ans]) ? fix + ans : fix - ans; printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n", ++kase, (dp[m][temp] + temp - fix) / 2, (dp[m][temp] - temp + fix) / 2); for (int i = 0; i < m; i++) { printf(" %d", path[m][temp][i]); } printf("\n\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。