我想知道算法的硬币找零问题，在不同面额有infinte硬币数量的想法。是指如何应用DP（像标准的硬币找零的问题） 对于例如在设置中的1,10,15， 变化35给 - 2硬币10和15一枚硬币

I want to know the idea of algorithm for the coin change problem where each denomination has infinte number of coins. Means how to apply DP (like the standard coin change problem) For e.g in set 1,10,15, change for 35 gives--2 coins of 10 and one coin of 15

另外给我暴力破解算法这样的想法。我知道遍历所有的集合。但如何改变每个硬币的数量，同时暴力破解

Also give me an idea of brute forcing algorithm for this. I know to iterate over all the sets. But how to vary the number of each coin while brute forcing

推荐答案

我会考虑构建解决方案一步一步时，电感：

I would think about building the solution one step at a time, inductively:

可用硬币有1℃，5℃，10℃，25℃（你可以根据你的需要调整它们）

Coins available are 1c, 5c, 10c, 25c (you can tweak them according to your needs)

如果你能感应制定的问题，可能更容易解决了。

If you can formulate the problem inductively, it might be easier to tackle it.

编辑： 好吧，这里的另一个试图解释的动态规划的解决方案：

Alright, here's another attempt to explain the dynamic programming solution:

思考与表的X 行（ X 是不同的教派号）和 N 列（ N 是，你必须建立使用最低面值金额）。在此表重新$ P $的每一个细胞psents一个独特的子问题，并最终将包含解决它。假设：

Think of a table with x rows (x is number of distinct denominations) and n columns (n is the amount you have to build using least denominations). Every cell in this table represents a distinct sub-problem and will eventually contain the solution to it. Assume:

第1行重新presents集 {1C} 即第1行中，你被允许使用无限 1C 第2行再presents集 {1℃，10℃} 即第2行你被允许无限 1C 和 10℃ 排3重presents集 {1℃，10℃，15℃} 等等... 再$ P $每列psents要构建的金额。

row 1 represents the set {1c} i.e. in row 1 you are allowed to use infinite 1c row 2 represents the set {1c, 10c} i.e in row 2 you are allowed to infinite 1c and 10c row 3 represents the set {1c, 10c, 15c} and so on... Each column represents the amount you want to construct.

因此​​，每个单元对应于一个小的子问题。例如（该索引从1开始为简单起见）， 细胞（1,5） ==>构建 5C 只使用 {1C} 细胞（2,9） ==>构建 9C 使用 {1℃，10℃} 单元（3，27） ==>构建 27℃使用 {1℃，10℃，15℃ } 现在，你的目标是获得答案单元（X，N）

Thus, every cell corresponds to one small sub-problem. For example (the indexes are starting from 1 for the sake of simplicity), cell(1, 5) ==> construct 5c using only {1c} cell(2, 9) ==> construct 9c using {1c, 10c} cell(3, 27) ==> construct 27c using {1c, 10c, 15c} Now your aim is to get the answer to cell(x, n)

解决方法： 开始从最简单的解决问题的表。解决第一个行是微不足道的，因为第一行中唯一可用的面额为 {1C} 。第1行中的每个单元都有一个简单的解决方案，从而单元（1，N） = {nx1c} （ N 的硬币 1C ）。

Solution: Start solving the table from the simplest problem. Solving the first row is trivial, since in the first row the only denomination available is {1c}. Every cell in row 1 has a trivial solution, leading to cell(1, n) = {nx1c} (n coins of 1c).

现在进入到下一行。概括为第二排，让我们看看如何来解决（说）电池（2，28）即构建 28℃使用 {1℃，10℃} 。在这里，你必须做出决定，是否包括 10℃于溶液中或没有，有多少硬币。你有3种选择（3 = 28/10 + 1）

Now proceed to the next row. Generalizing for the 2nd row, lets see how to solve for (say) cell(2, 28) i.e. construct 28c using {1c, 10c}. Here, you need to make a decision, whether to include 10c in the solution or not, and how many coins. You have 3 choices (3 = 28/10 + 1)

选择1 ： 以 {1x10c} 从previous行的其余部分（存储在单元（1，18））。这使您 {1x10c，18x1c} = 19金币

Choice 1: Take {1x10c} and the rest from the previous row (which is stored in cell(1, 18)). This gives you {1x10c, 18x1c} = 19 coins

选择2 ： 以 {2x10c} 和previous行的其余部分（存储在单元（1，8） ）。这使您 {2x10c，8x1c} = 10金币

Choice 2: Take {2x10c} and the rest from previous row (which is stored in cell(1, 8)). This gives you {2x10c, 8x1c} = 10 coins

选择3 ： 拿不出 10℃从previous行的其余部分（存储在单元（1，28） ）。这使您 {28x1c} = 28金币

Choice 3: Take no 10c and the rest from the previous row (which is stored in cell(1, 28)). This gives you {28x1c} = 28 coins

显然，选择2是最好的，因为它需要较少的硬币。把它写在表中，然后继续前进。表是待填充的一行的时间，和一排内，在增加量的顺序

Clearly, choice 2 is the best as it takes less coins. Write it down in the table and proceed ahead. The table is to be filled one row at a time, and within a row, in the order of increasing amounts.

经过，你会到达单元（X，N），解决这将是 N / P +之间做出选择1 的替代品，其中 P =最新面额行 X 。最好的选择是你的答案。

Going by above rules, you will reach cell(x, n), the solution to which will be a choice between n/p + 1 alternatives, where p = newest denomination in row x. The best choice is your answer.

表实际上memoizes的解决方案，以较小的问题，这样你就不必一次又一次地解决这些问题。

The table actually memoizes the solutions to smaller problems, so that you don't need to solve them again and again.