题目链接：点击打开链接
题意：
杭电分设备；
有 n 种设备；
每种都不同，每种都有 w[i] 个；
问怎样分才能使分成的两堆之差最少；
理解：
多重背包；
套模板；
递推式：dp[i] = max(dp[i], dp[i - mul * v[i]] + mul * v[i])；
其中的值根据代码定义；
也可以 01背包做；
但是顺手就用了多重背包；
有个坑，输入结束标志是一个负数，而不是-1；
代码如下：
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <stack> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int MIN_INF = 1e-7; const int MAX_INF = (1e9) + 7; #define X first #define Y second int dp[555555]; int v[1111]; int w[1111]; int main() { int n; while (cin >> n && n >= 0) { memset(dp, 0, sizeof(dp)); int sum = 0; for (int i = 0; i < n; ++i) { cin >> v[i] >> w[i]; sum += v[i] * w[i]; } for (int i = 0; i < n; ++i) { int num = w[i]; for (int k = 1; num > 0; k <<= 1) { // 注意是左移等于 int mul = min(k, num); for (int j = sum / 2; j >= mul * v[i]; --j) { dp[j] = max(dp[j], dp[j - mul * v[i]] + mul * v[i]); } num -= k; } } cout << sum - dp[sum / 2] << " "; cout << dp[sum / 2] << endl; } return 0; }