Least wasteful use of stamps to achieve a given postage

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

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))

hldh214/readme.md

Select an option

No results found

Select an option

No results found

Problem

Thoughts

Credit

hldh214 commented Feb 19, 2021

Uh oh!