1

我目前正在阅读一本关于算法设计的书，遇到了一个问题，即您必须使用动态规划实现一个贪心算法来解决硬币找零问题。

我试图实现这一点，但我无法弄清楚或理解我书中给出的算法。该算法如下（在评论中我（缺乏）理解）：

Change(p) {
  C[0] = 0
    for(i=1 to p) //cycling from 1 to the value of change we want, p
      min = infinity
        for(j=1 to k( //cyle from 1 to...?
          if dj <=i then
            if(1+C[i-dj] < min) then
               min = 1+C[i-dj]
            endif
          endif
        endfor
     C[i] = min
    endfor
  return C[p]
}

我试图解释正在发生的事情：

/**
     * 
     * @param d
     *            currency divisions
     * @param p
     *            target
     * @return number of coins
     */
    public static int change(int[] d, int p) {
        int[] tempArray = new int[Integer.MAX_VALUE]; // tempArray to store set
                                                        // of coins forming
                                                        // answer
        for (int i = 1; i <= p; i++) { // cycling up to the wanted value
            int min = Integer.MAX_VALUE; //assigning current minimum number of coints
            for (int value : d) {//cycling through possible values
                if (value < i) {
                    if (1 + tempArray[i - value] < min) { //if current value is less than min
                        min = 1 + tempArray[1 - value];//assign it
                    }
                }
            }
            tempArray[i] = min; //assign min value to array of coins
        }
        System.out.println("help"); // :(
        return tempArray[p];
    }

有人可以向我解释我缺少什么，如何解决这个问题，以及这个算法应该如何工作？动态编程似乎是一个非常有用的工具，但我无法理解它。我一直在递归地思考。

4

4 回答 4

0

动态规划的本质是将问题分解为子问题，然后开始向上构建解决方案。这个想法是，如果您解决“n”个子问题，您可以将它们组合起来，组合将成为整个问题的解决方案。递归是动态编程的一个例子，除了它存在潜在的堆栈溢出问题。另一种技术称为记忆化，它缓存结果以获得更快的查找时间，而不是重新计算已经计算的问题。这样可以节省大量处理并加快程序速度。至于贪心找零钱的问题，本质是寻找最大的面额，一直用到不能用为止（即 将总金额反复除以最大面额并记录余数）然后移至下一个最大值并重复相同的过程，直到剩下可以用最小面额表示的最低金额。您可以一直将最小值存储在一个数组中，并在找到新的最小值时继续更新它（即记忆化）。如果我在某个地方错了，我希望人们能纠正我。

编辑：但是请注意，并非所有问题都可以通过动态编程来解决，并且动态编程与任何编程语言都无关，它只是用于解决优化问题的技术的名称。

于 2011-10-30T15:03:59.357 回答
0

这似乎是硬件问题，所以我将给出一些指示。首先要通过 DP 解决问题是“思考顶部 Dwon 并自下而上解决”。

“自上而下” - 这是您制定递归关系的部分

例如：如果 n<1，则 T(n) = 0，否则为 T(n-1)；

递归关系依赖于先前计算的子问题。

“自下而上解决” - 这是您的代码将根据上面找到的递归关系自下而上解决问题的部分。

通常编码很简单，更难的部分是提出一个好的递归关系（虽然不会有递归）。

于 2011-10-30T16:20:55.903 回答
0

看到这个维基百科链接

摘录：

贪婪选择属性 我们可以做出目前看起来最好的任何选择，然后解决以后出现的子问题。贪心算法做出的选择可能取决于到目前为止所做的选择，但不取决于未来的选择或子问题的所有解决方案。它迭代地做出一个又一个贪婪的选择，将每个给定的问题减少为一个较小的问题。换句话说，贪心算法永远不会重新考虑它的选择。这是与动态规划的主要区别，动态规划是详尽的并且保证能找到解决方案。在每个阶段之后，动态规划都会根据前一阶段做出的所有决策做出决策，并且可能会重新考虑前一阶段的算法路径来解决问题。

您的代码遍历int p获取最佳选择并将其放入数组中，tempArray然后使用该值在下一次迭代中检查最佳选择。

于 2011-10-30T17:13:01.433 回答
0

聚会有点晚了，但你的功能已经奏效了。

public static int change(int[] d, int p) {
    // tempArray to store set of coins forming answer
    int[] tempArray = new int[Integer.MAX_VALUE];

    tempArray[0] = 0; // INITIAL STEP MISSING

    for (int i = 1; i <= p; ++i) { // cycling up to the wanted value
        // assigning current minimum number of coins
        int min = Integer.MAX_VALUE;

        // cycling through possible values
        for (int value : d) {

            if (value <= i) { // FIX missing = in <=

                // if current value is less than min
                if (1 + tempArray[i - value] < min) {

                    // FIX, it's [i-value] not [1-value]
                    min = 1 + tempArray[i - value];
                }
            }
        }
        tempArray[i] = min; // assign min value to array of coins
    }
    return tempArray[p];
}

并使用它。

public static void main(String[] args) {
    int[] coins = new int[] { 25, 12, 10, 5, 1 };

    int coinCount = change(coins, 15);
    System.out.println("min change: " + coinCount);
}
于 2015-03-31T01:21:13.700 回答