POJ 2392 初涉多重背包

题意：有K种石头，每种石头的高度为H，个数为Q，放置高度不能超过C。问这些石头最高的可达高度是多少。

裸的多重背包。

对于N种，K件的多重背包可以转换成∑ki的01背包。

假设不存在限制C时，则先放A种还是先放B中对结果无影响。当添加上限制条件C时，应该让C小的在下面。故在进行01背包前要将C排序。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <stack>

#define LL long long
#define ULL unsigned long long
#define PI (acos(-1.0))
#define EPS (1e-10)
#pragma comment(linker,"/STACK:102400000,1024000")

using namespace std;

struct N
{
    int w,v,q;
}c[410];

bool acc[40010];

bool cmp(N c1, N c2)
{
    return c1.w < c2.w;
}

int main()
{
    int n,i,j,k;

    scanf("%d",&n);

    for(i = 0;i < n; ++i)
    {
        scanf("%d %d %d",&c[i].v,&c[i].w,&c[i].q);
    }

    sort(c,c+n,cmp);

    memset(acc,false,sizeof(acc));

    acc[0] = true;

    int Max = 0;

    for(i = 0;i < n;++i)
    {
        for(j = 0;j < c[i].q; ++j)
        {
            for(k = c[i].w; k >= c[i].v; --k)
            {
                if(acc[k-c[i].v])
                {
                    acc[k] = true;
                    Max = max(Max,k);
                }
            }
        }
    }

    printf("%d\n",Max);

    return 0;
}

POJ 2392 初涉多重背包

原文：http://blog.csdn.net/zmx354/article/details/19414651