赞
踩
1.前言:动态规划与分治算法类似,递归求解子问题,再组合子问题来求解。但动态规划在子问题有重叠的情况下有优势。动态规划算法用于求解最优化问题,所求解的问题需要满足最优子结构性质:问题最优解由相关子问题的最优解组合而成。
2.动态规划的两种实现方式:
2.1 带备忘的自顶向下法
所谓的带备忘,即保存每一个子问题的解,在下次用时直接取出而不需要重新计算,从而提高效率。
2.2 自底向上法
即任何子问题的求解,只依赖于规模更小的子子问题的求解。由于是从小到大的规模顺序求解,即在计算子问题时,它的所有依赖的更小的子问题已经求解且保存,不需重新计算,从而提高效率。
3.钢条切割最优化求解(算法导论上的)
问题描述:给定钢条长度n和一个价格表p,求切割方案,使得销售收益r最大。
长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
价格p | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
建立数学模型:r(n)=max(p(i)+r(n-i)); 其中i=1,2,...n
说明:我们将钢条从左边切割下长度为i的一段,只对右边剩下的n-i长度来继续进行切割。即原问题最优解只包含一个子问题解(右端剩余部分),而不是两个。
java代码如下:
- package com.talkweb.test01;
-
- import java.util.Arrays;
-
- /**
- * 动态规划运用案例
- * 钢条切割
- * @author Administrator
- *
- */
- public class DynamicProgram {
-
-
- public static void main(String[] args){
- int[] p={-1,1,5,8,9,10,17,17,20,24,30};//下标对应钢条长度,值对应收益,下标从1开始
- DynamicProgram dp=new DynamicProgram();
-
- //1.初始化r
- int[] r=new int[p.length];
- for(int i=0;i<r.length;i++){
- r[i]=-1;
- }
- //2.调用方法求解
- int n=7;//需要切割的钢条长度
- int m=dp.iterationValue(p,n, r);//带备忘自顶向下
- System.out.println("带备忘自顶向下 m="+m);
- dp.printBottom_up(p,n); //自底向上
- }
- /**
- * 自顶向下递归求解:递归计算当前长度为n的钢条的最优值
- * @param p钢条对应收益数组
- * @param n当前钢条长度
- * @param r记录最优值
- */
- public int iterationValue(int[] p,int n,int[] r){
- if(r[n]>=0){//若已记录当前长度n的最优值,则直接返回
- return r[n];
- }
- //若当前长度n为0则最优值为0
- if(n==0){
- return 0;
- }
- int s=-1;//记录当前n做一次切割各种方案的最优值
- for(int i=1;i<=n;i++){//遍历当前长度,即当前长度的各种切割方案
- s=max(s,p[i]+iterationValue(p,n-i,r));
- }
- //保存当前长度n的最优值
- r[n]=s;
- return s;
- }
- public int max(int s,int t){
- return s>t?s:t;
- }
- /**
- * 自底向上非递归求解
- * @param p
- * @return
- */
- public int[] bottom_up(int[] p,int n){
- int[] r=new int[n+1]; //保存最优值
- int[] s=new int[n+1]; //保存最优切割方案
- for(int j=1;j<=n;j++){
- int q=-1; //记录钢条长度为j时的最优值
- for(int i=1;i<=j;i++){ //对长度为j的钢条做一次切割
- if(q<p[i]+r[j-i]){
- q=p[i]+r[j-i]; //保存较大值
- s[j]=i; //保存当前长度为j的最佳切割长度i
- }
- }
- r[j]=q; //保存钢条规模长度为j的最佳收益值
-
- }
- System.out.println("自底向上 最优收益:"+r[n]);
- return s; //返回钢条长度为n时的最佳收益值
- }
-
- public void printBottom_up(int[]p,int n){
- int[]s=bottom_up(p,n);
- System.out.println("切割方案:");
- while(n>0){
- System.out.print(s[n]+" ");
- n=n-s[n];
- }
- System.out.println();
- }
- }
4.商品折扣最优购买方案的优惠总额(只是简单的自顶向下实现,没有用到动态规划)
- package com.talkweb.arithmetic;
-
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.List;
-
- /**
- * 商品折扣最优购买方案
- * @author Administrator
- *
- */
- public class GoodsDiscount {
-
- public static void main(String[] args){
- //1.折扣集合
- List<ZheKou> zks=new ArrayList<ZheKou>();
- zks.add(new ZheKou(0,"0",0,0));
- zks.add(new ZheKou(1,"折扣1",30,6));
- zks.add(new ZheKou(3,"折扣2",60,15));
- zks.add(new ZheKou(2,"折扣3",99,20));
-
- GoodsDiscount gd=new GoodsDiscount();
- double money=100;
- int[] s=new int[zks.size()];
- System.out.println("优惠总额:"+gd.fun(zks,money,0));
- }
-
- /**
- * 递归计算最多优惠额
- * @param zks商品折扣
- * @param money余额
- * @return最多优惠额
- */
- public double fun(List<ZheKou> zks,double money,double youhui){
- //1.若余额不足以购买任何折扣,则返回优惠额
- boolean flag=false;
- for(int i=1;i<zks.size();i++){
- if(zks.get(i).getPrice()<money){
- flag=true;
- }
- }
- if(!flag){
- return youhui;
- }
-
- //2.迭代可以购买每一种折扣,计算并记录当前购买最大优惠额
- double max=0;
- for(int i=1;i<zks.size();i++){
- if(money>zks.get(i).getPrice()){
- //计算购买1件第i种折扣优惠额
- max=maxValue(max,fun(zks,money-zks.get(i).getPrice()+zks.get(i).getYhPrice(),youhui+zks.get(i).getYhPrice()));
- }
- }
- //保存优惠额
- youhui=max;
- return youhui;
- }
-
- public double maxValue(double m,double y){
- return m>y?m:y;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。