题目链接：http://poj.org/problem?id=1276
一开始tle，后来看了多重背包优化成0-1背包，复杂度从O(V\sumM_i)变成O(V\sumlogM_i)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;//POJ 1276 Cash Machineint main() {int cash, n;while (~scanf("%d %d", &cash, &n)){if (n == 0){printf("%d\n", 0);continue;}vector<int>zero_one_bug;vector<int> amount(n), denomination(n);for (int i = 0; i < n; ++i){int amount, denomination;scanf("%d %d", &amount, &denomination);int k = 1;while (amount > 0){if (amount < k){zero_one_bug.push_back(amount*denomination);break;}amount -= k;zero_one_bug.push_back(k*denomination);k <<= 1;}}int size = zero_one_bug.size();bool **dp = new bool*[size + 1];for (int i = 0; i <= size; ++i)dp[i] = new bool[cash + 1];//dp[i][j]表示在只有前i个的情况下，容量为j的包能否装满for (int i = 0; i < size + 1; ++i){dp[i][0] = true;for (int j = 1; j < cash + 1; ++j)dp[i][j] = false;}for (int i = 0; i < size; ++i){int temp = std::min(zero_one_bug[i], cash);for (int j = 0; j <= temp; ++j){dp[i + 1][j] |= dp[i][j];if (dp[i + 1][j])continue;}temp = zero_one_bug[i];for (int j = temp; j <= cash; ++j){dp[i + 1][j] = dp[i][j] | dp[i][j - temp];if (dp[i + 1][j])continue;}}int cur_cash = cash;for (;; cur_cash--)if (dp[size][cur_cash])break;printf("%d\n", cur_cash);for (int i = 0; i <= size; ++i)delete[] dp[i];delete[] dp;}system("pause");return 0;
}