子集型DP

这次来聊一聊DP中的子集型DP。

一.概述

DP，即动态规划。最优化问题是信息学竞赛的一大类题目， 动态规划是解决这类问题的有力武器， 但很多人在尝试理解并运用它时遇到极大的困难！当你学习了足够多的动态规划例题的时候，你会觉得它跟变魔术一样。

二.实质

动态规划实质就是记忆化搜索，是一种高效地实现回溯算法的方法，它的核心是用一个状态记忆表来记住所有中间状态的结果。因此我们要运用动态规划，首先需要发现朴素的回溯算法递归地一而再、再而三地计算一些相同的子问题，接下来需要把答案放在记忆表中而不重复计算。动态规划可以采用记忆化搜索，但记忆化搜索有其缺点，比如要用递归，不能优化空间。所以填表法作为动态规划实现的一种优化方法而广泛使用。

三.例题

1.背包问题

(1).01背包

有 $N$ 种物品，每种物品只有 $1$ 个。第 $i$ 种物品的体积为 $v[i]$，价值为 $p[i]$。选一些物品装入一个容量为 $C$ 的背包，使得背包内物品在总体积不超过 $C$ 的前提下价值尽量大。

分析：

[1].不正确的贪心

采用部分背包问题的贪心策略：按单位价值由大到小先装入背包，直到不能再装入物品为止。

设背包容量为 $50$，现有 $3$ 个物体：

物体 $1$： 体积为 $10$、价值为 $60$，单位价值为： $60/10=6$

物体 $2$： 体积为 $20$、价值为 $100$，单位价值为： $100/20=5$

物体 $3$： 体积为 $30$、价值为 $120$，单位价值为： $120/30=4$

如果按照贪心策略，选择物体 $1$ 和物体 $2$ 装入背包，体积和为 $30$，价值为和为 $160$。但是，如果选择物体 $2$ 和 $3$，则价值为 $220$。

所以在 $01$ 背包问题下，不能使用贪心策略，其错误的原因在于； 每个物品要么选，要么不选，不能只选部分，因此就可能有剩余空间，从而减小背包的单位价值。

[2].动态规划

显然这是子集生成问题。

1). 状态函数：

$f(i,j)$ 表示前 $i$ 个物品选择一些装入容量为 $j$ 的背包，所能获得最大价值；

2).问题的答案：

$ans=f(N,C)$；

3).状态转移方程：

根据分步决策的分析方法，可得出：

$f(i,j)=\max(f(i-1,j),p[i]+f(i-1,j-v[i]))(i>0)(j\geq0)(j-v[i]\geq0)$

4).边界分析：

$f(0,j)=0\ \ \ (j\geq0)$ //$0$ 个物品装入容量为 $j$ 的背包，最大价值为 $0$；

$f(i,0)=0\ \ \ (i\geq0)$ //$i$ 个物品装入容量为 $0$ 的背包，最大价值为 $0$。

5).优化：

通过状态转移数组可知，前 $i$ 个物品的状态只与 $i-1$ 层有关，故我们可以采用滚动数组优化，将二维降至一维。

$f(j)$ 代表选择物品装入容量为 $j$ 的背包时，能获得的最大价值。

$ans=f(C)$

$f(j)=\max(f(j),f(j-v[i])+p[i])\ \ \ (j-v[i]\geq0)$

边界：$f(j)=0\ \ \ (1\leq j \leq C)$

6).代码：

#include<stdio.h>
#include<string.h>
int c,n;
int v[101],p[101];
int num[101];
int f[10101];
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int min(int a,int b)
{
	if(a<b)
		return a;
	return b;
}
int main()
{
	scanf("%d%d",&c,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&v[i],&p[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&num[i]);
	for(int i=1;i<=n;i++)
		for(int j=c;j>=v[i];j--)//注意要倒着搜，填表从左向右填
			f[j]=max(f[j],f[j-v[i]]+p[i]);
	printf("%d\n",f[c]);
	return 0;
}

这里为什么要倒着搜呢？

很简单的原因，假如我们正着搜，则会出现以下情况：

1. $f[j]$ 被 $f[j-v[i]]+p[i]$ 更新。
2. $f[j+v[i]]$ 被 $f[j]+p[i]$ 更新。

很明显，在同一阶段内(即同时处于第 $i$ 阶段)，相当于我们用 DP 更新了两次状态，即使用了两次物品，违背了题目要求，故只能使用倒序搜索。

(2).多重背包

有 $N$ 种物品，每种物品只有 $n[i]$ 个。第 $i$ 种物品的体积为 $v[i]$，价值为 $p[i]$。选一些物品装入一个容量为 $C$ 的背包，使得背包内物品在总体积不超过 $C$ 的前提下价值尽量大。

1). 状态函数：

$f(j)$ 代表选择物品装入容量为 $j$ 的背包时，能获得的最大价值。

2).问题的答案：

$ans=f(C)$

3).状态转移方程：

$f[j]=\max(f[j],f[j-v[i]\times l]+p[i]\times l)\ \ \ (j-v[i]\geq 0)(0\leq l \leq t)(t=\min(n[i],\frac{j}{v[i]}))$

4).边界分析：

$f(j)=0\ \ \ (1\leq j \leq C)$

5).优化

多重背包有一种优化方式，能使它的时间复杂度降低一个层次。

这种优化方法通常称为二进制优化。

我们可以利用二进制拆分的方式，把 $n[i]$ 个物品拆分成多个不同的组合，$2^0$,$2^1$,$2^2$…,$2^k$ 为一组，将每一组看成一个整体，作为一个单独的物品。

然后多重背包就转换为 $01$ 背包了，直接用 $01$ 背包做就行了。

6).代码：

普通：

#include<stdio.h>
#include<string.h>
int c,n;
int v[101],p[101];
int num[101];
int f[10101];
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int min(int a,int b)
{
	if(a<b)
		return a;
	return b;
}
int main()
{
	scanf("%d%d",&c,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&v[i],&p[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&num[i]);
	for(int i=1;i<=n;i++)
		for(int j=c;j>=v[i];j--)//注意要倒着搜，填表从左向右填
		{
			int t=min(num[i],j/v[i]);
			for(int l=0;l<=t;l++)
				f[j]=max(f[j],f[j-v[i]*l]+p[i]*l);
		}
	printf("%d\n",f[c]);
	return 0;
}

优化：

#include<stdio.h>
#include<string.h>
int n,v,m[5010],w[5010],s[5010],w1[50100],s1[50100],cnt;
int f[510];
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int main()
{
	scanf("%d%d",&n,&v);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&m[i],&w[i],&s[i]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m[i];j<<=1)
		{
			w1[++cnt]=j*w[i];
			s1[cnt]=j*s[i];
			m[i]-=j;
		}
		if(m[i])
		{
			w1[++cnt]=m[i]*w[i];
			s1[cnt]=m[i]*s[i];
		}
	}
	for(int i=1;i<=cnt;i++)
		for(int j=v;j>=w1[i];j--)
			f[j]=max(f[j],f[j-w1[i]]+s1[i]);
	printf("%d",f[v]);
	return 0;
}

(3).完全背包

有 $N$ 种物品，每种物品有无穷多个。第 $i$ 种物品的体积为 $v[i]$，价值为 $p[i]$。选一些物品装入一个容量为 $C$ 的背包，使得背包内物品在总体积不超过 $C$ 的前提下价值尽量大。

1). 状态函数：

$f(j)$ 代表选择物品装入容量为 $j$ 的背包时，能获得的最大价值。

2).问题的答案：

$ans=f(C)$

3).状态转移方程：

$f(j)=\max(f(j),f(j-v[i])+p[i])\ \ \ (j-v[i]\geq0)$

4).边界分析：

$f(j)=0\ \ \ (1\leq j \leq C)$

5).代码：

#include<stdio.h>
#include<string.h>
int c,n;
int v[101],p[101];
int num[101];
int f[10101];
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int min(int a,int b)
{
	if(a<b)
		return a;
	return b;
}
int main()
{
	scanf("%d%d",&c,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&v[i],&p[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&num[i]);
	for(int i=1;i<=n;i++)
		for(int j=v[i];j<=c;j++)//注意！！！完全背包要正着搜，填表从右向左填，保证物品数量无限
			f[j]=max(f[j],f[j-v[i]]+p[i]);
	printf("%d\n",f[c]);
	return 0;
}

很明显，在 $01$ 背包我们曾说正着搜是将物品视为无限数量来搜的，这正好满足题目要求，所以正着搜。

(4).多费用背包

有 $N$ 个物品，第 $i$ 个物品的体积为 $vi$，重量为 $wi$，价值为 $pi$。选一些物品装到一个最大容量为 $C$，最大承重量为 $G$ 的背包，问如何选择装入背包的物品，使得装入背包的物品的总价值尽量大。

1). 状态函数：

相对于之前，选择一个物品装入背包，不仅要消耗背包的容积，还要消耗背包的承重量，所以这时设置状态函数应该有两个费用——体积和重量。于是状态函数相应增加一维。

$f(i,j)$ 表示选择一些物品装入容量为 $i$，承重量为 $j$ 的背包所获得的最大价值。

2).问题的答案：

$ans=f(C,G)$

3).状态转移方程：

$f(j,k)=\max(f(j,k),f(j-v[i],k-w[i])+p[i])\ \ \ (j-v[i]\geq0,k-w[i]\geq0)$

4).边界分析：

$f(j,k)=0\ \ \ (1\leq j \leq C,1\leq k\leq G)$

5).代码：

#include<stdio.h>
int c,g,n;
int v[101],w[101],p[101];
int f[2010][2010];
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int main()
{
	scanf("%d%d%d",&c,&g,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&v[i],&w[i],&p[i]);
	for(int i=1;i<=n;i++)
		for(int j=c;j>=v[i];j--)
			for(int k=g;k>=w[i];k--)
				f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+p[i]);
	printf("%d",f[c][g]);
	return 0;
}

(5).多数量背包

有 $N$ 种物品，每种只有一个，第 $i$ 种物品的体积为 $v[i]$，重量为 $w[i]$。现有两个背包，容量分别为为 $C_1$ 和 $C_2$ 的背包，问如何选择装入两个背包的物品，使得装入两个背包的物品的总价值尽量大。

1). 状态函数：

有两个背包，意味着每步有三种选择：物品 $i$ 不选、装入背包 $1$、装入背包 $2$(分 $3$ 堆)。

$f(i,j)$ 表示选择一些物品装入容量为 $i$ 和容量为 $j$ 的背包，所能得到的最大价值。

2).问题的答案：

$ans=f(C_1,C_2)$

3).状态转移方程：

$f(j,k)=\max(f(j,k),\max(f[j-v[i]][k]+w[i],f[j][k-v[i]]+w[i]))\ \ \ (j-v[i]\geq0,k-v[i]\geq0)$

4).边界分析：

$f(j,k)=0\ \ \ (1\leq j \leq C_1,1\leq k\leq C_2)$

5).代码：

#include<stdio.h>
#include<string.h>
int c1,c2,n;
int v[110],w[110];
int f[2010][2010];
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int main()
{
	scanf("%d%d%d",&c1,&c2,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&v[i],&w[i]);
	for(int i=1;i<=n;i++)
		for(int j=c1;j>=0;j--)
			for(int k=c2;k>=0;k--)
			{
				int x=-1e9,y=-1e9;
				if(j>=v[i])
					x=f[j-v[i]][k]+w[i];
				if(k>=v[i])
					y=f[j][k-v[i]]+w[i];
				f[j][k]=max(f[j][k],max(x,y));
			}
	printf("%d",f[c1][c2]);
	return 0;
}

(6).装满背包

给出 $N$ 个物品，第 $i$ 个物品的体积为 $v[i]$，价值为 $p[i]$,现在需要选择一些物品装满容量为 $C$ 的背包，所能获得的最大价值，如果不能装满，则输出 $-1$。

1). 状态函数：

本问题需要装满（而且必须装满），所以状态函数也应跟着改变：

$f(i)$ 表示选择一些物品装满容量为 $j$ 的背包能获得的最大价值。

2).问题的答案：

$ans=f(C)$

3).状态转移方程：

$f(j)=\max(f(j),f(j-v[i])+p[i])\ \ \ (j-v[i]\geq0)$

4).边界分析：

$f(0)=0$

$f(j)=-\infty\ \ \ (1\leq j \leq C)$

5).代码：

#include<stdio.h>
#include<string.h>
#define INF 0x7f7f7f7f
int c,n,k;
int v[101],p[101];
int f[20101];
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int main()
{
	scanf("%d%d",&c,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&v[i],&p[i]);
	scanf("%d",&k);
	memset(f,-INF,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=c;j>=v[i];j--)
			f[j]=max(f[j],f[j-v[i]]+p[i]);
	if(f[c]==-2122219118)
		printf("-1\n");
	else
		printf("%d\n",f[c]);
	return 0;
}

(7).K背包

给出 $N$ 个物品，第 $i$ 个物品的体积为 $v[i]$，价值为 $p[i]$,现在需要选择 $K$ 个装入容量为 $C$ 的背包，所能获得的最大价值，如果无解，则输出 $-1$。

1). 状态函数：

本问题需要选 $K$ 个物品装入容量为 $C$ 的背包（不一定要装满），所以状态函数变为：$f(k,j)$ 表示选择 $k$ 个物品装入容量 $j$ 的背包所能获得最大价值。

2).问题的答案：

$ans=\max(f(k,i))\ \ \ (0 \leq i \leq C)$

3).状态转移方程：

$f(j,k)=\max(f(j,k),f(j-1)(k-v[i])+p[i])\ \ \ (k-v[i]\geq0)(1 \leq j \leq K)$

4).边界分析：

$f(0,i)=0\ \ \ (0 \leq i \leq C)$

$f(k,i)=-\infty\ \ \ (1\leq k \leq K)$

5).代码

#include<stdio.h>
#include<string.h>
#define INF 0x7f7f7f7f
int c,n,k;
int v[101],p[101];
int dp[101][20101],ans;
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int main()
{
	scanf("%d%d",&c,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&v[i],&p[i]);
	memset(dp,-INF,sizeof(dp));
	for(int i=0;i<=k;i++)
		dp[0][i]=0;
	for(int i=1;i<=n;i++)
		for(int j=k;j>=1;j--)
			for(int k=c;k>=v[i];k--)
				dp[j][k]=max(dp[j][k],dp[j-1][k-v[i]]+p[i]);
	ans=dp[k][c];
	for(int i=0;i<=c;i++)
		ans=max(ans,dp[k][i]);
	if(ans<0)
		printf("-1\n");
	else
		printf("%d\n",ans);
	return 0;
}

(8).分组背包

有 $n$ 个物品，编号为 $1..n$，编号为 $i$ 的物品的体积为 $v[i]$，价值为 $p[i]$。

有 $m$ 个同样的背包，编号为 $1..m$，他们的最大容积都为 $C$。

现在需要选择一些物品装入这些背包，要求编号大的背包装入的物品不能比编号小的背包装入物品的编号小，具体地说，不允许把编号为 $2$ 的物品装入背包 $1$，然后把编号为 $1$ 物品装入背包 $2$ 的情况出现，也就是说，物品时按编号由小到大的顺序装入背包的，并且只有在背包 $1$ 不能再装物品时，才开始装背包 $2$！

请你计算 $m$ 个背包能装入物品的最大价值！

1).状态函数

这里我用了最笨拙的办法。

$f(i,j,k)$ 表示装第 $i$ 个背包，装第 $j$ 个物品时，背包容量为 $k$ 所能得到的最大价值。

2).问题的答案

$ans=f(m,n,c)$

3).状态转移方程

决策有三个：

1.不选这个物品

2.选这个物品，装一个新的空背包

3.选这个物品，装正在放未放满的背包

故状态转移方程如下：

int t=f[i][j-1][k];//不选
if(k>=v[j])
{
    t=max(t,f[i-1][j-1][c]+p[j]);//装一个新的空背包
    t=max(t,f[i][j-1][k-v[j]]+p[j]);//装正在放未放满的背包
}
f[i][j][k]=t;

4).边界条件分析

$f(i,j,k)=0\ \ \ (0 \leq i \leq m)(0 \leq j \leq n)(0 \leq k \leq c)$

5).代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,c;
int v[25],p[25];
int f[25][25][205];
int main()
{
	memset(f,0,sizeof(f));
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&v[i],&p[i]);
	for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            for(int k=0;k<=c;k++)
            {
                int t=f[i][j-1][k];
                if(k>=v[j])
                {
                    t=max(t,f[i-1][j-1][c]+p[j]);
                    t=max(t,f[i][j-1][k-v[j]]+p[j]);
                }
                f[i][j][k]=t;
            }
	printf("%d",f[m][n][c]);
	return 0;
}

(9).背包问题总结

1).动态规划是解决最优性问题的有力武器，其的关键是状态函数和状态转移方程

状态函数的定义一般根据题目的问题，问什么设什么，且要充分包含题目描述中的各“变量”。状态转移方程的就是要决策达到当前状态的最优值，有那些选项，并从这些选项中决策出最优的选项。

2).动态规划状态函数的边界分析是基础

动态规划通过状态函数的逐步转移来计算目标状态的最优值的，但必须要有一个转移的起点，分析边界时一般根据状态函数中变量的意义来确定，或者根据填表法或记忆化搜索的过程来分析。

另外，边界一般可能的值是：$0$ ，$\infty$ 或 $-\infty$。

$0$ 一般表示边界状态可行；

$\infty$ 一般表示计算最小值的时候边界状态不可行；

$-\infty$ 一般表示计算最大值的时候边界状态不可行。

2.多米诺骨牌

多米诺骨牌有上下 $2$ 个方块组成，每个方块中有 $1\sim6$ 个点。现有排成行的 $n$ 个多米诺骨牌如图所示。

上方块中点数之和记为:$Sum1$，下方块中点数之和记为:$Sum2$，它们的差为:$|Sum1-Sum2|$ 。例如在图中,$Sum1=6+1+1+1=9$,$Sum2=1+5+3+2=11$, $|Sum1-Sum2|=2$。每个多米诺骨牌可以旋转 $180$ 度，使得上下两个方块互换位置。

编程用最少的旋转次数使多米诺骨牌上下 $2$ 行点数之差达到最小。

对于图中的例子，只要将最后一个多米诺骨牌旋转 $180$ 度，可使上下 $2$ 行点数之差为 $0$。

1).状态函数

根据总结中的“题目问什么就设什么意义的状态函数”，于是定如下意义的状态函数 $f(i,j)$ 表示前 $i$ 个骨牌中得到上下两行点数之差为 $j$，需要的最少旋转次数。

2).问题的答案

在求答案之前，请深刻理解下面这些状态表达式的含义：

$if(f(n,j)<\infty)$ 则说明前 $n$ 个骨牌在上下两行差为 $j$ 时需要的最小旋转次数。

$if(f(n,j)==\infty)$ 则说明前 $n$ 个骨牌在上下两行差为 $j$ 时不可行。

因为题目中要得到的答案是“在上下两行点数差的绝对值最小的前提下，需要的最少旋转次数”，所以答案应按如下方式计算：

int ans=0;
for(int j=0;j<=cnt;j++)
{
	if(f(n,j)<INF)
	{
		ans=f(n,j);
		break;
	}
	if(f(n,-j)<INF)
	{
		ans=f(n,-j);
		break;
	}
}

3).状态转移方程

按照总结中说的“要达到 $f(i,j)$ 的状态，面临的选项”有：

选项 $1$： 第 $i$ 个骨牌不旋转，则状态转移为 $f(i-1,j-(a[i]-b[i]))$

选项 $2$： 第 $i$ 个骨牌旋转 $1$ 次，则状态转移为 $1+f(i-1,j-(b[i]-a[i]))$

所以，要达到 $f(i,j)$ 的决策就是：

$f(i,j)=min(f(i-1,j-(a[i]-b[i])),1+f(i-1,j-(b[i]-a[i])))$

4).边界条件

根据总结中说的 $0$ 表示可行，求最小值时 $\infty$ 表示不可行，所以：

$f(0,0)=0$ 表示 $0$ 个骨牌达到上下两行点数差为 $0$ 时，需要的最少旋转次数为 $0$

$f(0,j)=\infty$ 表示 $0$ 个骨牌达到上下两行点数差为 $j(j>0)$，显然这个状态永远也不能达到，所以为 $\infty$

5).代码实现技巧

根据状态函数 $f(i,j)$ 的意义，$j$ 的范围是 $-tot<=j<=tot$($tot$ 为骨牌点数和)，需要支持负数下标，但 $\text{C++}$ 数组不支持负数下标，所以需要“平移下标”。

在使用平移数组时，需要注意数组定义平移后的大小：int f[1005][2*6000];

6).代码

#include<cstdio>
#include<algorithm>
#define f(x,y) f[(x)][(y)+cnt]
#define INF 1e9
using namespace std;
int n,a[1010],b[1010];
int f[1010][12010],cnt;
int min(int a,int b)
{
	if(a<b)
		return a;
	return b;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		cnt+=a[i];
		cnt+=b[i];
	}
	for(int i=-cnt;i<=cnt;i++)
		f(0,i)=INF;
	f(0,0)=0;
	for(int i=1;i<=n;i++)
		for(int j=cnt;j>=-cnt;j--)
			f(i,j)=min(f(i-1,j-(a[i]-b[i])),1+f(i-1,j-(b[i]-a[i])));
	int ans=0;
	for(int j=0;j<=cnt;j++)
	{
		if(f(n,j)<INF)
		{
			ans=f(n,j);
			break;
		}
		if(f(n,-j)<INF)
		{
			ans=f(n,-j);
			break;
		}
	}
	printf("%d",ans);
	return 0;
}

3.最大约数和

选取和不超过 $S$ 的若干不同正整数，使得所有数的约数（不含它本身）和为最大！

1).状态函数

通过仔细观察题目可知，这道题其实是一个稍微变换了一下的 $01$ 背包问题，我们可以把 $S$ 想成背包容量，每一个数则是一种物品的体积，而这个数的约数和则是它的价值。

这就很好办了，我们可以很快设出状态函数：

$f(j)$ 代表选取不超过 $j$ 的若干不同正整数，使得所有数的约数（不含它本身）和为最大。

2).代码

因为这是一个裸的 $01$ 背包问题，我就直接放代码了。

#include<stdio.h>
int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
int f[1001],n,c[1001],w[1001],i,j;
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        w[i]=i;
        for(j=1;j<i;j++)
            if(i%j==0)
                c[i]+=j;
    }
    for(i=1;i<=n;i++)
        for(j=n;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("%d",f[n]);
}

4.金明的预算

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	电脑	书柜	书桌	工作椅
附件	打印机，扫描仪	图书	台灯，文具	无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 $N$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1\sim5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是 $10$ 元的整数倍）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v[j]$，重要度为 $p[j]$，共选中了 $k$ 件物品，编号依次为 $j_1$,$j_2$,…,$j_k$，则所求的总和为：

$v[j_1] \times p[j_1]+v[j_2] \times p[j_2]+ …+v[j_k] \times p[j_k]$。

请你帮助金明设计一个满足要求的购物单。

1).状态函数

这其实也是一个背包问题，它属于有依赖的背包问题。

所以我们的状态函数和普通背包问题的状态函数相同。

$f(j)$ 表示购买物品不超过 $j$ 元钱，物品的价格与重要度乘积的总和的最大值。

2).问题的答案

$ans=f(n)$

3).代码实现技巧

我们用 $zw(i),zv(i)$ 存储第 $i$ 个主件的费用和价值。

即 $zw(i)=v,zv(i)=v\times p$；

我们用 $fw(i,j),fv(i,j)$ 来存储关于附件的信息，其中 $j=0,1,2$。

如果 $j=0$，则数组表示第 $i$ 个主件的附件数量；

如果 $j=1,2$，则数组表示第 $i$ 个主件的附件 $1$ 和附件 $2$ 分别的费用和价值。

4).状态转移方程

这道题和普通背包问题的不同点在于它的决策不同。

普通背包问题只有两个决策：

1.不选，考虑下一个物品

2.选，背包容量减去物品体积，总价值加上物品价值。

但这道题决策有五个：

1.不选，考虑下一个物品

2.选且只选这个主件

3.选这个主件，并且选附件 $1$

4.选这个主件，并且选附件 $2$

5.选这个主件，并且选附件 $1$ 和附件 $2$

所以，状态方程如下所示：

f[j]=max(f[j],f[j-zw[i]]+zv[i]);//不选和只选主件
if(j-zw[i]-fw[i][1]>=0)//选主件和附件1
    f[j]=max(f[j],f[j-zw[i]-fw[i][1]]+zv[i]+fv[i][1]);
if(j-zw[i]-fw[i][2]>=0)//选主件和附件2
    f[j]=max(f[j],f[j-zw[i]-fw[i][2]]+zv[i]+fv[i][2]);
if(j-zw[i]-fw[i][1]-fw[i][2]>=0)//选主件和附件1，2
    f[j]=max(f[j],f[j-zw[i]-fw[i][1]-fw[i][2]]+zv[i]+fv[i][1]+fv[i][2]);

5).边界条件

$f[j]=0\ \ \ (0 \leq j \leq n)$

6).代码

#include<stdio.h>
int n,m,zv[32001],zw[32001],fv[32001][3],fw[32001][3],dp[32001];
int v,p,q;
int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v,&p,&q);
        if(q==0)
        {
            zw[i]=v;
            zv[i]=v*p;
        }
        else
        {
            fw[q][0]++;
            fw[q][fw[q][0]]=v;
            fv[q][fw[q][0]]=v*p;
        }
    }
    for(i=1;i<=m;i++)
        for(j=n;j-zw[i]>=0&&zw[i]!=0;j--)
        {
            dp[j]=max(dp[j],dp[j-zw[i]]+zv[i]);
            if(j-zw[i]-fw[i][1]>=0)
                dp[j]=max(dp[j],dp[j-zw[i]-fw[i][1]]+zv[i]+fv[i][1]);
            if(j-zw[i]-fw[i][2]>=0)
                dp[j]=max(dp[j],dp[j-zw[i]-fw[i][2]]+zv[i]+fv[i][2]);
            if(j-zw[i]-fw[i][1]-fw[i][2]>=0)
                dp[j]=max(dp[j],dp[j-zw[i]-fw[i][1]-fw[i][2]]+zv[i]+fv[i][1]+fv[i][2]);
        }
    printf("%d",dp[n]);
    return 0;
}

5.物品选取

小沐同学确信所有问题都有个多项式时间算法，为了证明，他决定自己去当一次旅行商，在上路之前，小 $X$ 需要挑选一些在路上使用的物品，但他只有一个能装体积为 $m$ 的背包。显然，背包问题对小沐来说过于简单了，所以他希望你来帮他解决这个问题。

小沐可以选择的物品有 $n$ 样，一共分为甲乙丙三类：

1. 甲类物品的价值随着你分配给他的背包体积变化，它的价值与分配给它的体积满足函数关系式，$v(x) = Ax^2-Bx$，$x$ 表示分配给该物品的体积，为非负整数，$A$，$B$ 是每个甲类物品的两个参数。注意每个体积的甲类物品只有一个。
2. 乙类物品的价值 $A$ 和体积 $B$ 都是固定的，但是每个乙类物品都有个参数 $C$，表示这个物品可供选择的个数。
3. 丙类物品的价值 $A$ 和体积 $B$ 也是固定的，但是每个丙类物品可供选择的个数都是无限多个。

你最终的任务是确定小沐的背包最多能装有多大的价值上路。

1).状态函数

很明显这也是一个背包问题，这是一个混合背包问题。

容易可以看出，第 $2$ 类物品属于多重背包，第 $3$ 类物品属于完全背包。

第 $1$ 类是一种新的背包类型，这时物品价值随分配给它的体积变化，属于泛化背包。

所以我们还是和以前一样的状态函数：

$f(j)$ 代表选择物品装入容量为 $j$ 的背包时，能获得的最大价值。

2).问题的答案

$ans=\max(f(i))\ \ \ (0 \leq i \leq m)$

这里由于第 $1$ 类的背包分配给的体积随时在变化，所以使得整个背包价值最大时的体积并不一定是 $m$，所以要重新遍历检索一遍。

3).状态转移方程

这要看物品的类型。

对于类型 $1$：$f[j]=\max(f[j],f[j-k]+s[i].a\times k^2 -s[i].b\times k)$；

对于类型 $2$：$f[j]=\max(f[j],f[j-k\times s[i].b]+k\times s[i].a)$；

对于类型 $3$：$f[j]=\max(f[j],f[j-s[i].b]+s[i].a)$。

4).边界条件

$f[0]=0$

$f[i]=-\infty\ \ \ (1 \leq i \leq m)$

因为这里类型 $1$ 物品的价值可能为负，所以要设为 $-\infty$。

5).代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
struct thing
{
	int x;
	int a;
	int b;
	int c;
}s[110];
int f[2010];
int main()
{
	memset(f,-0x3f,sizeof(f));
	f[0]=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i].x);
		if(s[i].x==2)
			scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
		else
			scanf("%d%d",&s[i].a,&s[i].b);
	}
	for(int i=1;i<=n;i++)
	{
		if(s[i].x==1)
		{
			for(int j=m;j>=0;j--)
				for(int k=j;k>=0;k--)
					f[j]=max(f[j],f[j-k]+s[i].a*k*k-s[i].b*k);
		}
		else if(s[i].x==2)
		{
			for(int j=m;j>=s[i].b;j--)
				for(int k=0;k<=s[i].c&&k*s[i].b<=j;k++)
						f[j]=max(f[j],f[j-k*s[i].b]+k*s[i].a);
		}
		else
		{
			for(int j=s[i].b;j<=m;j++)
				f[j]=max(f[j],f[j-s[i].b]+s[i].a);
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++)
		ans=max(ans,f[i]);
	printf("%d",ans);
	return 0;
}