POJ 1276 Cash Machine（分组背包，经典）

题目意思：
给出金钱数和N种不同的钱币数量和面额，求出这n种面额能够凑出的不大于给出金钱数的最大值

本题要点：
1、多重背包，二进制拆分法：(参考 《算法竞赛进阶指南》 280页)
币值为 money[i], 数量为 cnt[i] 的硬币，拆分为 2^0, 2^1, 2^2, …, 2^p , r （r = cnt[i] - 2^0 - 2^1 - 2^2 - … - 2^p）
组硬币， 每组硬币的 体积为 2^k (0 <= k <= p),价值是 money[i] * 2^k 。
这种方法，把每一种硬币分为 了 O(log(cnt[i])) 个。
如果采用直接分拆法，每一种硬币分为 cnt[i] 个。
2、然后，原来的多重背包，转化为 01 背包，套用 01 背包的模板。
3、 状态表示:
dp[i] 表示当前能够组成的面值不大于 i 的面值的最大值。
4、 状态转移：
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 20, MaxM = 100010;
int money[MaxN], cnt[MaxN];
int n, cash, m;	//m表示钞票一共多少张
int v[MaxM], w[MaxM];	
int dp[MaxM];	//dp[j] 表示 int calc(int c)		// 求出 2^0 + 2^1 + ... + 2^p <= c 的最大的p
{
    int p = 0;while((1 << p) - 1 <= c){
    p++;}return p - 1;
}void solve()
{
    int indx = 0;memset(dp, 0xcf, sizeof dp);dp[0] = 0;for(int i = 1; i <= n; ++i){
    if(!cnt[i])continue;int p = calc(cnt[i]);int r = cnt[i] - (1 << p) + 1;for(int j = 0; j < p; ++j)	{
    w[++indx] = money[i] * (1 << j);	v[indx] = (1 << j);}if(r > 0){
    w[++indx] = money[i] * r;v[indx] = r;}}for(int i = 1; i <= indx; ++i){
    for(int j = cash; j >= w[i]; --j){
    dp[j] = max(dp[j], dp[j - w[i]] + w[i]);}}for(int i = cash; i >= 0; --i){
    if(dp[i] >= 0){
    printf("%d\n", dp[i]);return;}}
}int main()
{
    while(scanf("%d", &cash) != EOF){
    scanf("%d", &n);m = 0;for(int i = 1; i <= n; ++i){
    scanf("%d%d", &cnt[i], &money[i]);m += cnt[i];}solve();}return 0;
}/* 735 3 4 125 6 5 3 350 633 4 500 30 6 100 1 5 0 1 735 0 0 3 10 100 10 50 10 10 *//* 735 630 0 0 */