动态规划之找零钱问题与背包问题

电玩女神 2022-06-10 05:13 279阅读 0赞

首先，个人对动态规划的理解就是一句话：找规律，找出状态转移方程，找出判决条件之后进行迭代

# 找零钱问题 #

用一个实际例子来体现动态规划的算法思想——硬币找零问题。  
硬币找零问题描述：现存在一堆面值为 V1、V2、V3 … 个单位的硬币，问最少需要多少个硬币才能找出总值为 T 个单位的零钱？假设这一堆面值分别为 1、2、5、21、25 元，需要找出总值 T 为 63 元的零钱。  
很明显，只要拿出 3 个 21 元的硬币就凑够了 63 元了。  
基于上述动态规划的思想，我们可以从 1 元开始计算出最少需要几个硬币，然后再求 2 元、3元…每一次求得的结果都保存在一个数组中，以后需要用到时则直接取出即可。那么我们什么时候需要这些子问题的解呢？如何体现出由子问题的解得到较大问题的解呢？  
其实，在我们从 1 元开始依次找零时，可以尝试一下当前要找零的面值（这里指 1元）是否能够被分解成另一个已求解的面值的找零需要的硬币个数再加上这一堆硬币中的某个面值之和，如果这样分解之后最终的硬币数是最少的，那么问题就得到答案了。  
单是上面的文字描述太抽象，先假定以下变量：  
values\[\] : 保存每一种硬币的币值的数组  
valueKinds :币值不同的硬币种类数量，即values\[\]数组的大小  
money : 需要找零的面值  
coinsUsed\[\] : 保存面值为 i 的纸币找零所需的最小硬币数  
算法描述：

public class CoinsChange {
              
            /**    
             * 硬币找零：动态规划算法    
             *     
             * @param values    
             *            :保存每一种硬币的币值的数组    
             * @param valueKinds    
             *            :币值不同的硬币种类数量，即coinValue[]数组的大小    
             * @param money    
             *            :需要找零的面值    
             * @param coinsUsed    
             *            :保存面值为i的纸币找零所需的最小硬币数    
             */     
            public static void makeChange(int[] values, int valueKinds, int money,      
                    int[] coinsUsed) {      
    
                coinsUsed[0] = 0;      
                // 对每一分钱都找零，即保存子问题的解以备用，即填表      
                for (int cents = 1; cents <= money; cents++) {      
    
                    // 当用最小币值的硬币找零时，所需硬币数量最多      
                    int minCoins = cents;      
    
                    // 遍历每一种面值的硬币，看是否可作为找零的其中之一      
                    for (int kind = 0; kind < valueKinds; kind++) {                   
                        // 若当前面值的硬币小于当前的cents则分解问题并查表      
                        if (values[kind] <= cents) {      
                            int temp = coinsUsed[cents - values[kind]] + 1;      
                            if (temp < minCoins) {      
                                minCoins = temp;      
                            }      
                        }      
                    }      
                    // 保存最小硬币数      
                    coinsUsed[cents] = minCoins;      
    
                    System.out.println("面值为 " + (cents) + " 的最小硬币数 : "     
                            + coinsUsed[cents]);      
                }      
            }      
    
            public static void main(String[] args) {      
    
                // 硬币面值预先已经按降序排列      
                int[] coinValue = new int[] { 25, 21, 10, 5, 1 };      
                // 需要找零的面值      
                int money = 63;      
                // 保存每一个面值找零所需的最小硬币数，0号单元舍弃不用，所以要多加1      
                int[] coinsUsed = new int[money + 1];      
    
                makeChange(coinValue, coinValue.length, money, coinsUsed);      
            }      
        }

# 背包问题 #

背包问题具体例子：假设现有容量10kg的背包，另外有3个物品，分别为a1，a2，a3。物品a1重量为3kg，价值为4；物品a2重量为4kg，价值为5；物品a3重量为5kg，价值为6。将哪些物品放入背包可使得背包中的总价值最大？

首先想到的，一般是穷举法，一个一个地试，对于数目小的例子适用，如果容量增大，物品增多，这种方法就无用武之地了。

