在洛谷上碰到一题 《桜》是个0/1、多重、完全背包的混合问题。
原题
掏出珍藏的背包模板，结果得了80。
参考了一下题解发现事情没有那么简单。

朴素的背包

假设总的时间限制是T。物品i具有三个属性p[i]是可取用的次数，以0代表无穷次；t[i]为占用的时间；c[i]为可以获得的收益。

首先，0/1背包明显是多重背包的一个特例，在此不多讨论。

然后，对于完全背包，由于总的时间限制的存在，不可能随意取用，所以可以令p[i]=T / t[i]将其化为多重背包问题。

对于多重背包问题，朴素的动态规划的时间复杂度是T \cdot n \cdot \overline {p[i]}，空间复杂度是T \cdot n,考虑到题目限制T \le 1000、n \le 10^4。这表面上还行，但是想想看，\overline {p[i]} \le T/ {\overline {t[i]}}是个隐藏条件，非常有可能被卡数据（时间复杂度可以达到T^2 \cdot n）。也确实被卡了

但是这个方法胜在实现简单，也能得个80，还算让人满意的。

膜法优化贡献时间

设想对于物品k,有p[k]=20,当我们规划到它时，我们有取0 \sim 20个，共21个决策要做，这实在是太粗暴了，我们来处理一下。

20 = 1 + 2 + 4 + 8 + 5

这样子，任何整数n可以分解为不超过\lceil \log_{2}{n} \rceil +1个整数的和。具体来说，任何正整数n可以分解为\sum_{i=0}^{ \lfloor log_2{n-1} \rfloor}{2^i}+a(a，从这些数字中挑选，可以组合出0 \sim n的任何数字。这样将物品进行划分，变为0/1背包，就可以将时间复杂度降低至T \cdot n \cdot \log{T}。令人舒适。

传统0/1背包的空间优化

前文提到，将一个物品分解以降低其消耗的决策数，可以加快计算。
但是，这是有代价的，物品的总数增加了，如果还是保存一个完整的动态规划表格就会在内存上捉襟见肘。
不过现在已经是0/1背包的天下了。而这种背包可以通过复用内存空间实现空间复杂度的好几个数量级的降低。
就是每次处理一个物品时，按照剩余时间的逆序进行动态规划，就可以不用保存上个物品的规划信息。
这个顺序十分重要，反过来会导致数据的错误覆盖，从而WA。

---

代码警告

略去了部分不重要的代码。

---

朴素的做法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
const int MAX_N = 10007;
const int MAX_T = 1007;
int n, TeH, TeM, TsH, TsM, T;
int mem_dp[MAX_N][MAX_T];
int ynT[MAX_N];
int ynP[MAX_N];
int ynC[MAX_N];
inline int max(int a, int b)；
void ResetMem(void)；
int ynDP(int i, int j)
{
    if (i < 0 || j <= 0)
    {
        return 0;
    }
    else
    {
        if (mem_dp[i][j] != -1)
        {
            return mem_dp[i][j];
        }
        else
        {
            if (j < ynT[i])
            {
                return mem_dp[i][j] = ynDP(i - 1, j);
            }
            else
            {
                int MaxC = 0;
                if (ynP[i] == 0)
                {
                    for (size_t k = 0; k <= j / ynT[i]; k++)
                    {
                        MaxC = max(ynDP(i - 1, j - ynT[i] * k)+k*ynC[i],MaxC);
                    }
                }
                else
                {
                    for (size_t k = 0; k <= ynP[i] && k <= j / ynT[i]; k++)
                    {
                        MaxC = max(ynDP(i - 1, j - ynT[i] * k)+k*ynC[i],MaxC);
                    }
                }
                return mem_dp[i][j] = MaxC;
            }
        }
    }
}
int main(void)
{
    while (scanf("%d:%d%d:%d%d",&TsH,&TsM,&TeH,&TeM,&n)!=EOF)
    {
        T = (TeH - TsH) * 60 + TeM - TsM;
        ResetMem();
        for (size_t i = 0; i < n; i++)
        {
            scanf("%d%d%d", &ynT[i], &ynC[i], &ynP[i]);
        }
        printf("%d\n", ynDP(n-1, T));
    }
    return 0;
}

优化的做法

#include<stdio.h>
const int MAX_N = 100007;
const int MAX_T = 1001;
int n, TeH, TeM, TsH, TsM, T;
int mem_dp[MAX_T];
int ynT[MAX_N];
int ynP[MAX_N];
int ynC[MAX_N];
inline int max(int a, int b)；
inline int min(int a, int b)；
inline void ResetMem(void)；
int ynDP(int i, int j)
{
        if (j>=ynT[i])
        {
            return mem_dp[j] = max(mem_dp[j], mem_dp[ j - ynT[i]] + ynC[i]);
        }
        else
        {
            return mem_dp[j] = mem_dp[j];
        }
}
int main(void)
{
    while (scanf("%d:%d%d:%d%d", &TsH, &TsM, &TeH, &TeM, &n) != EOF)
    {
        T = (TeH - TsH) * 60 + TeM - TsM;
        for (size_t i = 0; i < n;)
        {
            scanf("%d%d%d", &ynT[i], &ynC[i], &ynP[i]);
            int p = ynP[i];
            int t = ynT[i];
            int c = ynC[i];
            int k = 1;
            if (p==0)
            {
                p = T / t;
            }
            int RestP = p;
            while (k<p/2)
            {
                    ynC[i] = c * k;
                    ynP[i] = k;
                    ynT[i] = t * k;
                    RestP -= k;
                    k <<= 1;
                    n++;
                    i++;
            }
            ynC[i] = c * RestP;
            ynP[i] = RestP;
            ynT[i] = t * RestP;
            i++;
        }
        ResetMem();
        for (size_t i = 0; i < n; i++)
        {
            for (int j = T; j >=0 ; j--)
            {
                ynDP(i, j);
            }
        }
        printf("%d\n", mem_dp[T]);
    }
    return 0;
}