UVA - 323 Jury Compromise——01背包

UVA - 323 Jury Compromise——01背包

第二遍做

因为问题有后效性， 所以当前状态不能由前面的状态转移而来，应该用这个状态更新后面的状态

#include #include #include #include #include using namespace std;const int maxn = 205;int flag = 0, n, m, d[maxn], p[maxn], sum[maxn], sub[maxn], dp[25][805];vector path[25][800];int main() { while (~scanf("%d %d", &n, &m) && (n+m)) { for (int i = 1; i <= n; i++) { scanf("%d %d", &d[i], &p[i]); sum[i] = d[i] + p[i]; sub[i] = d[i] - p[i]; } int t = m * 20, v = m * 40; for (int i = 0; i <= m; i++) { for (int j = 0; j <= v; j++) { dp[i][j] = -1; path[i][j].clear(); } } dp[0][t] = 0; for (int k = 1; k <= n; k++) { for (int i = m; i >= 0; i--) { for (int j = 0; j <= v; j++) { if (dp[i][j] < 0 || j + sub[k] < 0 || j + sub[k] > v) continue; if (dp[i + 1][j + sub[k]] < dp[i][j] + sum[k]) { dp[i + 1][j + sub[k]] = dp[i][j] + sum[k]; path[i + 1][j + sub[k]] = path[i][j]; path[i + 1][j + sub[k]].push_back(k); } } } } int pos = 0; while (dp[m][t+pos] < 0 && dp[m][t-pos] < 0) pos++; int state = (dp[m][t+pos] > dp[m][t-pos]) ? t+pos : t-pos; int sumd = 0, sump = 0; for (int i = 0; i < path[m][state].size(); i++) { int index = path[m][state][i]; sumd += d[index], sump += p[index]; } printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n", ++flag, sumd, sump); for (int i = 0; i < path[m][state].size(); i++) { printf(" %d", path[m][state][i]); } printf("\n\n"); } return 0;}

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