java动态规划，背包问题（解决最优选择方案）

比眉伴天荒 2023-06-06 10:55 115阅读 0赞

简言：

** 动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。**  
    解决动态规划问题的关键是要找到状态转移方程。将问题分解成最小的子问题，找到由子问题到全局问题的解决方案。

>     可以采用动态规划求解的问题的一般要具有3个性质：  
>     (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。  
>     (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。  
>    （3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）。

>     求解动态规划问题的基本步骤：  
>     （1）分析最优解的性质，并刻画其结构特征。  
>     （2）递归的定义最优解。  
>     （3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值  
>     （4）根据计算最优值时得到的信息，构造问题的最优解
> 
>

最近公司做一个功能，关于优惠券的多选问题：

问题描述：优惠券可以多选，但是需要匹配最优的方案，匹配时不能大于订单金额：

顿时头大无比，因为订单金额不固定，最后查阅资料，找到解决办法，通过动态规划的方式解决该问题，并作出分享：

代码展示：（附带说明）

int n = 3;    //优惠券个数
            int w = 600;    //订单金额
    
            int value[] = {6, 10, 120};        //优惠券优惠金额
            int weight[] = {100, 200, 400};        //优惠券满减金额
    
    
            int dp[][] = new int[n + 1][w + 1];        //表示分割，成一个 小的表格
    
            for (int i = 1; i <= n; i++) {        //表示优惠券往容器里面加
                for (int cw = 1; cw <= w; cw++) {    //袋子在每一个容积下所装的最大的钱=优惠券
                    if (weight[i - 1] <= cw) {        //表示这个优惠券可以装
                        dp[i][cw] = Math.max(
                                value[i - 1] + dp[i - 1][cw - weight[i - 1]],        //我装新加的优惠券
                                dp[i - 1][cw]        //我不装这个新加的优惠券
                        );
                    } else {
                        dp[i][cw] = dp[i - 1][cw];        //新加的这个装不下 ，那么就取前一个优惠券装值
                    }
                }
            }
            System.out.println("优惠券的最大价值:" + dp[n][w]);

得到的结果：

![20191011143124949.png][]

[20191011143124949.png]: /images/20230601/606a391794c74e2c936530e592956404.png