【题解】多重背包 (HDU2191) -boshi

题意：

给定一些物品的价值、大小、数量。求一个大小为 m 的背包最多装得下多少价值的物品。

虽然这道题乱搞都可以 AC，但是我们还是实用单调队列优化

这里的 f[i] 表示容量为 i 的背包可以装下的最大价值 (而不是恰好装下)。因此可以很方便地使用单调队列优化
这所谓的单调队列是神码样的呢？它其实维护了两个单调性：
右边的比左边的新进队。
左边的比右边的优。
为什么这样就对呢？其他单调性为什么不对呢？
这样想：我们至少得维护时间的单调性：也就是右边的比左边的新进队。为什么同时左边的要比右边的优呢？感性地想：在队列中的元素向左侧 “流动” 时，我们会 “失去” 非常优秀的解而只能从新进来的解中转移。因此单调性是左边优于右边。
有了单调队列的思路，有了状态转移方程，我们就可以轻松的写出代码。
噢，不知道大家有没有想到这样一个问题：
由于状态转移方程是：
f[i]=max(f[i-kw[i]]+kv[i])
我们不能直接将每个 f[i] 的值存进队列，而应该保存 f[i]-i/w[i]*v[i]（仔细想一想为什么）
有了以上这些准备工作，我们的程序差不多就完备了。

#include <iostream>
#include <cstdio>
#include <cstring>

#define max(a,b) ((a>b)?(a):(b))
#define MX 101

using namespace std;

int v[MX],w[MX],c[MX];
int n,m;

void input()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&w[i],&v[i],&c[i]);
}

pair<int,int>q[MX];
int h,t;
int f[MX];

void work()
{
    int relex;
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        if(c[i]==0)continue;
        if(c[i]>m/w[i])c[i]=m/w[i];
        for(int j=0;j<w[i];j++)
        {
            h=0,t=1;
            for(int k=0;k<=(m-j)/w[i];k++)             //这里我们直接枚举装入几个物品，而不是枚举装到多大空间。
            {
                relex=f[k*w[i]+j]-k*v[i];                      //详见上文的分析
                while(q[h].first<relex&&h>=t)h--;
                q[++h].first=relex;
                q[h].second=k;
                while(q[t].second<k-c[i])t++;
                f[k*w[i]+j]=q[t].first+k*v[i];
            }
        }
    }
    printf("%d\n",f[m]);
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        input();
        work();
    }
    return 0;
}