题意:已知n个设备的价值和数量,将它们分给AB两人,要求两人分得价值尽可能相同,且A>=B。
分析:
1、每种设备的数量是有限个,所以相当于有cnt个设备,每个设备具有一定的价值,B分得的价值最大为sum/2。
2、背包容量为sum/2,每个设备可选可不选,因此A的价值为sum - dp[sum / 2]。
3、dp[i]---截止到当前设备,背包内价值为i时背包的最大价值。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define lowbit(x) (x & (-x)) const double eps = 1e-8; inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1; } typedef long long LL; typedef unsigned long long ULL; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const LL LL_INF = 0x3f3f3f3f3f3f3f3f; const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const int MAXN = 5000 + 10; const int MAXT = 250000 + 10; using namespace std; int v[MAXN]; int dp[MAXT]; int main(){ int N; while(scanf("%d", &N) == 1){ if(N < 0) return 0; memset(dp, 0, sizeof dp); int V, M; int cnt = 0; int sum = 0; for(int i = 0; i < N; ++i){ scanf("%d%d", &V, &M); sum += V * M; while(M--){ v[cnt++] = V; } } for(int i = 0; i < cnt; ++i){ for(int j = sum / 2; j >= v[i]; --j){ dp[j] = max(dp[j], dp[j - v[i]] + v[i]); } } printf("%d %d ", sum - dp[sum / 2], dp[sum / 2]); } return 0; }