其次，可以先把价值最大的物体放入，这已经是贪婪算法的雏形了。如果不添加某些特定条件，结果未必可行。

最后，就是动态规划的思路了。先将原始问题一般化，欲求背包能够获得的总价值，即欲求前i个物体放入容量为m（kg）背包的最大价值c\[i\]\[m\]——使用一个数组来存储最大价值，当m取10，i取3时，即原始问题了。而前i个物体放入容量为m（kg）的背包，又可以转化成前(i-1)个物体放入背包的问题。下面使用数学表达式描述它们两者之间的具体关系。

表达式中各个符号的具体含义。

w\[i\] : 第i个物体的重量；

p\[i\] : 第i个物体的价值；

c\[i\]\[m\] ： 前i个物体放入容量为m的背包的最大价值；

c\[i-1\]\[m\] ： 前i-1个物体放入容量为m的背包的最大价值；

c\[i-1\]\[m-w\[i\]\] ： 前i-1个物体放入容量为m-w\[i\]的背包的最大价值；

由此可得：

c\[i\]\[m\]=max\{c\[i-1\]\[m-w\[i\]\]+pi , c\[i-1\]\[m\]\}  
　根据上式，对物体个数及背包重量进行递推，列出一个表格（见下表），表格来自（[http://blog.csdn.net/fg2006/article/details/6766384?reload][http_blog.csdn.net_fg2006_article_details_6766384_reload]） ，当逐步推出表中每个值的大小，那个最大价值就求出来了。推导过程中，注意一点，最好逐行而非逐列开始推导，先从编号为1的那一行，推出所有c\[1\]\[m\]的值，再推编号为2的那行c\[2\]\[m\]的大小。这样便于理解。

![这里写图片描述][SouthEast]

public class BackPack {
        
        public static void main(String[] args) {
            int m = 10;
            int n = 3;
            int w[] = {
       3, 4, 5};
            int p[] = {
       4, 5, 6};
            int c[][] = BackPack_Solution(m, n, w, p);
            for (int i = 1; i <=n; i++) {
                for (int j = 1; j <=m; j++) {
                    System.out.print(c[i][j]+"\t");
                    if(j==m){
                        System.out.println();
                    }
                }
            }
            //printPack(c, w, m, n);
    
        }
    
     /**
         * @param m 表示背包的最大容量
         * @param n 表示商品个数
         * @param w 表示商品重量数组
         * @param p 表示商品价值数组
         */
        public static int[][] BackPack_Solution(int m, int n, int[] w, int[] p) {
            //c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值
            int c[][] = new int[n + 1][m + 1];
            for (int i = 0; i < n + 1; i++)
                c[i][0] = 0;
            for (int j = 0; j < m + 1; j++)
                c[0][j] = 0;
    
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < m + 1; j++) {
                    //当物品为i件重量为j时，如果第i件的重量(w[i-1])小于重量j时，c[i][j]为下列两种情况之一：
                    //(1)物品i不放入背包中，所以c[i][j]为c[i-1][j]的值
                    //(2)物品i放入背包中，则背包剩余重量为j-w[i-1],所以c[i][j]为c[i-1][j-w[i-1]]的值加上当前物品i的价值
                    if (w[i - 1] <= j) {
                        if (c[i - 1][j] < (c[i - 1][j - w[i - 1]] + p[i - 1]))
                            c[i][j] = c[i - 1][j - w[i - 1]] + p[i - 1];
                        else
                            c[i][j] = c[i - 1][j];
                    } else
                        c[i][j] = c[i - 1][j];
                }
            }
            return c;
        }

运行结果：

0    4    4    4    4    4    4    4    4    
       0    4    5    5    5    9    9    9    9    
       0    4    5    6    6    9    10    11    11    
    
    Process finished with exit code 0

个人觉得动态规划的思维还需要慢慢适应，需要从懒惰的“暴力列举”的想法中走出来，去习惯适应状态转移和更新迭代的想法。

[http_blog.csdn.net_fg2006_article_details_6766384_reload]: http://blog.csdn.net/fg2006/article/details/6766384?reload
[SouthEast]: /images/20220610/2e20f16e42b84f7dbd1cdfbaae122158.png