我要招人

去企业版

首页 > 试题广场 >

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n

[问答题]

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n<10000)，有多少中组合可以组成n分钱？

spm

应该从硬币种类开始循环，如果是从从每个n开始，会出现重复情况，比如计算第三个（n=3）时，依次放入1 2 和 2 1 是重复得，却计算了2次。

def f(n):
    V = [1,2,5,10] A = [0,0,0]
    C = [0 for _ in range(n+1)]
    C[0] = 1    for v in V:  for i in range(v,n+1):  if i -v >=0:
                C[i] += C[i-v]  return C
n = int(input())
C = f(n) print(C[n])

发表于 2019-08-15 23:32:47 回复(0)

林某人

# 首先，1元只有一种表示方式[1]，2元有两种表示方式[2, (1)]，5元有四种表示方式[5, (2)]，10元有8种表示方式[10, (5), (5,2,1), (2), (1)]

# 对于任意的 n

a = n / 10
b = n % 10
c = b / 5
d = b % 5
e = d / 2
f  =  d  %  2

sum_numb = a*8 + c*4 + e*2 + f

发表于 2019-08-21 22:17:25 回复(1)

学而复始

def count_money(n):
    result = 0
    m = n+1
    for i in range(m):
        for j in range(int(m/2)+1):
            for a in range(int(m/5)+1):
                for b in range(int(m/10)+1):
                    if n == i + 2*j + 5*a + 10*b:
                        result += 1

    return result

发表于 2019-08-14 15:11:12 回复(2)

pein531

n = int(input())
# 背包问题
candidates = [1, 2, 5, 10]
dp = [0]*(n + 1)
for c in candidates:
    for i in range(c, n + 1):
        dp[i] += dp[i - c]
print(dp[n])

发表于 2021-02-19 12:04:40 回复(2)

201906112225646

n=int(input())
list=[]
for i in range(0,n+1):
    for j in range(0,n+1):
        for k in range(0,n+1):
            for l in range(0,n+1):
               if i*1+j*2+k*5+l*10==n:
                   list.append(i)
print(len(list))

发表于 2019-09-16 15:03:05 回复(0)

叶123456

class count():
count=0
list=[1,2,5,10]
def sum(self,n,a):
if a==n:
self.count+=1
return
if a>n:
return
for i in self.list:
a+=i
self.sum(n, a)
a-=i
return self.count

a=count()

n=8

print(a.sum(n, 0))

发表于 2019-08-31 15:20:50 回复(0)

海问香12138

先线下DP计算出所有情况的结果，再直接给出结果，这样可以允许多组输入。（题目只说n的上限，未给出下限，应提前对（n<1）的情况剪枝提高容错率）。该算法的时间复杂度为O(n),空间复杂度为O(n)。

#include <stdio.h>

#define MAXN 10010

int n;
int money[4]={1,2,5,10};
int dp[MAXN];

int main()
{
	int i,j;
	dp[0] = 1;
	for(i=1;i<MAXN;i++)
		for(j=0;j<4;j++)
			if(i>=money[j])
				dp[i] += dp[i-money[j]];
	while(scanf("%d",&n)!=EOF)
	{
		if(n>0)
			printf("%d\n",dp[n]);
		else
			puts("0");
	}
	return 0;
}

发表于 2019-08-14 21:00:48 回复(0)

提交观点

问题信息

C++工程师瓜子二手车算法工程师 2019 Java工程师

上传者：小小

难度：

7条回答 28收藏 2379浏览

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n

先线下DP计算出所有情况的结果，再直接给出结果，这样可以允许多组输入。（题目只说n的上限，未给出下限，应提前对（n<1）的情况剪枝提高容错率）。该算法的时间复杂度为O(n),空间复杂度为O(n)。

#include <stdio.h> #define MAXN 10010 int n; int money[4]={1,2,5,10}; int dp[MAXN]; int main() { int i,j; dp[0] = 1; for(i=1;i<MAXN;i++) for(j=0;j<4;j++) if(i>=money[j]) dp[i] += dp[i-money[j]]; while(scanf("%d",&n)!=EOF) { if(n>0) printf("%d\n",dp[n]); else puts("0"); } return 0; }

问题信息

热门推荐

相关试题