All geek questions in one place

Complete coin combination search algorithm

The problem is similar to the problem with changing coins, but a little different.

The problem is this: you have a collection of coins, and you know the values ​​of the coins and the amount of each type of coin in it. You want to know how many different amounts you can make from non-empty groupings of these coins.

So, for example, from coins = [1, 2, 3]and quantity = [1, 2, 2], there are 11 possible sums, basically all numbers from 1 to 11.

The length of the coin array can reach 20, but the number [x] can reach 10 ^ 5.

What will be an effective solution to the algorithm. Collecting all the possible combinations of such a large amount will take forever. Is there a mathematical formula that can determine the answer? I don’t see how it will work, especially he wants excellent amounts.

I was thinking about creating an array base on coins and its quantity. Basically there are several:

[ [1],
  [2, 4],
  [3, 6]]

Then you need to select 1 or none of each array.

1
1,2
1,4
1,3
...
1,4,6

I don't seem to think of a good algorithm to accomplish this. Executing a nested loop may be too slow, as there can be 20 different coins, and each coin can have a large amount.

Another possible solution is a cycle from 1 to maximum. Where maximum is the sum of all coins multiplied by its amount. But the problem would be to determine if there is a subset that will be equal to that number. I know that there is a dynamic programming algorithm (the sum of a subset) to determine if there is a subset that will contain a specific value, but what will be the array?

, [1,2,4,3,6], 11, "True" DP 11. , , coins = [10,50,100] quantity = [1,2,1]. - 9 , sum DP algo 21 'True'. [10,50,100,100] [10,50,100] [[10], [50, 100], [100]]

python , .

, 21 [10,50,100].

def possibleSums(coins, quantity):
    def subsetSum(arr,s):
        dp = [False] * (s + 1)  
        dp[0] = True

        for num in sorted(arr):  
            for i in range(1, len(dp)):  
                if num <= i:  
                    dp[i] = dp[i] or dp[i - num]  
        return sum(dp)


    maximum = sum((map(lambda t: t[0] * t[1], zip(coins, quantity))))

    combinations = [[]]*len(coins)
    for i,c in enumerate(coins):
        combinations[i] = [ j for j in range(c,(c*quantity[i])+1,c) ]

    array = []
    for item in combinations:
        array.extend(item)

    print(subsetSum(array,maximum) - 1)

:

1 ≤ coins.length ≤ 20,
1 ≤ coins[i] ≤ 10^4.

quantity.length = coins.length,
1 ≤ quantity[i] ≤ 10^5.

, ( [0] + 1) * ( [1] + 1) *... * ( [. - 1] + 1) <= 10 ^ 6.

+10
6

, , , .

:

    for num in sorted(arr):  
        for i in range(len(dp)-1,-1,-1):  
            if num <= i:  
                dp[i] = dp[i] or dp[i - num]

, , :

def possibleSums2(coins, quantity):
    maximum = sum((map(lambda t: t[0] * t[1], zip(coins, quantity))))

    dp = [False] * (maximum + 1)
    dp[0] = True
    for coin,q in zip(coins,quantity):
        for b in range(coin):
            num = -1
            for i in range(b,maximum+1,coin):
                if dp[i]:
                    num = 0
                elif num>=0:
                    num += 1
                dp[i] = 0 <= num <= q

    print(sum(dp) - 1)

O ( * ) O ( * *)

+10

, .

[0]. , . , , . - . , : = [1, 2, 3], = [1, 2, 2]. ...

sum_set = {0}
current_coin  = 1;  #  coin[0]
current_quant = 1;  # quant[0]
This step is trivial ... add 1 to each element of the set.  This gives you {1}.
Add that to the existing set.  You now have
sum_set = {0, 1}

:

current_coin  = 2;  #  coin[0]
current_quant = 2;  # quant[0]
Now, you have two items to add to each set element: 1*2, giving you {2, 3}; and 2*2, giving you {4, 5}.  
Add these to the original set:
sum_set = {0, 1, 2, 3, 4, 5}

:

current_coin  = 3;  #  coin[0]
current_quant = 2;  # quant[0]
You add 1*3 and 2*3 to each set element, giving you {3, 4, 5, 6, 7, 8} and {6, 7, 8, 9, 10, 11}.  
Adding these to the sum_set gives you the set of integers 0 through 11.

0 ( ) . 11 - .

, ? .

+9

,

, ( [0] + 1) * ( 1 + 1) *... * ( [ quantity.length - 1] + 1) <= 10 ^ 6

! , , , . 10 ^ 6 .

, , Q V

1 + x^V + x^(2V) + ... + x^(QV)

N N.

,

(1 + x^(V1) + x^(2*V1) + ... + x^(Q1*V1))(1 + x^(V2) + x^(2*V2) + ... + x^(Q2*V2))

N , N , .

, . dict set , , , . , . , - , .

+4

(Python 3):

def numsums(values, counts):
    from itertools import product
    choices = [range(0, v*c+1, v) for v, c in zip(values, counts)]
    sums = {sum(p) for p in product(*choices)}
    return len(sums) - 1  # sum "0" isn't interesting

, ,

print(numsums([10,50,100], [1, 2, 1])) # 9
print(numsums([1, 2, 3], [1, 2, 2])) # 11
print(numsums([1, 2, 4, 8, 16, 32], [1]*6)) # 63

; , :

def numsums(values, counts):
    sums = {0}
    for v, c in zip(values, counts):
        sums |= {i + choice
                 for choice in range(v, v*c+1, v)
                 for i in sums}
    return len(sums) - 1  # sum "0" isn't interesting

