我最近面临着一个编程算法，我不知道该怎么做了提示。我从来没有真正写一个算法之前，所以我是那种对于新手在此。

I was recently faced with a prompt for a programming algorithm that I had no idea what to do for. I've never really written an algorithm before, so I'm kind of a newb at this.

这个问题说写一个程序来确定一个收银员来回馈为基础的硬币值和硬币的数量变化所有可能的硬币组合。例如，有可能是有4个硬币的货币：2分，6分，10分和15分硬币。怎么这么多的组合，即等于50美分有哪些？

The problem said to write a program to determine all of the possible coin combinations for a cashier to give back as change based on coin values and number of coins. For example, there could be a currency with 4 coins: a 2 cent, 6 cent, 10 cent and 15 cent coins. How many combinations of this that equal 50 cents are there?

我正在使用的语言是C ++，虽然这并不真正的问题太多了。

The language I'm using is C++, although that doesn't really matter too much.

编辑：这是一个更具体的编程问题，但我将如何分析一个字符串在C ++中获得的硬币价值？他们被赋予在一个文本文件如

edit: This is a more specific programming question, but how would I analyze a string in C++ to get the coin values? They were given in a text document like

4 2 6 10 15 50 

（其中，在这种情况下，数字对应于予给的例子）

(where the numbers in this case correspond to the example I gave)

推荐答案

这看起来有点像一个分区，只是你不使用的所有整数1:50。它似乎也类似于装箱问题有细微​​的差别：

This seems somewhat like a Partition, except that you don't use all integers in 1:50. It also seems similar to bin packing problem with slight differences:

维基百科：分区（数论） 百科：装箱问题 钨Mathworld：Partiton Wikipedia: Partition (Number Theory) Wikipedia: Bin packing problem Wolfram Mathworld: Partiton

其实，思考它后，它的的ILP ，从而NP难。

Actually, after thinking about it, it's an ILP, and thus NP-hard.

我会建议一些动态规划appyroach。基本上，你会定义一个值剩女，并将其设置为任何你的目标是（比方说，50）。然后，在每一步，你会做以下内容：

I'd suggest some dynamic programming appyroach. Basically, you'd define a value "remainder" and set it to whatever your goal was (say, 50). Then, at every step, you'd do the following:

在图什么，可以其余内适应最大硬币 在考虑会发生什么，如果你（A）包括的硬币或（B）不包括硬币。 对于每一个场景，递归。

因此​​，如果其余的是50，最大的硬币是值得25和10，你会跳转到两种情况：

So if remainder was 50 and the largest coins were worth 25 and 10, you'd branch into two scenarios:

1. Remainder = 25, Coinset = 1x25
2. Remainder = 50, Coinset = 0x25

（对于每个分支）下一步可能如下：

The next step (for each branch) might look like:

1-1. Remainder = 0,  Coinset = 2x25 <-- Note: Remainder=0 => Logged
1-2. Remainder = 25, Coinset = 1x25
2-1. Remainder = 40, Coinset = 0x25, 1x10
2-2. Remainder = 50, Coinset = 0x25, 0x10

每个分支将分成两个分支，除非：

Each branch would split into two branches unless:

其余为0（你会在这种情况下登录吧） 剩余比最小硬币更少（你会在这种情况下，放弃它） 有没有留下更多的硬币（你会在这种情况下，放弃它，因为剩下的！= 0）