首页 > 代码库 > 1.6 饮料供货
1.6 饮料供货
问题:
总共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 * Hi + Opt(V’-Vi * 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; }
1.6 饮料供货
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。