, ;-), @user2357112, "" " ?" ( "" , sums). "" , (value, count), x**0 |=. , , , ""; -)

+3

hmm. This is a very interesting problem. If you just want to get the value of the sum useSums (). To view all cases, use possibleCases ().

import itertools


coins = ['10', '50', '100']
quantity = [1, 2, 1]

# coins = ['A', 'B', 'C', 'D']
# quantity = [1, 2, 2, 1]


def possibleSums(coins, quantity):
    totalcnt=1
    for i in quantity:
        totalcnt = totalcnt * (i+1)
    return totalcnt-1    # empty case remove


def possibleCases(coins, quantity):
    coinlist = []
    for i in range(len(coins)):
        cset=[]
        for j in range(quantity[i]+1):
            val = [coins[i]] * j
            cset.append(val)
        coinlist.append(cset)
    print('coinlist=', coinlist)

    # combination the coinlist
    # cases=combcase(coinlist)
    # return cases
    alllist =  list(itertools.product(*coinlist))
    caselist = []
    for x in alllist:
        mergelist = list(itertools.chain(*x))
        if len(mergelist)==0 :  # skip empty select.
            continue
        caselist.append(mergelist)
    return caselist


sum = possibleSums(coins, quantity)
print( 'sum=', sum)

cases = possibleCases(coins, quantity)
cases.sort(key=len, reverse=True)
cases.reverse()

print('count=', len(cases))
for i, x in enumerate(cases):
    print('case',(i+1), x)

conclusion is

sum= 11
coinlist= [[[], ['10']], [[], ['50'], ['50', '50']], [[], ['100']]]
count= 11
case 1 ['10']
case 2 ['50']
case 3 ['100']
case 4 ['10', '50']
case 5 ['10', '100']
case 6 ['50', '50']
case 7 ['50', '100']
case 8 ['10', '50', '50']
case 9 ['10', '50', '100']
case 10 ['50', '50', '100']
case 11 ['10', '50', '50', '100']

You can check other cases. coins = ['A', 'B', 'C', 'D'] quantity = [1, 3, 2, 1]

sum= 47
coinlist= [[[], ['A']], [[], ['B'], ['B', 'B'], ['B', 'B', 'B']], [[], ['C'], ['C', 'C']], [[], ['D']]]
count= 47
case 1 ['A']
case 2 ['B']
case 3 ['C']
case 4 ['D']
case 5 ['A', 'B']
case 6 ['A', 'C']
case 7 ['A', 'D']
case 8 ['B', 'B']
case 9 ['B', 'C']
case 10 ['B', 'D']
case 11 ['C', 'C']
case 12 ['C', 'D']
case 13 ['A', 'B', 'B']
case 14 ['A', 'B', 'C']
case 15 ['A', 'B', 'D']
case 16 ['A', 'C', 'C']
case 17 ['A', 'C', 'D']
case 18 ['B', 'B', 'B']
case 19 ['B', 'B', 'C']
case 20 ['B', 'B', 'D']
case 21 ['B', 'C', 'C']
case 22 ['B', 'C', 'D']
case 23 ['C', 'C', 'D']
case 24 ['A', 'B', 'B', 'B']
case 25 ['A', 'B', 'B', 'C']
case 26 ['A', 'B', 'B', 'D']
case 27 ['A', 'B', 'C', 'C']
case 28 ['A', 'B', 'C', 'D']
case 29 ['A', 'C', 'C', 'D']
case 30 ['B', 'B', 'B', 'C']
case 31 ['B', 'B', 'B', 'D']
case 32 ['B', 'B', 'C', 'C']
case 33 ['B', 'B', 'C', 'D']
case 34 ['B', 'C', 'C', 'D']
case 35 ['A', 'B', 'B', 'B', 'C']
case 36 ['A', 'B', 'B', 'B', 'D']
case 37 ['A', 'B', 'B', 'C', 'C']
case 38 ['A', 'B', 'B', 'C', 'D']
case 39 ['A', 'B', 'C', 'C', 'D']
case 40 ['B', 'B', 'B', 'C', 'C']
case 41 ['B', 'B', 'B', 'C', 'D']
case 42 ['B', 'B', 'C', 'C', 'D']
case 43 ['A', 'B', 'B', 'B', 'C', 'C']
case 44 ['A', 'B', 'B', 'B', 'C', 'D']
case 45 ['A', 'B', 'B', 'C', 'C', 'D']
case 46 ['B', 'B', 'B', 'C', 'C', 'D']
case 47 ['A', 'B', 'B', 'B', 'C', 'C', 'D']
0
source

This is the javascript version of Peter de Rives, but a bit more efficient, since you don’t have to do the maximum iteration for each coin to find the remainder



function possibleSums(coins, quantity) {
    // calculate running max sums
  var prevmax = 0;
  var maxs = [];
  for (var i = 0; i < coins.length; i++) {
    maxs[i] = prevmax + coins[i] * quantity[i];
    prevmax = maxs[i];
  }

  var dp = [true];

  for (var i = 0; i < coins.length; i++) {
    var max = maxs[i];
    var coin = coins[i];
    var qty = quantity[i];
    for (var j = 0; j < coin; j++) {
      var num = -1;
      // only find remainders in range 0 to maxs[i];
      for (var k = j; k <= max; k += coin) {
        if (dp[k]) {
          num = 0;
        } 
        else if (num >= 0) {
          num++;
        }
        dp[k] = 0 <= num && num <= qty;    
      }
    }
  }

  return dp.filter(e => e).length - 1;
}
0
source

Source: https://habr.com/ru/post/1016801/

More articles:


All Articles