本文共 883 字,大约阅读时间需要 2 分钟。
标签:01背包
/* 题意:有N种物品,每种价值为V,数量为M。平分为A,B两堆,A,B之差尽可能小,且A不小于B。 思路:01背包变形,用总价值的一半total/2去选择最多价值的物品。*/#include#include #include using namespace std;const int maxn = 125555 + 5;int dp[maxn], value[5005];int main(){ int N; while(scanf("%d", &N) && N > 0) { int total = 0, pos = 0; int a, b; for(int i = 0; i < N; i++) { scanf("%d %d", &a, &b); total += a * b; for(int j = 0; j < b; j++) value[pos++] = a; /// } memset(dp, 0, sizeof(dp)); //ZeroOnePack template for(int i = 0; i < pos; i++) for(int j = total / 2; j >= value[i]; j--) dp[j] = max(dp[j], dp[j - value[i]] + value[i]); printf("%d %d\n", max(dp[total / 2], total - dp[total / 2]), min(dp[total / 2], total - dp[total / 2])); } return 0;}
转载地址:http://wikxi.baihongyu.com/