当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

编程之美-饮料供货-动态规划

发表于: 2012-07-20   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Arrays; import java.util.Random; public class BeverageSupply { /** * 编程之美 饮料供货 * 设Opt(V’,i)表示从i到n-1种饮料中,总容量为V’的方案中,满意度之和的最大值。 * 那么递归式就应该是:Opt(V’,i)=max{ k * Hi+Op

import java.util.Arrays;
import java.util.Random;

public class BeverageSupply {

	/**
	 * 编程之美 饮料供货
	 * 设Opt(V’,i)表示从i到n-1种饮料中,总容量为V’的方案中,满意度之和的最大值。
	 * 那么递归式就应该是:Opt(V’,i)=max{ k * Hi+Opt(V’-Vi * k,i+1)}(k=0,1,2…,Ci,i=0,1,2…,n-1)
	 * 其中Ci为第i种饮料的最大供应量
	 * 
	 * 想了好久都没法理解书上这个递推公式里面的i+1,为什么是i+1而不是其他?
	 * 后来我转换了一下,代码本质上是一样的,只是比较符合我自己的思路:
	 * opt[i][j] i代表供货总容量,j代表饮料种类。假设容量都是整数。i和j都从1开始考虑:
	 * 当只有一种饮料时,容易求得各种总容量对应的最大满意度;当新增加一种饮料时,将一部分容量用新饮料代替,求得新的满意度;
	 * 将新的满意度与旧满意度比较,如果新结果较大就更新。
	 * 如何由opt[i][j-1]求得opt[i][j]呢?
	 * --将一部分容量分给第j种饮料,那新的满意度就是(opt[i-k*v][j]+k*value),其中v代表第j种饮料每瓶的容量,k代表瓶数,value代表满意度
	 */
	
	public static void main(String[] args) {
		int T=3;
		int V=10;
		BeverageSupply beverageSupply=new BeverageSupply();
		Beverage[] beverages=beverageSupply.initBeverage(V, T);
		int maxValue=beverageSupply.maxValue(beverages,V, T);
		System.out.println("总容量:"+V+" 最大满意度="+maxValue);
	}
	
	public int maxValue(Beverage[] beverages,int V,int T){
		
		if(beverages==null||beverages.length==0){
			return -1;
		}
		if(V<0){
			return -1;
		}
		if(T<0 || T>beverages.length){		//beverages' index starts with 1
			return -1;
		}
		
		int[][] opt=new int[V+1][T+1];
	
		for(int j=1;j<=T;j++){
			int c=beverages[j].count;
			int v=beverages[j].volume;
			int value=beverages[j].value;
			for(int i=1;i<=V;i++){
				for(int k=0;k<=c;k++){
					if(i<k*v){
						break;
					}
					int x=opt[i-k*v][j-1];
					int y=x+k*value;
					if(y>=opt[i][j]){
						opt[i][j]=y;
					}
				}
			}
		}
//		myprint(opt);
		return opt[V][T];
	}
	
	static class Beverage{
		int value;		//满意度
		int volume;		//每瓶的容量
		int count;		//最多可提供多少瓶
		Beverage(int value,int volume,int count){
			this.value=value;
			this.volume=volume;
			this.count=count;
		}
	}
	
	public Beverage[] initBeverage(int V,int T){
		if( V<0 || T<0 ){
			return new Beverage[0];
		}
		Beverage[] beverages=new Beverage[T+1];
		Random random=new Random();
		System.out.println("满意度	容量(每瓶)	最多可提供数量(瓶)");
		for(int i=0;i<T;i++){
			//value volume count随机生成
			int value=random.nextInt(T)+1;
			int volume=random.nextInt(V/2)+1;
			int count=random.nextInt(V/2)+1;
			beverages[i+1]=new Beverage(value,volume,count);
			System.out.println(value+"		"+volume+"		"+count);
		}
		return beverages;
	}
	
	public void myprint(int[][] array){
		if(array!=null){
			for(int[] a:array){
				System.out.println(Arrays.toString(a));
			}
		}
	}
}



编程之美-饮料供货-动态规划

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目地址:http://poj.org/problem?id=2411 编程之美的课后题也有一个和整个题目一样的。(P269) 题
问题定义(动态规划) 如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义"
题目地址:http://poj.org/problem?id=2411 编程之美的课后题也有一个和整个题目一样的。(P269) 题
3、题目:能否快速找出一个数组(简单起见,数组中元素值各不一样)中的两个数字,让这两个数字之和
今天开始看编程之美 。第一个问题是CPU的使用率控制,微软的问题果然高大上,我一看就傻了,啥也不
第一章 软件架构是什么 软件架构应该... asoftware architect that the system should be friendly
给定一个前序和中序变量的结果,写一个算法重建这棵树:如: 前序: a b d c e f 中序: d b a e c f
还好看到了,这个以前好早见到过。 用得是辗转相除法。 k =x/y b=x%y 则 x = ky+b 如果一个整数能够
题目:编写一个函数,把一个char组成的字符串循环右移n位。例如:原来是”abcdefghi”,如果n = 2,
Windows中有一项功能,是可以在任务管理器中查看CPU的使用率,管理器以图形使用率在不同的时间点的
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号