问题：

总共n中饮料，每种饮料表示为(S[i],V[i],C[i],H[i],B[i]),S表示名称，V表示容量。C表示能够买的最大数量，H表示惬意度，B表示实际购买量 在V[i]*B[i]求和=V的情况下，H[i]*B[i]求和最大化

最优化。毫无疑问。考虑动态规划跟贪心。

状态转移方程：

设Opt（V’，i）表示从 i 到 n-1 种饮料中，Ci 为第i种饮料可能的最大数量。算出总量为V’的方案中惬意度之和的最大值。

那么递归式就应该是：

Opt（V’，i）= max{ k * H_i + Opt（V’-V_i * k，i+1）}（k=0，1。2…，Ci，i=0。1。2…，n-1）

这里我认为须要说明给出的饮料组合终于能够组合出V。

递推：

int Cal(int V, int T) {	opt[0][T] = 0;									//边界条件，T为全部饮料种类	for(int i = 0; i <= V; ++i) opt[i][T] = -INF;	//边界条件	for(int j = T-1; j >= 0; --j) {		for(int i = 0; i <= V; ++i) {			opt[i][j] = -INF;			for(int k = 0; k <= C[j]; ++k) {        //遍历第j种饮料选取数量k				if(i < k * V[j]) break;				int x = opt[i - V[j] * k][j + 1];				if(x != -INF) {					x += k * H[j];					if(x > opt[i][j]) opt[i][j] = x;				}			}		}	}	return opt[V][0];}

记忆化搜索：

int opt[V+1][T+1];    //初始化时opt中存储值为-1，表示该子问题尚未被求解int Cal(int V, int type) {	if(type == T) {		if(V == 0) return 0;		else return -INF;	}	if(V < 0) return -INF;	if(V == 0) return 0;	else if(opt[V][type] != -1) return opt[V][type];  //该子问题已求解，则直接返回子问题的解	int ret = -INF;                                   //子问题尚未求解，则求解该子问题	for(int i = 0; i <= C[type]; ++i) {               		int temp = Cal(V - i * V[type], type + 1);		if(temp != -INF) {			temp += i * H[type];			if(temp > ret) ret = temp;		}	}	return opt[V][type] = ret;}