萌新求助！关于一个题解的一些问题！

xixi_bang @ 2020-04-05 13:47:32

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
int f[5000010],h[5000010];
struct node
{
    int v,p,q;
}a[1010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
        a[i].p*=a[i].v;
    }
    for(int i=1;i<=m;i++)
        if(!a[i].q)
        {
            for(int j=1;j<a[i].v;j++)
                h[j]=0; 
            for(int j=a[i].v;j<=n;j++)
                h[j]=f[j-a[i].v]+a[i].p;
            for(int j=1;j<=m;j++)
                if(a[j].q==i)
                    for(int k=n;k>=a[i].v+a[j].v;k--)
                        h[k]=max(h[k],h[k-a[j].v]+a[j].p);
            for(int j=a[i].v;j<=n;j++)
                f[j]=max(f[j],h[j]);
        }   
    printf("%d\n",f[n]);
    return 0;
}

by metaphysis @ 2020-04-05 19:57:54

@xixi_bang

本题可以归结为背包问题。背包问题有四种基本类型，分列如下（参见我写的书 《C++，挑战编程——程序设计竞赛进阶训练指南》 第 11 章“动态规划”第 11.1 节“背包问题”的内容）：

基本背包问题： 给定一个容量为 C 的背包，现有 n 个物品，每个物品具有容量 C_i 和价值 P_i，1≤i≤n，问如何选取放入背包的物品，使得背包内的物品容量之和不超过 C 且价值之和最大。由于物品要么放入背包，要么不放入背包，设xi表示物品在背包中的状态，则有 x_i ∈ {0，1}，故称01背包问题。

完全背包问题： 给定一个容量为 C 的背包，有 n 种物品，每种物品都有容量 C_i 和价值 P_i，1≤i≤n，假设每种物品的数量不限，问如何选取放入背包的物品，使得背包内的物品容量之和不超过 C 且价值之和最大。

多重背包问题： 给定一个容量为 C 的背包，有 n 种物品，每种物品都有容量 C_i 和价值 P_i，且有数量上限 Q_i，1≤i≤n，问如何选取放入背包的物品，使得背包内的物品容量之和不超过 C 且价值之和最大。

部分背包问题： 给定一个容量为 C 的背包，有 n 个物品，每个物品都有容量 C_i 和价值 P_i，1≤i≤n，物品可以拆分且可取全部或一部分放入背包，问如何选取放入背包的物品，使得背包内的物品容量之和不超过 C 且价值之和最大。

前三种背包问题可以使用动态规划解决，最后一种部分背包问题可以通过贪心算法解决。

从题目的约束来看，属于基本背包问题的一种变形。预算 N 等价于背包的容量，m 为物品的个数，物品的价格 v 等价于物品的容量 C_i，物品的价值为物品的价格 v 和重要度 p 的乘积。与基本的背包问题稍有差异的地方是：题目限制了必须购买主件才能购买附件。那么可以令法 f[i] 表示预算为不超过 i 时能够得到的价格与重要度乘积的总和的最大值，那么我么可以按照解决基本背包问题的思路，从第一件物品枚举到第 m 件物品，检查放入某种物品是否可能更新最优值。由于限制了必须购买主件才能购买附件，对于第 j 种主件来说，可以令 h[i] 表示在前 j-1 中主件和附件可选的情况下，预算不超过 i 时能够得到的最优值，然后考虑购买第 j 种主件和其附件是否能够更新最优值。

以上是解题思路的概述，如果您大致理解了，可以继续参考以下的代码注释进行理解。

// 读入 m 种物品的价格、重要度，第 i 种物品的价值为其价格和重要度的乘积。
for(int i = 1; i <= m; i++)
{
    scanf("%d%d%d", &a[i].v, &a[i].p, &a[i].q);
    a[i].p *= a[i].v;
}
// 逐个物品考虑是否放入背包。
for(int i = 1; i <= m; i++)
    // 题目的特殊限制：必须先放主件。当 a[i].q 为 0 时表示主件。
    if(!a[i].q)
    {
        // 初始化 h 数组，因为第 i 种物品的价格为 a[i].v，
        // 所以当预算小于 a[i].v 时，能够得到的最大价值为 0。
        for(int j = 1; j < a[i].v; j++) h[j] = 0; 

        // 考虑购买该种主件，在原有的最优值数组 f 上更新得到最优值数组 h。
        for(int j = a[i].v; j <= n; j++) h[j] = f[j - a[i].v] + a[i].p;

        // 考虑购买主件的附件。  
        for(int j = 1; j <= m; j++)
            // 检查当前物品是否为主件 i 的附件。   
            if(a[j].q == i)
                // 检查放入附件 j 是否能够更新最优值。注意容量 k 的枚举顺序和下限值。
                // k 从大到小枚举可以节省动态规划状态数组的一维存储空间。
                // 参见我写的书 [《C++，挑战编程——程序设计竞赛进阶训练指南》]
                // 第 11 章“动态规划”第 11.9 节“动态规划的优化”第
                // 11.9.1 小节“空间优化”的内容。  
                for(int k = n; k >= a[i].v + a[j].v; k--)
                    h[k] = max(h[k], h[k - a[j].v] + a[j].p);
        // 数组 h 存储的是考虑放入第 i 种主件及其附件后的最优值，
        // 数组 f 存储的是不考虑放入第 i 种主件及其附件的最优值，
        // 取两者的较优值。由于必须放入主件，故从 a[i].v 开始考虑更新。
        for(int j = a[i].v; j<=n; j++) f[j] = max(f[j], h[j]);
    }
// 输出最优值。
printf("%d\n",f[n]);

如果您有其他问题，欢迎您@我，如果时间允许的话，我很乐意提供帮助。

by xixi_bang @ 2020-04-05 20:37:23

@metaphysis 明白了！谢谢您这么耐心的解答！您实在很细心且逻辑清晰！之后有问题还烦请您指导！