从0/1背包到多重背包

在现实生活中，很少有像0/1背包一样的情况，而更多的是一件东西可以有很多件，这种情况我们就要用多重背包来解决这个问题了。

从0/1背包到多重背包

我们以洛谷P1833 樱花作例子，来讲一讲多重背包。

我们把原题先转化成0/1背包问题来看，也就是所有的$P_i = 1$的情况，根据题目，我们很容易得到转移方程:

$dp[t] = max(dp[t - t[i]] + c[i],dp[t])$

那么如果我们某一朵花可以看$3$遍，其实这样说来就是有三朵这样的花，我们只需要把0/1背包的过程重复$3$遍就可以了。

扩展到$P_i$，我们只需要将0/1背包的过程重复$P_i$遍就好了。

for(int x = 1;x <= n;x++){
    if(p[x] >= 1)
        for(int i = 1;i <= p[x];i++)//唯一比0/1背包多出来的东西就是这个循环，代表着将0/1循环重复p[x]遍
            for(int ti = T;ti >= t[x];ti--)
                dp[ti] = max(dp[ti - t[x]] + c[x],dp[ti]);
}

优化

我们分析dp数组，我们可以得到:

第一次0/1dp时，$dp[t[x]]$到$dp[2t[x]]$的数据是由$dp[0]$到$dp[t[x]]$得来的（因为$dp[ti - t[x]] + c[x]$），而第二次0/1dp时这些数据并不会改变,我们就不需要dp$t[x]$到$2t[x]$这一段了，

同理:

第二次0/1dp时，$dp[2t[x]]$到$dp[3t[x]]$的数据是由$dp[t[x]]$到$dp[2t[x]]$得来的，而第三次0/1dp时这些数据并不会改变,我们就不需要dp$2t[x]$到$3*t[x]$这一段了。

也就是说，我们只需要dp $T >= ti >= i*t[x]$ 这一段就行了。

for(int x = 1;x <= n;x++){
    if(p[x] >= 1)
        for(int i = 1;i <= p[x];i++)
            for(int ti = T;ti >= t[x]*i;ti--)//一个简单的判断条件的改变大大减少了时间复杂度
                dp[ti] = max(dp[ti - t[x]] + c[x],dp[ti]);
}

题解/$748.00KB$/$843ms$

这道题还有一部分是$P_i == 0$的，也就是说可以看无限多次，也就是说，这种情况是完全背包。

for(int x = 1;x <= n;x++){
    if(p[x] >= 1)
        for(int i = 1;i <= p[x];i++)
            for(int ti = T;ti >= t[x]*i;ti--)
                dp[ti] = max(dp[ti - t[x]] + c[x],dp[ti]);
    else//完全背包部分
        for(int ti = t[x];ti <= T;ti++)
            dp[ti] = max(dp[ti - t[x]] + c[x],dp[ti]);
}

然后这道题的读入有点特殊，但是用scanf可以轻松解决。

1	scanf("%d:%d %d:%d",&h1,&m1,&h2,&m2);

时间的计算很简单，就不赘述了。

1	T = (h2-h1)*60 + m2 - m1;

那么完整的代码就出来了:

#include <bits/stdc++.h>
#define MAXN 10005
using namespace std;

int T,n,t[MAXN],c[MAXN],p[MAXN],dp[MAXN];

int main(){
    int h1,m1,h2,m2;
    scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&n);
    T = (h2 - h1)*60 + m2 - m1;
    for(int i = 1;i <= n;i++) cin>>t[i]>>c[i]>>p[i];
    for(int x = 1;x <= n;x++){
        if(p[x] >= 1)
            for(int i = 1;i <= p[x];i++)
                for(int ti = T;ti >= t[x]*i;ti--)
                    dp[ti] = max(dp[ti - t[x]] + c[x],dp[ti]);
        else
            for(int ti = t[x];ti <= T;ti++)
                dp[ti] = max(dp[ti - t[x]] + c[x],dp[ti]);
    }
    cout<<dp[T]<<endl;
    return 0;
}