动态规划-企业成本

某企业在未来的12个月要研究一种新产品，新产品的研制需要四个阶段，每个阶段都可用慢、正常、快等三种速度进行，时间和成本如下表所列。
理论研究 试验阶段 政府批准 销售
慢 5/5 3/6 6/1 5/8
正常 4/7 2/8 4/1 4/10
快 2/10 1/12 2/3 3/15
说明：单位（月/万元），时间按月，成本按万元为单位。
例如：5/5代表5个月，5万元；4/7代表4个 月，7万元。
该企业准备在12个月内花费最少的费用就可以有新产品。
（1）请给出最佳方法或算法。
（2）编程实现最佳算法。
（3） 达到同一目标的次佳方法或算法是什么？

 

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

/* 理论研究 试验阶段 政府批准 销售
 慢 5/5 3/6 6/1 5/8
 正常 4/7 2/8 4/1 4/10
 快 2/10 1/12 2/3 3/15*/
public class Test {
	int[][][] data = { { { 5, 5 }, { 4, 7 }, { 2, 10 }, }, 
	                   { { 3, 6 }, { 2, 8 }, { 1, 12 }, },
	                   { { 6, 1 }, { 4, 1 }, { 2, 3  }, }, 
	                   { { 5, 8 }, { 4, 10}, { 3, 15 }, }, };
	
	Map<Integer, Integer> strategyMap0 = new HashMap<Integer, Integer>();
	Map<Integer, Integer> strategyMap = new HashMap<Integer, Integer>();

	Map<String, String> strategyPathMap = new HashMap<String, String>();

	public static void main(String[] args) {
		new Test().go();
	}
	
	public Map<Integer, Integer> copyMap(Map<Integer, Integer> map2) {
		Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
		
		for(Entry<Integer, Integer> entry : map2.entrySet()) {
			map1.put(entry.getKey(), entry.getValue());
		}
		return map1;
	}

	public void go() {
		// initialize the strategymap with the first row
		for(int i = 0; i < 3; i++) {
			strategyMap.put(data[0][i][0], data[0][i][1]);
			strategyPathMap.put(data[0][i][0] + "/" + data[0][i][1], data[0][i][0] + "/" + data[0][i][1]);
		}
		
		for(int i = 0; i < 3; i++) {
			strategyMap0 = copyMap(strategyMap);
			strategyMap.clear();
			
			for(Entry<Integer, Integer> entry : strategyMap0.entrySet()) {
				for(int j = 0; j < 3; j++) {

					int monthsum = entry.getKey() + data[i + 1][j][0];
					int moneysum = entry.getValue() + data[i + 1][j][1];
					
					strategyPathMap.put(monthsum + "/" + moneysum, strategyPathMap.get(entry.getKey() + "/" + entry.getValue()) + "-" + (data[i + 1][j][0] + "/" + data[i + 1][j][1]));
					
					// strategy filtering
					if(strategyMap.get(monthsum) == null || moneysum < strategyMap.get(monthsum)) {
						strategyMap.put(monthsum, moneysum);
					}
				}
			}

		}
		
		System.out.println(strategyMap.get(12));
		System.out.println(strategyPathMap.get(12 + "/" + strategyMap.get(12)));
	}

}

 

动态规划加入策略筛选，排除明显非最优子策略以剪枝

 

每一个子阶段，比如12阶段，123阶段都有一些最优策略组，这些策略在没有引入下一阶段之前无法进行筛选，所以都予以保留，只筛选那些明显非最优的子策略