Least wasteful use of stamps to achieve a given postage

readme.md

Problem

we have 2 kinds of stamp with values $A and $B, The

number of stamps is infinite, we have a letter to send out and need $T

postage, question is to find out the lowest cost required to get $T postage? Pls describe your method

and code it with any language you are good at( even we perfer C/C++ :）。

example as below,

Input：A B T

1 ≤ A < B ≤ 10e9

1 ≤ T ≤ 10e9

A, B, T are integers

Output： The lowest value of 2 kinds of stamps combination which should

be >= $T

Thoughts

As a human being we first came to a brute-force greedy algorithm w/o thinking, which was:

def greedy(a, b, t):
    num_of_b = t // b
    num_of_a = 1 if t % b else 0
    cost = num_of_a * a + num_of_b * b

    return {'cost': cost, 'num_of_a': num_of_a, 'num_of_b': num_of_b}

Then after a cup of tea we realize that this cannot cover all the cases.

For example, let's say a = 3 and b = 10 and finally t = 12.

If we using the solution above we have 10 + 3 == 13 as a result.

But obviously 3 + 3 + 3 + 3 == 12 is a more acceptable answer.

So we are thinking if there is a way to do it more elegantly?

After a long-time searching the Internet. Finally I got this solution, which I think it emulates the real world scenario.

Let t be your target and a and b < a be the values of the stamps you have. Let n = ⌈t/a⌉ be the maximum number of a stamps it makes sense to use.

For each number i from n to 0, consider the cost of the solution with:

• i stamps of value a and
• j = ⌈(t - i*a) / b⌉ stamps of value b

The cost of each solution would obviously be i*a + j*b.

Your solution is the pair (i, ⌈(t - i*a) / b⌉ ) that minimizes said cost. (Note there's only one unknown in that pair, i.)

Note: This answer is assuming a > b but the raw problem is assuming a < b. And it doesn't matter~

And we do a quick coding work:

import math

def yet_another_solution(a, b, t):
    n = math.ceil(t / b)
    cost = []
    for i in range(n + 1):
        j = math.ceil((t - i * b) / a)
        cost.append({'cost': i * b + j * a, 'num_of_a': j, 'num_of_b': i})

    cost.sort(key=lambda x: x.get('cost'))

    return cost[0]

Voila! We have achieved the goal of this problem.

And the original answer noticed that if we find the division without rest. Then we can give up searching and stop immediately.

An additional optimization would be to stop immediately as soon as a division without rest is performed, either when determining n or j. A division without rest means that we have found a solution that perfectly pays the due amount and cannot thus be improved on. (There may be others like it, but none that is actually better, so there's no need to keep searching).

And there is also a "dp" solution(Why using quotation mark? bc I'm not familiar with those dp stuff... and I also don't know why it works /shrug).

# credit to my kyodai(@tingyume)
def dp_solution(a, b, t):
    def dp(x):
        if not x:
            return 0
        if x <= a:
            return a
        if x <= b:
            return min(b, dp(x - a) + a)

        return min(dp(x - b) + b, dp(x - a) + a)

    return dp(t)

Credit

https://math.stackexchange.com/q/742/593617

https://github.com/nimrc

Bonus

你好，循环是可以这样做的，那我再追问下， A,　B比较小， T比较大的时候，在小的Embedded设备上耗时比较多，请问有没有好的办法可以加速？

Thoughts

首先需要明确的点是不能空谈, 需要紧密贴合实际生活, A,　B比较小， T比较大 其实已经背离了原题针对邮资的场景 (有人见过一千万面值的邮资吗 :P).

再次, 不论怎样的演算法, 都逃不过循环的本质, 无非就是循环的次数的多与少.

我个人推测这个追问应该是想表达如何减少循环的次数, 这样就比较说得通, 也更切合实际一些.

因为 A,　B比较小， T比较大 这个条件可以转义为 a 和 b 跟 T 差好几个量级, 这样才会出现上述的耗时问题.

因为上面正文提到的演算法正是利用了这个量级差做 range 循环求出最优解.

那么在上面正文里面提到的减少循环的方法(整除判断法)我这里就不再赘述.

我这里引入一个新的演算法来处理化解所谓的超大规模循环的问题.

话说回来, 我们就事论事的探讨这种极端的情况, 不难联想到与之类似的另一个经典背包问题.

为了不造成阅读上的困扰, 本文下述把原题的追问代称为 问题α, 把上面引出的背包问题代称为 问题β.

问题β 的本意是计算两种邮票不能拼凑出来的最大的邮资金额, 换句话说也正好符合了 问题α 的思路.

显然, 若 a 和 b 均趋近于 0, 而 T 趋近于正无穷的时候, 有且必有最优解 T' = T.

可能有的小伙伴还不太理解上面这段话的含义, 我引用一张二维表大家就明白了.

import pprint

depth = 10
x = 4
y = 7

matrix = []
for i in range(depth):
    matrix.append([])
    for j in range(depth):
        matrix[i].append(i * x + j * y)

pprint.pp(matrix)

[[0, 7, 14, 21, 28, 35, 42, 49, 56, 63],
 [4, 11, 18, 25, 32, 39, 46, 53, 60, 67],
 [8, 15, 22, 29, 36, 43, 50, 57, 64, 71],
 [12, 19, 26, 33, 40, 47, 54, 61, 68, 75],
 [16, 23, 30, 37, 44, 51, 58, 65, 72, 79],
 [20, 27, 34, 41, 48, 55, 62, 69, 76, 83],
 [24, 31, 38, 45, 52, 59, 66, 73, 80, 87],
 [28, 35, 42, 49, 56, 63, 70, 77, 84, 91],
 [32, 39, 46, 53, 60, 67, 74, 81, 88, 95],
 [36, 43, 50, 57, 64, 71, 78, 85, 92, 99]]

这是一张二维表, 表示了一个为 4 分钱, 另一个为 7 分钱的邮票所能拼凑出来的邮资的结果表.

不难看出从 18 开始之后的数字都是连续出现的, 故此情况下 问题β 的解便是 17.

回到 问题α, A,　B比较小， T比较大 这个描述可以转换成 问题β 中的求最大不可拼凑的邮资.

通过判断求解 问题β 得出的结果 T' 是否小于 问题α 的目标 T, 若小于则可判定 问题alpha 的解必定是最优解 T.

那么这个时候就有同学会问了, 那如果不小于的情况该怎么办呢.

其实大家忽略了一个大前提, 问题α 中清晰的描述了 A,　B比较小， T比较大, 此时必定不可能出现不小于的情况.

若不小于则不满足上述条件了, 这一点也可以通过观察上面的二维表得出结论.

因为我们是处于对时间复杂度的考虑, 在使用上面正文中提到的整除法之前, 先使用本法判定是否已经有最优解.

若无法判定则可继续用整除法求解, 此时正好也满足了量级相对较小, 循环次数减少的基本要求.

需要注意的是, 此方法有一个限制是需要二者的面值的最大公约数不大于1, 换言之是需要两数互质才可以.

否则则求不出此处的不能拼凑出来的最大的邮资金额.

还是之前那句话, 脱离了实际场景的问题都是空谈, 不论是邮票也好, 货币也罢, 很难找不到两个互质的配对.

经过查阅相关资料得出计算公式 T' = xy − x − y. 把上述例子代入公式计算得出 T' = 17

Credit

http://jwilson.coe.uga.edu/emt725/Stamps/TwoStamp.html

https://en.wikipedia.org/wiki/Coin_problem

https://math.stackexchange.com/q/2424616/593617

Bonus

你好，看到了你的一些思路，注意我们说邮票只是为了给个具体的例子，条件并没有限制A, B是不是互质，除了题目里面的条件你也不能自己增加限制条件，所以需要一个相对较快的通用的解法能解决这个问题。

Thoughts

首先为我自己的逻辑思维, 语言组织和表达能力, 写作能力的严重匮乏而道歉.

我自认为在上面的回应中很清晰的表述了针对 A,　B比较小， T比较大 这个特定的场景的一种情况的优化方案.

我没有说要 限制A, B是不是互质, 没有任何这个意思.

但是你问, 你一定要觉得要问我, 对 A,　B比较小， T比较大 这个特定的场景 有没有好的办法可以加速.

我说有, 我就明确地告诉你这一点. 只是上述方案需要先判断 A, B是不是互质.

那么既然都得罪了, 不妨就顺着这个思路继续补充下去, 我们来讨论非互质的情况.

首先我想再把这种情况分为两种子链路, 一条是二者相除可以得到一个整数, 另一条是不能.

A ÷ B ∈ ℤ

这种情况下其实在问题本体中已经讨论过了, 我这里再强调一下其中的一些关键点.

直接拿目标邮资 T 与较小价值的邮票 A 做 ceiling division 操作得出一个正整数 r.

然后用 r 与 A 相乘得出一个近似 T 的数字 T', 此数字即为此题的解.

有一种特殊情况是当正好整除的时候 T' = T.

A ÷ B ∉ ℤ

这种情况可以排除奇数的情况, 因为若不互质, 又不是互相为整数倍数, 是不可能为奇数的.

则此处二者均为偶数, 根据此处的陈述, 可以判断出能获得的结果肯定是二者的最大公约数的倍数

则可先求出此最大公约数, 然后作为除数与 T 做 ceiling division 操作, 之后就跟上面整数的流程是一致的了.

一个相对较快的通用的解法

其实这样的方法是不存在的, 就好比 CAP theorem 一样, 有要满足这一点, 就必须牺牲那一点.

这也是为什么前后三篇拙作通篇离不开 空谈 与 实际.

就算是一块 STM32, 又有谁会拿她去计算圆周率的前一百亿位呢 :P

Credit

https://gist.github.com/hldh214/0fd4fc4b7b7a61df1e09ad410863555b#gistcomment-3635420

import math


def yet_another_solution(a, b, t):
    n = math.ceil(t / b)
    cost = []
    for i in range(n + 1):
        j = math.ceil((t - i * b) / a)

        # fix negative number issue
        if j < 0:
            continue

        cost.append({'cost': i * b + j * a, 'num_of_a': j, 'num_of_b': i})

    cost.sort(key=lambda x: x.get('cost'))

    return cost[0]


def main(a, b, t):
    gcd = math.gcd(a, b)
    is_co_prime = (gcd == 1)

    if is_co_prime:
        mystery_number = a * b - a - b
        if mystery_number < t:
            # Coin problem optimization
            return t
    else:
        if not b % a:
            # A ÷ B ∈ ℤ optimization
            num_of_a = math.ceil(t / a)

            if not t % a:
                return t

            return num_of_a * a

        # A ÷ B ∉ ℤ case
        # @see https://math.stackexchange.com/q/3430648
        mystery_number = ((a * b) / gcd ** 2 - (a + b) / gcd + 1) * gcd

        if mystery_number < t:
            num_of_a = math.ceil(t / gcd)

            if not t % gcd:
                return t

            return num_of_a * gcd

    return yet_another_solution(a, b, t).get('cost')


if __name__ == '__main__':
    print(main(29, 42, 320))