放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

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

目录

组合数学 原书第5版-冯速等译.png挑战程序设计竞赛第二版.jpg

POJ 3260 The Fewest Coins 

最小货币流通:用面值Vi,个数Ci的硬币购买价格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的子序列出来,按照《组合数学》中的证明:

组合数学 原书第5版-冯速等译.png

hankcs.com 2017-01-15 下午11.46.35.png

它们存在子序列可以被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;
}
16483065 hankcs 3260 Accepted 360K 125MS C++ 1862B 2017-01-16 13:03:46

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

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的作品

HanLP自然语言处理包《自然语言处理入门》