编程之美1.6-饮料供货

参考链接：http://blog.csdn.net/lichaoyin/article/details/9983883

给定一批饮料，每种饮料参数有每瓶容积、饮料数量及满意度。

总共可提供的饮料容积为V，通过组合各饮料的数量，求出最大满意度之和。

设最大满意的之和为opt。

代码：

//opt(V,i):从第i,i+1,i+2...n-1种饮料中，算出总量为V的方案中满意度之和的最大值
//opt(V,i) = max{k*Hi + opt(V-Vi*ki,i+1)}
//Hi:第i种饮料的满意度
//k:购买该种饮料的数量，k=0~该饮料最大瓶数

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
const int MAXV=101;  
const int MAXT=101;  
int opt[MAXV][MAXT];  

class Drink
{
public:
	int Volume;		//该饮料每瓶的容量 = 2的Volume次方
	int TotalCount;	//该饮料的购买瓶数
	int Happiness;	//该饮料每瓶的满意度
	Drink(int v,int t,int h)
	{
		Volume = v;
		TotalCount = t;
		Happiness = h;
	}
};

vector<vector<Drink> > drinks;
//构建一个名为drinks的二维vector
void Init()
{
	ifstream fin("drink.txt");	
	/*
	drink.txt:
	0 2 2
	0 2 3
	0 3 5
	0 3 4
	1 2 6
	1 3 5
	1 4 4
	2 1 18
	2 2 12
	*/
	int v,t,h;  

	while(fin>>v>>t>>h)  
	{  
		while(drinks.size()<=v)  
		{  
			drinks.push_back(vector<Drink>());  
		}  
		drinks[v].push_back(Drink((int)pow(2.0,v),t,h));  
	}  
	fin.close();  
}

int MaxSatisfyDP(int V)	//V为最大容积
{
	int MaxSatisfy = 0;
	vector<Drink> temp;
	for(int i = 0 ; i < drinks.size(); ++i)
		for(int j = 0 ; j < drinks[i].size() ; ++j)
			temp.push_back(drinks[i][j]);
	//T为饮料种类
	int T = temp.size();
	//初始化
	for(int i = 0 ; i < T ; ++i)
		opt[0][i] = 0;
	for(int i = 0 ; i < V ; ++i)
		opt[i][T] = 0;
	//计算opt
	for (int i=T-1; i>=0; --i)  
	{  
		for(int j=0; j<=V; ++j)  
		{  
			opt[j][i] = 0;  
			for (int k=0; k<=temp[i].TotalCount; ++k)  
			{  
				int v = ((int)pow(2.0,temp[i].Volume))*k;
				int h = temp[i].Happiness*k;  
				if (v<=j && opt[j-v][i+1]+h>opt[j][i])  
				{  
					opt[j][i] = opt[j-v][i+1]+h;  
				}  
			}  
		}  
	}  
	return opt[V][0];  
}
int main()
{
	Init();
	cout<<MaxSatisfyDP(7)<<endl;
}