hdu3244Inviting Friends(二分+完全背包)

背包)"/>

hdu3244Inviting Friends(二分+完全背包)

->题目请戳这里<-

题目大意：lz要请客，要准备n种原料，每种原料有6个参数：x,y,s1,p1,s2,p2。表示的含义分别是：对于第i种原料，每个人的需求量是x，现在还剩下y的量，每种原料有2种包装，一种小包的，一种打包的，每一小包的量是s1，价格是p1，打包的量是s2，价格是p2。现在给你n种原料和m的钱，求最多能请几个人。

题目分析：由于要请多少人不知道，要满足所有人，所以我们二分枚举人数。人数的上界是：对于每种原料，假设m的钱全部用来满足这种原料，求出一个人数上界，n个上界取最小值就是整个二分的上界。然后对于每个二分过程，要依次满足n原料的数量大于需要的量，抽象出来的模型就是如何用m的前买最多的量，这就是一个完全背包问题。跟完全背包稍有不同的是：假设某种原料差量是need，那么我们背包的容量不是恰好为need的，而是大于等于need的，所以背包的容量要取大一点，取need + s2 -1 即可(想一想，为什么)。最后在dp数组中从need扫到need + s2-1，求出最小值返回即可。

详情请见代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 104;
const int INF = 0x3fffff;
const double eps = 1e-4;
struct node
{int per,remain,s1,p1,s2,p2;double ave1,ave2;
}lcm[N];
int n,m;int dp[1110000];
int pack(int cur,int sum)
{int i;int a=min(lcm[cur].s1,lcm[cur].s2);int b=max(lcm[cur].s1,lcm[cur].s2);if(sum < a)return min(lcm[cur].p1,lcm[cur].p2);    sum+=b-1;for(i=1;i<=sum;i++)dp[i]=INF;dp[0]=0;for(i=1;i<=sum;i++)if(i>=lcm[cur].s1&&((i-lcm[cur].s1==0)||dp[i-lcm[cur].s1]))dp[i]=min(dp[i],dp[i-lcm[cur].s1]+lcm[cur].p1);for(i=1;i<=sum;i++)if(i>=lcm[cur].s2&&((i-lcm[cur].s2==0)||dp[i-lcm[cur].s2]))dp[i]=min(dp[i],dp[i-lcm[cur].s2]+lcm[cur].p2);int ans=INF;for(i=sum-(b-1);i<=sum;i++)ans=min(ans,dp[i]);return ans;
}int isok(int x)
{int money = m;int i;for(i = 0;i < n;i ++){int need = lcm[i].per * x - lcm[i].remain;money -= pack(i,need);if(money < 0)return 0;}if(money < 0)return 0;return 1;
}int main()
{int cnt,i;while(scanf("%d%d",&n,&m),(m + n)){int mx = 100000;for(i = 0;i < n;i ++){scanf("%d%d%d%d%d%d",&lcm[i].per,&lcm[i].remain,&lcm[i].s1,&lcm[i].p1,&lcm[i].s2,&lcm[i].p2);lcm[i].ave1 = (double)lcm[i].s1 / (lcm[i].p1 * 1.0);lcm[i].ave2 = (double)lcm[i].s2 / (lcm[i].p2 * 1.0);int tmp = m / lcm[i].p2;cnt = (m - lcm[i].p2 * tmp) * lcm[i].s1 / lcm[i].p1 + tmp * lcm[i].s2;cnt += lcm[i].remain;cnt /= lcm[i].per;if(mx > cnt)mx = cnt;}int l = 1;int r = mx;int mid;int ans;while(l <= r){mid = (l + r)>>1;if(!isok(mid))r = mid - 1;else{ans = mid;l = mid + 1;}}printf("%d\n",ans);}return 0;
}