简单的多重背包问题，要使设备的体积之和尽量均匀的分成两部分，设总体积为v2 则该问题就转化成了一个背包容量为v/2的多重背包问题
费用和价值都为设备的体积，根据num[i] * cost[i] 是否小于 v / 2转化为01背包和完全背包做
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<iomanip> 5 #include<string> 6 #define mem(a) memset(a, 0, sizeof(a)) 7 using namespace std; 8 const int maxn = 60; 9 double dp[260000]; 10 int cost[maxn]; int num[maxn]; 11 int main() 12 { 13 int n; 14 while(cin >> n && n > 0) { 15 int v = 0; 16 for(int i = 1 ; i <= n ; i++) cin >> cost[i] >> num[i], v += cost[i] * num[i]; 17 int v1 = v; v /= 2; 18 mem(dp); 19 for(int i = 1 ; i <= n ; i++) { /// complete pack 20 if(cost[i] * num[i] >= v) { 21 for(int j = 1 ; j <= v ; j++) 22 if(j - cost[i] >= 0) 23 dp[j] = max(dp[j], dp[j - cost[i]] + cost[i]); 24 } 25 else { /// zero one pack 26 int k = 1; 27 while(k <=num[i]) { 28 for(int j = v ; j >= cost[i] * k ; j--) dp[j] = max(dp[j], dp[j - cost[i] * k] + cost[i] * k); 29 num[i] -= k; k *= 2; 30 } 31 for(int j = v ; j >= cost[i] * k ; j--) dp[j] = max(dp[j], dp[j - cost[i] * k] + cost[i] * k); 32 } 33 } 34 cout << v1 - dp[v] << " " << dp[v] << endl; 35 } 36 return 0; 37 }