题目31：考察英国货币面值的组合问题
本帖最后由 欧拉计划 于 2015-4-23 23:35 编辑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 于 2015-5-1 19:59 编辑
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:
COUNT += 1
# print(pre_sum +
# "{0}*{1}p".format(sum_value//coin_values, str(coin_values)))
else:
for i in range(sum_value//coin_values + 1):
coin_sums(pre_sum + "{0}*{1}p + ".format(i, str(coin_values)),
coin_values, sum_value-i*coin_values)
target = 200
coin_sums("{}p = ".format(str(target)),, target)
print(COUNT)运行结果
>>> ================================ RESTART ================================
>>>
73681
>>> 还缺1种，就是由2磅本身构成的。所以应该是
73682种
73682
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 本帖最后由 渡风 于 2017-1-23 21:38 编辑
此代码使用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 + 1):
get_target(values, target - i*values)
else:
count += 1
return count
values =
target = 200
get_target(values, target)
print(count) 73682
动态规划之无限背包问题，状态转移方程为
https://wx2.sinaimg.cn/mw690/0081qlg6ly1ghicxavzw0j30nm00uwed.jpg
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int coin[] = {1,2,5,10,20,50,100,200};
int comb;
int dp(int i,int sum){
//cout << i << " " << sum << endl;
//if (sum == 0) {cnt++; return 0;}
if (i == 1) return comb = 1;
if (comb >= 0)return comb;
int k = sum / coin;
int res = 0;
for (int j = 0;j <= k;j++)
res += dp(i-1,sum - j*coin);
return comb = res;
}
int main(){
memset(comb,-1,sizeof(comb));
cout << dp(8,200) << endl;
return 0;
}
#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 于 2022-1-3 10:43 编辑
/*
动态规划
答案：73682
*/
#include <iostream>
using namespace std;
int a = { 1, 2, 5, 10, 20, 50, 100,200 };//各种币值
long long f = { 1 };//f表示k值可以有多少种构造方式
int main(void)
{
//动态转移方程
for (int i = 0; i < 8; ++i)//对钞票的种类进行枚举
{
for (int j = 200; j >= a; --j)//对要构造的值j进行枚举
{
for (int k = 1; k * a <= j; ++k)//对构造的钞票张数进行枚举
f += f];//在原来基础上添加k张值为a便士的钞票
}
}
cout << f << endl;
return 0;
}
页:
[1]