高效的动态规划算法应用案例

1.前言：动态规划与分治算法类似，递归求解子问题，再组合子问题来求解。但动态规划在子问题有重叠的情况下有优势。动态规划算法用于求解最优化问题，所求解的问题需要满足最优子结构性质：问题最优解由相关子问题的最优解组合而成。

2.动态规划的两种实现方式：

    2.1 带备忘的自顶向下法

           所谓的带备忘，即保存每一个子问题的解，在下次用时直接取出而不需要重新计算，从而提高效率。

    2.2 自底向上法

          即任何子问题的求解，只依赖于规模更小的子子问题的求解。由于是从小到大的规模顺序求解，即在计算子问题时，它的所有依赖的更小的子问题已经求解且保存，不需重新计算，从而提高效率。

3.钢条切割最优化求解（算法导论上的）

问题描述：给定钢条长度n和一个价格表p,求切割方案，使得销售收益r最大。

建立数学模型：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;
	}
}

最后

以上就是鲜艳钻石为你收集整理的高效的动态规划算法应用案例的全部内容，希望文章能够帮你解决高效的动态规划算法应用案例所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。