0%

动态规划和回溯算法

发表于 更新于 分类于 阅读次数：
简介

前几天在朋友圈中看到一个富士康面试题，题目是9个球放入4个袋子，如何保证每个袋子都有球且每个袋子中的球是单数。正好这几天又巩固下基础算法，想到个题不是可以用回溯和动态规划去解决吗？其实算法一个非常重要的东西就是建模，如果将现实中的东西抽象成模型，这个问题我们可以将其模型抽象成一个二维数据，一维代表背包的个数，二维代表一个包的所放的球数，对于不同算法，这个模型也有着不同含义，比如对于动态规划，同样使用二维数组去建模，动态规划二维数组代码的确实现在包中一共放了多少个球，另外数组加链表也是一种常用的建模工具，类似HashMap就使用了数组加链表来存储hash冲突的数据，在计算图相邻顶点时我们也会使用这种数据结构，数组下标代表的是当前点，数组中又加了一个链表来存储这个顶点相邻的点。

回溯算法

简单的来说回溯算法就是列举出所有可能性，选出一个满足条件的结果。就好比我们走迷宫，当我们遇到一条死路就原路返回到上一个入口，然后接着走，直到我们找到出口，所以顾名思义这个算法就叫回溯。我们知道贪心算法不能得出最优解，但是使用回溯我们列举出所以的可能，然后从中筛选出一个最优解即可。

回溯算法是我遇到这个问题的第一个想到的解法,解决的思路就是我们根据常理得出要保证每个包就有球，那么每个包最少要有1个球，那么得出一个包最多只能有6个球，那么我们我们可以使用递归去实现，一个包最多放6个球，我们列举出这4个包从放1个球到6个球的所有可能，并且其它包要根据之前包放的球个数的变化二改变最多可以放的球数量的变化，实现这个是这个算法最绕的地方，为了将这个题目抽象成代码我用一个二维数组来建模，一维表示包的编号(从0-4)，二维数组的下标表示当前背包中有多少个球，如果当前坐标维true，那么这个背包中就有多少个球(二维数组的下标)，具体代码如下,

最后得出根本不存在这样的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package com.nebula.orderpublish;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringJoiner;

/**
 * @author Liush
 * @description
 * @date 2021/7/9 14:40
 **/
public class Main {

    static List<String> results=new ArrayList<>();

    public static void main(String[] args) {

        calculate(4,9);
        System.out.println(results);

    }

    public static void calculate(int bagNum ,int ballNum){

        
        getBallNumPut(6,1,4,new int[4],ballNum);

    }

   
    

    public static void getBallNumPut(int currentBagBallNumMax, int currentBag, int bags, int[] result, int ballNum){
        //递归结束条件当袋子都遍历完时
        if(currentBag==bags){
            int lastBagBallNum=ballNum- getBallNumPut(result);
            if(lastBagBallNum%2==0){
                return;
            }
            result[currentBag-1]=ballNum- getBallNumPut(result);
            results.add(Arrays.toString(result));
            return;
        }
        for(int i=0;i<currentBagBallNumMax;i++){
            clean(result,currentBag);
            //查询时候为偶数，如果是偶数的话跳过
            if((i+1)%2==0){
                continue;
            }
            //保存当前袋子中所放球的个数
            result[currentBag-1]=i+1;
            int nextBagBallNum= countNextBagBallsMax(result,ballNum,currentBag,bags);
            getBallNumPut(nextBagBallNum,currentBag+1,bags, result,ballNum);

        }




    }

    //清除结果，每次不满足条件(偶数)时吧结果清除，循环回溯去排查下一个结果
    public static void clean(int[] results,int currentLevel){
        for(int i=0;i<results.length;i++){
            if(i>=currentLevel-1){
                results[i]=0;
            }
        }

    }

    //计算本次计算的单个袋子最多可以放多少个球
    public static int countNextBagBallsMax(int[] results, int balls, int currentLevel, int level){
        int ballNumPut = getBallNumPut(results);
        //+1 是为了计算最少还要预留多少个球放入后面的袋子 比如4个袋子当前是第一个袋子，现在要计算第二个袋子，就至少还要预留2个球(3和4袋子)才能保证每个袋子都有球
        return balls-ballNumPut-(level-currentLevel)+1;

    }

    //查询已经放入袋子的球
    private static int getBallNumPut(int[] results) {
        int result=0;
        for(int a: results){
            result+=a;
        }
        return result;
    }


}
动态规划

能使用动态规划解决问题一般都满足以下三个原则

  1. 最优子结构最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。
  2. 无后效性无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
  3. 重复子问题这个概念比较好理解。前面一节，我已经多次提过。如果用一句话概括一下，那就是，不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

这个问题可以满足这3个条件，于是我尝试使用动态规划去解决此问题,不同于回溯，我用二维数组来建模，一位数组同样代表的是背包编号，不同的是二维数组，我使用二维数组的下标来表示目前一共在包中放入了多少个球，根据动态规划的定义，我把问题分解为4个重复的子问题，就是每个包要放入多少个球，我们把每个包中放的球的所有可能都列举出来，并且将所有背包里的球的数量累加(这是数组的二维不是代表本个袋子放了多少个球，而是代表这个袋子放好后，一共装到袋子的球有多少个)，最后相加发现根本不可能放入9个球（二维数组的[3][8]坐标为0）

0 1 2 3 4 5 6 7 8
0 √ √ √
1 √ √ √
2 √ √ √
3 √ √ √ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * @author Liush
 * @description
 * @date 2021/7/12 16:04
 **/
public class Main2 {


        public static void main(String[] args) {

            int[][] matrix=new int[4][9];
            int everyBagBallMax=getEveryBagBallMax(9,4);
            for(int i=0;i<matrix.length;i++){
                //初始化第一个背包
                if(i==0){
                    for(int z=0;z<everyBagBallMax;z++){
                        if((z+1)%2==0){
                            continue;
                        }
                        matrix[0][z]=1;
                    }
                    continue;
                }

                //根据上一个放入球的背包计算本次背包能放入多少个球
                for(int k=0;k<matrix[i].length;k++){
                    if(matrix[i-1][k]>0){
                        //计算本个背包最多能放多少个球4-（i+1）为计算后面没放球的背包，每个背包最少要放一个，K+1为已经放入的球树
                        int cycleTime=9-(4-(i+1))-(k+1);
                        for(int c=1;c<=cycleTime;c++){
                            if(c%2==0){
                                continue;
                            }
                            matrix[i][k+c]=1;

                        }

                    }

                }

            }

            System.out.println(matrix);

        }
        

        //计算出每层最多可以放几个球
        public static int getEveryBagBallMax(int ballNum ,int bagNum){


            return ballNum-bagNum+1;

        }




}