首页 > 试题广场 >

牛牛的超市

[编程题]牛牛的超市

定义一种新货币，有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个。现在你有 x(x<=100) 元，但是你想将 x 元换成若干零钱，请问有多少种换钱的方案？

示例1

输入

2,10,[[1, 5],[ 2, 4]]

10元可以由 2张1元的和4张2元的组成，也可以由4张1元的和3张2元的组成

x可以不属于n种币值之一

算法知识视频讲解

Peterliang

发表于 2021-09-14 23:52:21

题意分析给你一个序列，我们需要选取其中几个数字拼接成一个固定的数字，问不同的拼接方案？思路分析 DP 解法一首先，我们来分析一下，这个题目需要n种数字拼接成一个固定的数字x，假设我们当前已经知道了前i-1种数字的情况凭借成x的方案数，那么当我们枚举到第i种数字的时候，我们拼接的方案数就可展开全文

摸鱼学大师

发表于 2021-08-23 17:02:38

思路：题目的主要信息：有n种不同面值的货币，面值大小和数量记录在数组a中问将x元换成若干零钱的种类有多少，x可以不为货币面值方法一：动态规划具体做法：使用动态规划，设表示用前种货币凑出金额为的方案数量，初始时，因为每种面值的货币的数量有限，我们要枚举每一个出现的可能数量。则用前种货币凑出展开全文

球球了给孩子一个offer吧

发表于 2021-08-21 18:57:21

题目：定义一种新货币，有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个。现在你有 x(x<=100) 元，但是你想将 x 元换成若干零钱，请问有多少种换钱的方案？方法一：动态规划这是背包问题的变形，我们可以定义dp[i] 展开全文

xqxls

发表于 2021-08-24 13:23:57

题意整理有n种不同的货币，给定每种货币的面值和个数。现在要将x元兑换为这些货币的组合，求总共有多少种方案。方法一（动态规划） 1.解题思路这是一个典型的背包问题，x元是背包容量，根据面值以及个数限制逐个推导出每种金额x对应的方案数。状态定义：表示i种币值下，j元的金额有多少换钱方案。展开全文

开车的阿Q

发表于 2021-09-05 21:46:20

描述这是一篇面对初级coder的题解。知识点：动态规划难度：三星题解题目：定义一种新货币，有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个。现在你有 x(x<=100) 元，但是你想将 x 展开全文

动态规划基础数学

难度：

5条回答 22收藏 5487浏览

查看代码