题目链接：http://poj.org/problem?id=1014
多重背包 –> 01背包。
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;//POJ 1014 Dividingint main()
{int amount;int sum, count = 0;while (true){count++;sum = 0;vector<pair<int, int> > zero_one_bug;for (int i = 0; i < 6; i++) {scanf("%d", &amount);sum += amount * (i + 1);int k = 1;while (amount > 0) {if (amount < k) {zero_one_bug.push_back(make_pair(amount, amount * (i + 1)));break;}amount -= k;zero_one_bug.push_back(make_pair(k, k * (i + 1)));k <<= 1;}}if (sum == 0)break;if (sum & 1 == 1){printf("Collection #%d:\n", count);printf("Can't be divided.\n\n");continue;}int V = sum >> 1; // 价值即容量vector<int> F(V + 1); // F[i, v] 表示前i个物品在容量为v的情况下的最大容量。for (int i = 0; i < V + 1; i++)F[i] = 0;const int size = zero_one_bug.size();for (int i = 0; i < size; i++){int value = zero_one_bug[i].second;for (int v = V; v >= value; v--) {F[v] = max(F[v], F[v - value] + value);}}printf("Collection #%d:\n", count);if (F[V] != V) printf("Can't be divided.\n\n");else printf("Can be divided.\n\n");}system("pause");return 0;
}