题目31：考察英国货币面值的组合问题

欧拉计划

Coin sums

In England the currency is made up of pound, ￡, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) and ￡2 (200p).
It is possible to make ￡2 in the following way:

1×￡1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can ￡2 be made using any number of coins?

题目：

在英国，货币是由英镑 ￡，便士 p 构成的。一共有八种钱币在流通：

1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p).
要构造 ￡2 可以用如下方法：

1×￡1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

允许使用任意数目的钱币，一共有多少种构造 ￡2 的方法？

lightninng

python版块的我来凑个热闹
1、解题思路：把问题由大划小，先想一个数用一种货币有多少种组合方法；在一种的基础上想两种货币怎么解决，可以想到，一种货币的数目固定了，另外一种的数目就固定了；在两种的基础上想三种，同理，两种的数目确定了便可以确定第三种的数目
基于此，递归函数解决的问题为，用n种不同的货币组成总钱数为m的方法的数目
例如，总数为200钱币，面值为100的钱币可以有三种选择方法，0,1,2，则在100的钱币为0，1，2的时候用剩下的面值的钱币分别组合成200,100,0即可
2、代码如下：

COUNT = 0  # 变量用于存储构造方法的数目


def coin_sums(pre_sum, coin_values, sum_value):
    global COUNT
    if len(coin_values) == 1:
        if sum_value % coin_values[0] == 0:
            COUNT += 1
            # print(pre_sum + 
            #      "{0}*{1}p".format(sum_value//coin_values[0], str(coin_values[0])))
    else:
        for i in range(sum_value//coin_values[0] + 1):
            coin_sums(pre_sum + "{0}*{1}p + ".format(i, str(coin_values[0])), 
                      coin_values[1:], sum_value-i*coin_values[0])

target = 200
coin_sums("{}p = ".format(str(target)),  [100, 50, 20, 10, 5, 2, 1], target)
print(COUNT)

运行结果

>>> ================================ RESTART ================================
>>> 
73681
>>>

jerryxjr1220

还缺1种，就是由2磅本身构成的。所以应该是
73682种

73682
[Finished in 5.5s]

count = 1
for a in range(3):
        if a * 100 <= 200:
                for b in range(5):
                        if a * 100 + b *50 <= 200:
                                for c in range(11):
                                        if a * 100 + b * 50 + c * 20 <= 200:
                                                for d in range(21):
                                                        if a * 100 + b * 50 + c * 20 + d * 10 <= 200:
                                                                for e in range(41):
                                                                        if a * 100 + b * 50 + c * 20 + d * 10 + e * 5 <= 200:
                                                                                for f in range(101):
                                                                                        if a * 100 + b * 50 + c * 20 + d * 10 + e * 5 + f * 2 <= 200:
                                                                                                for g in range(201):
                                                                                                        if a * 100 + b * 50 + c * 20 + d * 10 + e * 5 + f * 2 + g == 200:
                                                                                                                count += 1
print (count)

芒果加黄桃

# encoding:utf-8
# 英镑组合问题
from time import time 
def euler031():
    count = 0
    for i in (0, 1):  # 1磅
        for j in (0, 1, 2, 3):  # 50便士
            if i * 100 + j * 50 > 200:
                break
            for l in range(0, 10):  # 20便士
                if i * 100 + j * 50 + l * 20 > 200:
                    break
                for k in range(0, 20):  # 10便士
                    if i * 100 + j * 50 + l * 20 + k * 10 > 200:
                        break
                    for m in range(0, 40):  # 5便士
                        if i * 100 + j * 50 + l * 20 + k * 10 + m * 5 > 200:
                            break
                        for n in range(0, 100):  # 2便士
                            if i * 100 + j * 50 + l * 20 + k * 10 + m * 5 + n * 2 > 200:
                                break
                            for o in range(0, 200):  # 1便士
                                tmp = i * 100 + j * 50 + l * 20 + k * 10 + m * 5 + n * 2 + o
                                if tmp == 200:
                                    count += 1
                                # print(i, j, k, m, n, o)
                                    break
                                if tmp > 200:
                                    break
    # 加上7种一种面值组成的  如果2磅也算的话  加8种
    print(count + 7)      
if __name__ == '__main__':
    start = time() 
    euler031()
    print('cost %.6f sec' % (time() - start))

73681
cost 1.730173 sec

渡风

此代码使用matlab编程
Problem31所用时间为2.0718秒
Problem31的答案为73682
感谢楼上的兄弟提供的思路

%% Problem31
% 题目31:考察英国货币面值的组合问题
%细节 Break的使用
function Output=Problem31(Input)
tic
if nargin==0
Input=200;
end
tic
Type=0;
for a1=0:Input
    for a2=0:100
        if a1+2*a2>Input
            break
        end
        for a3=0:40
            if a1+2*a2+5*a3>Input
                break
            end
            for a4=0:20
                if a1+2*a2+5*a3+10*a4>Input
                    break
                end
                for a5=0:10
                    if a1+2*a2+5*a3+10*a4+20*a5>Input
                        break
                    end
                    for a6=0:4
                        if a1+2*a2+5*a3+10*a4+20*a5+50*a6>Input
                            break
                        end
                        for a7=0:1
                            if a1+2*a2+5*a3+10*a4+20*a5+50*a6+100*a7==Input
                                Type=Type+1;
                            end
                        end
                    end
                end
            end
        end
    end
end
Type=2+Type;%一张200磅，两张100磅
Output=Type;
toc
toc
disp('此代码使用matlab编程')
disp(['Problem31所用时间为',num2str(toc),'秒'])
disp(['Problem31的答案为',num2str(Output)])

由我们主宰

public class CoinSums{
        public static void main(String[] args){
                int sum = 0,count = 1;
                for(int hundred = 0;hundred <= 2;hundred++){
                        sum = 0;
                        sum = 100*hundred;
                        if(sum > 200){
                                continue;
                        }
                        for(int fifty = 0;fifty <= 4;fifty++){
                                sum = 100*hundred+50*fifty;
                                if(sum > 200){
                                        continue;
                                }
                                for(int twenty = 0;twenty <= 10;twenty++){
                                        sum = 100*hundred+50*fifty+20*twenty;
                                        if(sum > 200){
                                                continue;
                                        }
                                        for(int ten = 0;ten <= 20;ten++){
                                                sum = 100*hundred+50*fifty+20*twenty+10*ten;
                                                if(sum > 200){
                                                        continue;
                                                }
                                                for(int five = 0;five <= 40;five++){
                                                        sum = 100*hundred+50*fifty+20*twenty+10*ten+5*five;
                                                        if(sum > 200){
                                                                continue;
                                                        }
                                                        for(int two = 0;two <= 100;two++){
                                                                sum = 100*hundred+50*fifty+20*twenty+10*ten+5*five+2*two;
                                                                if(sum > 200){
                                                                        continue;
                                                                }
                                                                for(int one = 0;one <= 200;one++){
                                                                        sum = 100*hundred+50*fifty+20*twenty+10*ten+5*five+2*two+one;
                                                                        if(sum == 200){
                                                                                count ++;
                                                                                System.out.print("第"+count+"种情况");
                                                                                System.out.println(hundred+"\t"+fifty+"\t"+twenty+"\t"+ten+"\t"+five+"\t"+two+"\t"+one);
                                                                        }
                                                                }
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
}

73682

王小召

73682

count = 0


def get_target(values, target):
    global count
    if len(values) > 1:
        for i in range(target//values[0] + 1):
            get_target(values[1:], target - i*values[0])
    else:
        count += 1
    return count

values = [200, 100, 50, 20, 10, 5, 2, 1]
target = 200
get_target(values, target)
print(count)

debuggerzh

73682
动态规划之无限背包问题，状态转移方程为

                               
登录/注册后可看大图

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

const int coin[] = {1,2,5,10,20,50,100,200};
int comb[10][205];

int dp(int i,int sum){
  //cout << i << " " << sum << endl;
  //if (sum == 0) {cnt++; return 0;}
  if (i == 1) return comb[i][sum] = 1;
  if (comb[i][sum] >= 0)  return comb[i][sum];
  int k = sum / coin[i-1];

  int res = 0;
  for (int j = 0;j <= k;j++)
    res += dp(i-1,sum - j*coin[i-1]);
  return comb[i][sum] = res;
}

int main(){
  memset(comb,-1,sizeof(comb));
  cout << dp(8,200) << endl;
  return 0;
}

a1351468657

#include <stdio.h>
#include <time.h>

main()
{
        int sum, count = 0;
        int begin = time(0), end;

        for (int a = 0; a <= 2; a++)
        {
                if (a == 2)
                {
                        count++;
                        break;
                }
                for (int b = 0; b <= 4; b++)
                {
                        for (int c = 0; c <= 10; c++)
                        {        
                                for (int d = 0; d <= 20; d++)
                                {
                                        for (int e = 0; e <= 40; e++)
                                        {        
                                                for (int f = 0; f <= 100; f++)
                                                {
                                                        for (int g = 0; g <= 200; g++)
                                                        {
                                                                sum = a * 100 + b * 50 + c * 20 + d * 10 + e * 5 + f * 2 + g;
                                                                if (200 == sum)
                                                                {
                                                                        count++;
                                                                }
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
        end = time(0);
        printf("%d\n", count + 1); 
        printf("time = %ds\n", end - begin);
}

73682

guosl

/*
动态规划
答案：73682
*/
#include <iostream>
using namespace std;

int a[8] = { 1, 2, 5, 10, 20, 50, 100,200 };//各种币值
long long f[201] = { 1 };//f[k]表示k值可以有多少种构造方式

int main(void)
{
  //动态转移方程
  for (int i = 0; i < 8; ++i)//对钞票的种类进行枚举
  {
    for (int j = 200; j >= a[i]; --j)//对要构造的值j进行枚举
    {
      for (int k = 1; k * a[i] <= j; ++k)//对构造的钞票张数进行枚举
        f[j] += f[j - k * a[i]];//在原来基础上添加k张值为a[i]便士的钞票
    }
  }
  cout << f[200] << endl;
  return 0;
}