动态规划：生产计划问题

ProductPlan.cpp

/*
 * 动态规划
 *
 * 生产计划问题 解答
 *
 * 工厂生产某种产品，每单位(千件)的成本为1(千元)，
 * 每次开工的固定成本为3(千元)，工厂每季度的最大生产能力为6(千件)。
 * 经调查，市场对该产品的需求量第一、二、三、四季度分别为 2，3，2，4(千件)。
 * 如果工厂在第一、二季度将全年的需求都生产出来，
 * 自然可以降低成本(少付固定成本费)，
 * 但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5(千元)。
 * 还规定年初和年末这种产品均无库存。
 * 试制订一个生产计划，即安排每个季度的产量，使一年的总费用(生产成本和存储费)最少。
 *
 *  Created on: 2010-3-1
 *  Author: songpp
 */
#include <iostream>
#include <map>
#include <vector>
using namespace std;
//阶段数
const int Q = 4;
//每阶段需求量
const int req[Q] = { 2, 3, 2, 4 };
//固定开工成本
const double fix_cost = 3;
//每千件生产费用
const int per = 1;
//每千件存储费用
const double store_cost = 0.5;
//单阶段最大生产量
const int Max = 6;
// 阶段计划
struct plan {
	int u; // 阶段产量
	int x; // 阶段存储量
	int step; //阶段号
	double cost;//阶段花费
};
//计算阶段的花费
double cost(int total, int u, int step);
/*
 * x 阶段库存
 * step 第几阶段？
 * arr_u 由此阶段库存x导出的所有可能的生产计划
 */
void f2(int x, int step, vector<plan>& arr_u);

double cost(int total, int u, int step) {
	assert (total >= req[step] && total >= u);
	int x = total - req[step];
	if (u == 0)
		return store_cost * x;
	else
		return store_cost * x + fix_cost + per * u;
}

void f2(int x, int step, vector<plan>& arr_u) {
	//	cout << step << endl;
	assert( step >= 0 && step <= Q);
	arr_u.clear();
	if (step == Q) { // 最后一步
		plan p;
		p.step = step;
		p.cost = 0;	//不花费
		p.u = 0;	// 不生产
		p.x = 0;	// 第Q阶段开始库存为0
		arr_u.push_back(p);
		return;
	}

	int min_u = req[step];

	if (x >= min_u) {
		min_u = 0;
	} else {
		min_u = min_u - x;
	}
	for (int u = min_u; u <= Max; ++u) {
		double cost0 = cost(u + x, u, step);
		plan p;
		p.step = step;
		p.cost = cost0;
		p.u = u;
		p.x = u + x - req[step];
		arr_u.push_back(p);
	}
}

int main(int arglen, char ** args) {
	map<int, plan> result; // 最终结果
	map<int, int> storage; // 每阶段开始时的库存
	storage[0] = 0; //第一阶段为0

	for (int i = 0; i < Q; ++i) {
		double t = 0xffffff;
		vector<plan> start;
		f2(storage[i], i, start); // 当前阶段可用的所有计划

		for (vector<plan>::iterator bgn = start.begin();
				bgn != start.end(); ++bgn) {
			vector<plan> next;
			//下阶段可用所有计划
			f2(bgn->x, bgn->step + 1, next);

			for (vector<plan>::iterator nbgn = next.begin();
					nbgn != next.end();	++nbgn) {
				double min = bgn->cost + nbgn->cost;
				// 查找 两个阶段 花费和的 最小值
				if (t > min) {
					t = min;
					result[bgn->step] = *bgn;
					// 计算出下阶段开始时产品的库存数量
					storage[nbgn->step] = bgn->x;
				}
			}// end for

		}//end for

	}//end for
	double sum = 0;
	for (map<int, plan>::const_iterator iter = result.begin();
			iter != result.end(); ++iter) {
		sum += (iter->second).cost;
		cout << iter->first + 1 << " => " << (iter->second).u << endl;
	}
	cout << " total cost : " << sum << endl;

}