本文主要是介绍编程之美：饮料供货，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
水房能容纳饮料的总量是V，有一批饮料，每种饮料单个容量都是2的方幂，每种饮料信息如下：（Si,Vi,Ci,Hi）分别对应（名字，容量，满意度），求在满足总容量等于V的情况下，求满意度的最大值。
分析：
1、动态规划解法，不难看出这是一道完全背包问题
具体思路解法见：第七章 背包问题——完全背包
2、动态规划法的变形：备忘录法
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x7fffffffconst int N=3;//饮料种数
const int V=8;//水房容量 int C[N+1]={0,8,4,2}; //Ci表示第i种饮料的容量 （i从1开始）
int H[N+1]={0,2,3,1}; //W[i]表示第i种饮料的满意度 int dp[N+1][V+1]; int Cal(int n,int v){if(n>N){if(v==0)return 0;else return -INF;} if(v<0)return -INF;else if(v==0)return 0;else if(dp[n][v]!=-1)return dp[n][v];int ret=-INF;for(int i=0;i<=V/C[n];i++){int temp=Cal(n+1,v-i*C[n]);if(temp!=-INF){temp+=H[n]*i;ret=max(ret,temp);}}return dp[n][v]=ret;
}
int main(){for(int i=1;i<=N;i++)for(int j=1;j<=V;j++)dp[i][j]=-1;cout<<Cal(1,V);return 0;
}
3、注意到这个题目的限制，每种饮料容量只能是2的方幂
1）对于总容量V，假设为10，写成2进制形式为，1010，因为每种容量只能是2的方幂，所以对于容量10，也就是等于，拿8容量的饮料最大值加上拿2容量得饮料的最大值
2）对于相等容量的饮料，当然只用取满意度最高的那种就行了
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x7fffffffconst int N=4;//饮料种数
const int V=7;//水房容量 struct node{int C;int H;bool operator<(const node &t)const{return H<t.H;}
};
node water[N+1]={{0,0},{8,4},{4,3},{4,2},{2,1}};node *bucket[20][20]={NULL};
int length[20]={0};
int main(){//将饮料按照容量进行分类，假设最多20类，如容量为2=2^1，所以将它放到1位置for(int i=1;i<=N;i++){int cnt=0;int t=water[i].C;while(!(t&1)){t>>=1;cnt++;}bucket[cnt][length[cnt]++]=&water[i];}//每个类别按照满意度进行排序，选出满意度最高的此类饮料for(int i=0;i<20;i++){if(length[i]==0)continue;sort(bucket[i],bucket[i]+length[i]);}//store[i]数组存储如要拿2^i容量的饮料所获得的最大满意度int store[20];memset(store,-1,sizeof(store));store[0]=length[0]>0?bucket[0][0]->H:-1;for(int i=1;i<20;i++){int t=-1;if(length[i]>0)t=bucket[i][0]->H;store[i]=max(t,2*store[i-1]);if(store[i]>V)break;}//将V转化成2进制数据求总满意度int H=0;//总满意度int C=0;//总容量int v=V;int k=0;while(v>0){if(v&1){if(store[k]<0){cout<<"无法组成"<<(1<<k)<<"容量的饮料"<<endl;//break;}else {H+=store[k];C+=1<<k;}}v>>=1;k++;}cout<<"总容量为"<<V<<endl<<"所用容量为"<<C<<endl<<"最大满意度为"<<H<<endl;return 0;
}
这篇关于编程之美：饮料供货的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
