首页 > ACM题库 > HDU-杭电 > HDU 3244-Inviting Friends-背包问题-[解题报告]HOJ
2014
03-09

HDU 3244-Inviting Friends-背包问题-[解题报告]HOJ

Inviting Friends

问题描述 :

You want to hold a birthday party, inviting as many friends as possible, but you have to prepare enough food for them. For each person, you need n kinds of ingredient to make good food. You can use the ingredients in your kitchen, or buy some new ingredient packages. There are exactly two kinds of packages for each kind of ingredient: small and large.

We use 6 integers to describe each ingredient: x, y, s1, p1, s2, p2, where x is the amount (of this ingredient) needed for one person, y is the amount currently available in the kitchen, s1 and p1 are the size (the amount of this ingredient in each package) and price of small packages, s2 and p2 are the size and price of large packages.

Given the amount of money you can spend, your task is to find the largest number of person who can serve. Note that you cannot buy only part of a package.

输入:

There are at most 10 test cases. Each case begins with two integers n and m (1<=n<=100, 1<=m<=100000), the number of kinds of ingredient, and the amount of money you have. Each of the following n lines contains 6 positive integers x, y, s1, p1, s2, p2 to describe one kind of ingredient (10<=x<=100, 1<=y<=100, 1<=s1<=100, 10<=p1<=100, s1<s2<=100, p1<p2<=100). The input ends with n = m = 0.

输出:

There are at most 10 test cases. Each case begins with two integers n and m (1<=n<=100, 1<=m<=100000), the number of kinds of ingredient, and the amount of money you have. Each of the following n lines contains 6 positive integers x, y, s1, p1, s2, p2 to describe one kind of ingredient (10<=x<=100, 1<=y<=100, 1<=s1<=100, 10<=p1<=100, s1<s2<=100, p1<p2<=100). The input ends with n = m = 0.

样例输入:

2 100
10 8 10 10 13 11
12 20 6 10 17 24
3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16
0 0

样例输出:

5
2

->题目请戳这里<-

题目大意: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;
}

参考:http://blog.csdn.net/ophunter_lcm/article/details/9072113


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks