例题2：集合求和

对于从 \(1\) 到 \(N (1 \leq N \leq 39)\) 的连续整数集合，

能划分成两个子集合，且保证每个集合的数字和是相等的。

举个例子，如果 \(N=3\)，

对于 \(\{1,2,3\}\) 能划分成两个子集合，他们每个的所有数字和是相等的：

\(\{3\}\) 和 \(\{1,2\}\)

这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）

如果 \(N=7\)，

有四种方法能划分集合 \(\{1,2,3,4,5,6,7\}\)，每一种分法的子集合各数字和是相等的：

\(\{1,6,7\}\) 和 \(\{2,3,4,5\}\)

\(\{2,5,7\}\) 和 \(\{1,3,4,6\}\)

\(\{3,4,7\}\) 和 \(\{1,2,5,6\}\)

\(\{1,2,4,7\}\) 和 \(\{3,5,6\}\)

给出 \(N\)，你的程序应该输出划分方案总数，

如果不存在这样的划分方案，则输出 \(0\) 。

根据题意，当 \(n\) 个数的和为奇数时，输出 \(0\)。

sum=(1+n)*n/2;
if(sum%2==1)
{
    cout<<0;
    return 0;
}

状态：\(f[i][j]\)：前 \(i\) 个数，累加和为 \(j\) 的方案数

状态转移：\(f[i][j]=f[i-1][j]+f[i-1][j-i]\)

sum/=2;
f[0]=1;
int ans=0;
for(int i=1;i<=n;i++)
    for(int j=sum;j>=i;j--)
        f[j]=f[j]+f[j-i];
printf("%d\n",f[sum]\2);

练习1：开心的金明 Luogu P1060 [NOIP2006 普及组]

练习2：最大约数和 Luogu P1734

练习3：笔直的水管

奶牛们想把水从池塘运输到牛棚里，池塘和牛棚相距 \(D\) 个单位。

它们有 \(P\) 根水管，每根水管由 \(2\) 个整数来描述：水管长度 \(L_i\)，最大流量 \(C_i\) 。

水管可以依次连接构成一条运输管道，

那么这条运输管道的流量就是构成这条管道的所有水管中最小的一个流量。

但是，要让水从池塘通过运输管道流到牛棚里，

管道的长度必须恰好等于池塘和牛棚的距离（也就是说，水管长度 \(L_i\) 之和为 \(D\)）！

在只要求构造一条运输管道，求其最大流量。

二、完全背包

例题1：完全背包

有一个负重能力为 \(m(m \leq 300)\) 的背包和 \(n(n \leq 0)\) 种物品，

第 \(i\) 种物品的价值为 \(v[i]\)，重量为 \(w[i]\) 。

在不超过背包负重能力的前提下选择若干个物品装入背包，使这些物品的价值之和最大。

每种物品可以不选，也可以选择多个。假设每种物品都有足够的数量。

我们可以将其转换为 01背包。

状态：\(f[i][j]\)：前 \(i\) 种物品放入到容量为 \(j\) 的背包的最大权值

状态转移：\(f[i][j]=max(f[i][j],f[i-1][j-k \times v[i]]+k \times w[i]), \ 0 \leq k \times v[i] \leq c\)

我们在做 01背包 时倒着枚举第二层循环是为了保证物品只用 \(1\) 次

而完全背包并没有这个限制，每一个物品可以无限次使用

故只需要把 01背包 的第二层循环改为正序枚举即可

for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
        if(j-w[i]>=0) f[j]=max(f[j],f[j-w[i]]+v[i]);
printf("max=%d\n",f[m]);

例题2：质数和分解

任何大于 \(1\) 的自然数 \(n\) 都可以写成若干个大于等于 \(2\) 且小于等于 \(n\) 的质数之和表达式

（包括只有一个数构成的和表达式的情况），并且可能有不止一种质数和的形式。

例如，\(9\) 的质数和表达式就有四种本质不同的形式：

\(9 = 2 + 5 + 2 = 2 + 3 + 2 + 2 = 3 + 3 + 3 = 2 + 7\) 。

这里所谓两个本质相同的表达式是指：

可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。

试编程求解自然数 \(n\) 可以写成多少种本质不同的质数和表达式。

先进行质数筛，用 \(vis\) 数组标记 \(i\) 是否为质数。

状态：\(f[i][j]\)：前 \(i\) 个质数累加和为 \(j\) 的方案数

状态转移：\(f[j]=f[j]+f[j-i]\)

f[0]=1;
for(int i=1;i<=n;i++)
{
    if(vis[i]) continue;
    for(int j=2;j<=n;j++)
        if(j-i>=0) f[j]=f[j]+f[j-i];
}
printf("%d\n",f[n]);

练习：上课

新学期开始了，小Y就要选课上了。

小Y所在的学校有一个奇怪的上课系统，有 \(N\) 种课可以选择，

每种课可以重复的上，并且每次上都花掉同样的时间，获得同样的知识量。

小Y同学每天有一定的上课时间总额，他想获得最大的知识量，

你能告诉他最多能得到多少知识吗？

三、多重背包

例题：逃亡的准备

在《Harry Potter and the Deathly Hallows》中，Harry Potter他们一起逃亡，

现在有许多的东西要放到赫敏的包里面，但是包的大小有限，

所以我们只能够在里面放入非常重要的物品，现在给出该种物品的数量、体积、价值的数值

希望你能够算出怎样能使背包的价值最大的组合方式，

并且输出这个数值，赫敏会非常地感谢你。

状态：\(f[i][j]\)：前 \(i\) 种物品放入容量为 \(j\) 的背包的最大权值

状态转移：\(f[i][j]=max(f[i][j],f[i-1][j-k \times v[i]]+k \times w[i]),\ 0 \leq k \leq a[i]\)

如果单独枚举 \(k\)，效率较低，容易 TLE，因此可以进行二进制拆分，大幅减少枚举次数。