POJ 3260 The Fewest Coins 题解《挑战程序设计竞赛》

POJ 3260 The Fewest Coins 

最小货币流通：用面值V_i，个数C_i的硬币购买价格T的商品，假设商店每种面值的硬币都有无限个，求最小货币流通量。

4.4常用技巧精选（二） 

双端队列 

流通分为付钱和找钱两个过程，定义两个过程分别需要的硬币数为如下dp数组：

int dp_change[MAX_T + MAX_V * MAX_V];   // dp_change[i] := 商店找钱金额为i时最少硬币数
int dp_pay[MAX_T + MAX_V * MAX_V];      // dp_pay[i] := 顾客付钱金额为i时最少硬币数

那么最终答案为两个硬币数之和的最小值：

for (int i = max_v * max_v; i >= 0; --i)
{
    ans = min(ans, dp_change[i] + dp_pay[T + i]);
}

上面付出了T+i金额的钱，收回了i金额的钱，于是实际上就买到了价格T的商品。

问题大的框架就是这样，再来看怎么求解两个子过程的解。

付钱阶段

付钱阶段，每个硬币的携带量有限。将硬币视作物品，硬币的价格作为物品的重量，硬币的个数1作为物品的价值，则给定某个T作为背包容量W，问题转化为“物品价值总和最小”的多重背包问题。

多重背包问题可以用书上的双端队列，也可以二进制分解转化为01背包问题，O(nWlog m)快速求解。

// 多重背包转化为二进制的01背包
void dp_multiple_pack(int n, int W)
{
    memset(dp_pay, 0x3f, (W + 1) * sizeof(int));
    dp_pay[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int num = C[i];
        for (int k = 1; num > 0; k <<= 1)
        {
            int mul = min(k, num);
            for (int j = W; j >= V[i] * mul; --j)
            {
                dp_pay[j] = min(dp_pay[j], dp_pay[j - V[i] * mul] + mul);   // 价值为1
            }
            num -= mul;
        }
    }
}

找钱阶段

找钱阶段，硬币数量不限，在类似的思路下直接视作完全背包问题。

// 完全背包
void dp_complete_pack(int n, int W)
{
    memset(dp_change, 0x3f, (W + 1) * sizeof(int));
    dp_change[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = V[i]; j <= W; ++j)
        {
            dp_change[j] = min(dp_change[j], dp_change[j - V[i]] + 1);  // "价值总和"最小
        }
    }
}

鸽笼原理

题目的难点其实在于背包容量W的确定，W的意义为最优方案金额的最大值（上界）。

上述定义中频繁出现

MAX_T + MAX_V * MAX_V

意味着，要凑足（大于等于）价格T的商品且硬币数最少，最多只能多给max_v * max_v的金额（其中max_v为硬币的最大面值），称此上界为W。为什么会有这么紧的上界呢，假设存在一种最优支付方案，给了多于t + max_v * max_v的钱，那么商店就会找回多于max_v * max_v的钱，这些硬币的个数大于max_v。设这些硬币的面值分别为a_i，根据鸽笼原理的应用，硬币序列中存在至少两个子序列，这两个子序列的和分别都能被max_v整除。如果我们直接用长度更小的那个子序列换算为面值为max_v的硬币某整数个，再去替换母序列就能用更少的硬币买到商品，形成矛盾。

关于整除更详细的证明如下，尝试构造这样的子序列。长度为max_v+x的母序列至少可以找两个不同的长度为max_v的子序列出来，按照《组合数学》中的证明：

它们存在子序列可以被max_v整除。

完整代码

#include <iostream>

using namespace std;
const int MAX_T = 10000 + 4;
const int MAX_N = 100 + 2;
const int MAX_V = 120 + 1;
const int INF = 0x3f3f3f3f;

int N, T;
int V[MAX_N], C[MAX_N];     // 面值和携带个数
int max_v;                  // 最大面值
int dp_change[MAX_T + MAX_V * MAX_V];   // dp_change[i] := 商店找钱金额为i时最少硬币数
int dp_pay[MAX_T + MAX_V * MAX_V];      // dp_pay[i] := 顾客付钱金额为i时最少硬币数

// 完全背包
void dp_complete_pack(int n, int W)
{
    memset(dp_change, 0x3f, (W + 1) * sizeof(int));
    dp_change[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = V[i]; j <= W; ++j)
        {
            dp_change[j] = min(dp_change[j], dp_change[j - V[i]] + 1);  // "价值总和"最小
        }
    }
}

// 多重背包转化为二进制的01背包
void dp_multiple_pack(int n, int W)
{
    memset(dp_pay, 0x3f, (W + 1) * sizeof(int));
    dp_pay[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int num = C[i];
        for (int k = 1; num > 0; k <<= 1)
        {
            int mul = min(k, num);
            for (int j = W; j >= V[i] * mul; --j)
            {
                dp_pay[j] = min(dp_pay[j], dp_pay[j - V[i] * mul] + mul);   // 价值为1
            }
            num -= mul;
        }
    }
}

void solve()
{
    dp_multiple_pack(N, T + max_v * max_v);     // 付钱
    dp_complete_pack(N, T + max_v * max_v);     // 找钱
    int ans = INF;
    for (int i = max_v * max_v; i >= 0; --i)
    {
        ans = min(ans, dp_change[i] + dp_pay[T + i]);
    }
    if (ans == INF)
    {
        ans = -1;
    }
    printf("%d\n", ans);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d", &N, &T);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &V[i]);
        max_v = max(max_v, V[i]);
    }
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &C[i]);
    }
    solve();
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3260 The Fewest Coins 题解《挑战程序设计竞赛》