问题描述

Whuacmers 使用硬币进行支付。他们拥有面值为 A1, A2, A3...An 的银币。某天 Hibix 打开钱包发现了一些硬币，他想用这些硬币购买一块价格不超过 m 的手表，并且希望正好支付手表的价格（不需要找零）。

编写程序读取 n、m 以及各硬币的面值和数量，计算能够恰好支付多少种不同的价格（范围从 1 到 m）。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含两个整数 n（1 ≤ n ≤ 100）和 m（m ≤ 100000）。第二行包含 2n 个整数，表示 A1, A2, A3...An, C1, C2, C3...Cn（1 ≤ Ai ≤ 100000, 1 ≤ Ci ≤ 1000）。输入以两个 0 结束。

输出格式

对于每个测试用例，在一行中输出答案。

样例输入

3 10
1 2 4 2 1 1

2 5
1 4 2 1

0 0

样例输出

8
4

解决方案

这是一个典型的多重背包问题。每种面值的硬币都有一定的数量限制，需要计算在给定约束下可以组成多少种不同的金额。

解决思路是将多重背包问题转化为 01 背包和完全背包的组合。当某种硬币的总价值超过目标金额时，可视为完全背包处理；否则使用二进制优化的 01 背包方法。

实现方案一：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int value[110];
int count[110];
int dp[100005];

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        if(n == 0 && m == 0)
            break;
            
        memset(value, 0, sizeof(value));
        memset(count, 0, sizeof(count));
        for(int i = 1; i <= m; i++)
            dp[i] = -9999999;
        dp[0] = 1;
        
        for(int i = 1; i <= n; i++)
            scanf("%d", &value[i]);
        for(int i = 1; i <= n; i++)
            scanf("%d", &count[i]);
            
        for(int i = 1; i <= n; i++)
        {
            if(value[i] * count[i] >= m) // 完全背包
            {
                for(int j = value[i]; j <= m; j++)
                {
                    dp[j] = max(dp[j], dp[j - value[i]] + value[i]);
                }
            }
            else // 01背包优化
            {
                for(int k = 1; k <= count[i]; k *= 2)
                {
                    for(int j = m; j >= value[i] * k; j--)
                    {
                        dp[j] = max(dp[j], dp[j - value[i] * k] + value[i] * k);
                    }
                    count[i] -= k;
                }
                if(count[i] > 0)
                {
                    for(int j = m; j >= value[i] * count[i]; j--)
                        dp[j] = max(dp[j], dp[j - value[i] * count[i]] + value[i] * count[i]);
                }
            }
        }
        
        int result = 0;
        for(int i = 1; i <= m; i++)
        {
            if(dp[i] >= 0)
                result++;
        }
        printf("%d\n", result);
    }
    return 0;
}

实现方案二：

#include<iostream>
#include<string.h>
using namespace std;

int coinValue[200], coinCount[200], dp[100005];

void zeroOnePack(int val, int vol, int capacity)
{
    for(int i = capacity; i >= vol; --i)
    {
        dp[i] = max(dp[i], dp[i - vol] + val);
    }
}

void completePack(int val, int vol, int capacity)
{
    for(int i = vol; i <= capacity; ++i)
    {
        dp[i] = max(dp[i], dp[i - vol] + val);
    }
}

void multiplePack(int val, int vol, int num, int capacity)
{
    if(vol * num >= capacity)
    {
        completePack(val, vol, capacity);
        return;
    }
    
    for(int i = 0; (1 << i) <= num; ++i)
    {
        zeroOnePack(val << i, vol << i, capacity);
        num -= (1 << i);
    }
    
    if(num)
    {
        zeroOnePack(val * num, vol * num, capacity);
    }
}

int main()
{
    int n, m;
    while(cin >> n >> m)
    {
        if(n + m == 0)
            break;
            
        memset(dp, 0, sizeof(dp));
        
        for(int i = 0; i < n; i++)
            cin >> coinValue[i];
        for(int i = 0; i < n; i++)
            cin >> coinCount[i];
            
        for(int i = 0; i < n; i++)
        {
            multiplePack(coinValue[i], coinValue[i], coinCount[i], m);
        }
        
        int total = 0;
        for(int i = 1; i <= m; i++)
        {
            if(dp[i] == i)
                total++;
        }
        cout << total << endl;
    }
    return 0;
}