hdu3244 Inviting Friends(2점+완전 백팩)

-> 제목은 여기를 찍으세요<-
제목: lz가 한턱 내야 하고 n가지 원료를 준비해야 한다. 각 원료는 6개의 매개 변수가 있다. x, y, s1, p1, s2, p2.표현의 의미는 다음과 같다. 제i종의 원료에 대해 모든 사람의 수요량은 x이고 현재 y의 양이 남았다. 각 원료는 2종의 포장, 1종의 소포, 1종의 포장, 1종의 소포의 양은 s1, 가격은 p1, 포장의 양은 s2, 가격은 p2이다.지금 n가지 원료와 m의 돈을 드릴 테니 최대 몇 명을 초대해 주십시오.
제목 분석: 몇 명을 청해야 할지 모르고, 모두를 만족시켜야 하기 때문에 우리는 2분의 1로 사람 수를 든다.인원수의 상계는 각 원료에 대해 m의 돈이 모두 이런 원료를 충족시키는 데 쓰인다고 가정하고 한 인원수의 상계를 구하면 n개의 상계가 최소치를 취하는 것이 전체 2분의 상계이다.그리고 각 2분의 과정에 대해 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
",ans);
    }
    return 0;
}