#P1064. [NOIP2006 提高组] 金明的预算方案

真·金明

死路

nPr123f 最喜欢的 枚举子集，时间复杂度 $O(2^n)$，对于 $n \leq 3.2 \times 10^4$ 还是太大了……

思路

可以转化成分组背包解决。

读入之后，对应同一个主件的附件放在一起，得到一个“组”。

在 DP 的第一层循环中枚举每一组，再考虑每一组内的情况。

每一组内的情况就可以用 01 背包解决。

但是我们要考虑的不是每一个物品的选不选，而是几个物品组合起来的所有情况。

拿样例举例：

• 主件：电脑
• 附件：打印机、扫描仪

我们需要考虑：

• 电脑
• 电脑 + 打印机
• 电脑 + 扫描仪
• 电脑 + 打印机 + 扫描仪

所以我们怎么快捷地循环遍历每一种情况呢？

nPr123f 最喜欢的 枚举子集！！！！！！

这里介绍一种快捷的、可靠的循环枚举方法——二进制法：

枚举子集中，可以用 1 表示选，0 表示不选。

则上面的考虑情况可以转换为（只考虑附件，因为主件必选）：

• 00
• 01
• 10
• 11

每一个状态的迭代可以直接 +1 实现（$(101)_2 - (100)_2 = 1$）。

这样，一个 int 就成功枚举了所有可能。

这样就成功解决了本题。

代码

#include <cstdio> 
#include <vector>
#include <algorithm>
#define M 62
#define N 32010

using namespace std;

bool ismain[M] = {};			// 是否是主件 
int v[M], p[M], q, dp[N], m, n;	
vector<int> adds[M];			// 每个主件拥有的附件的下标 

int main()
{
    scanf("%d %d", &n, &m);	// 输入 
    
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &v[i], &p[i], &q);	// 输入 
        p[i] *= v[i];			// 提前计算好乘积 

        if (!q)
            ismain[i] = true;	// 是主件 
        else
            adds[q].push_back(i);	// 是 q 的附件 
    }

    for (int i = 1; i <= m; i++)	// 枚举每件物品 
        if (ismain[i])				// 如果是主件 
            for (int j = n; j >= 0; j--)	// 背包容量 
                for (int S = 0; S < 1 << adds[i].size(); S++)	// S 是 i 的附件选或不选的子集 
                {
                    int sumv = v[i], sump = p[i];				// 价格和 & 价值和 

                    for (int k = 0; k < adds[i].size(); k++)	// 检验每一位 
                        if (S & (1 << k))						// 是 1（选了） 
                        {
                            sumv += v[adds[i][k]];				// 累加 
                            sump += p[adds[i][k]];
                        }

                    if (j >= sumv)									// 背包容量足够 
                        dp[j] = max(dp[j], dp[j - sumv] + sump);	// 更新答案 
                }

    printf("%d", dp[n]);	// 输出 

    return 0;	// AC!!!!!!
}