—– 天泽龟

1、01 / 完全 / 多重 背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void zop(int c,int w){  //01 
	for(int i=n;i>=c;i--)
		f[i]=max(f[i],f[i-c]+w);
}
void cp(int c,int w){ //完全 
	for(int i=c;i<=n;i++)
		f[i]=max(f[i],f[i-c]+w);
}
void mp(int c,int w,int num){ //多重 
	if(c*num>=n) cp(c,w);
	else {
		int k=1;
		while(k<num){
			zop(k*c,k*w);
			num-=k;
			k<<=1;
		}
		zop(num*c,num*w);
	}
}

2、混合背包

分开处理，说着简单…

3、分组背包

先枚举容量，再枚举每组的物品

feizu

4、二维费用背包

碰到再说…

5、依赖背包

金明的预算方案

直接放题解… 题解

第一种方法 ：对于每种 主件+附件 共五种情况(本题)，枚举就行

第二种：背包九讲上关于依赖背包的方法。将每个主件和附件的集合看成一个物品组，可以先对主件及其附件集合进行一次 01 背包，得到费用一次为 $0…V - C_k$ 所有这些值时相应的最大价值 $F_k[0…V - C_k]$,那么这个主件及其附件集合相当于 $V - C_k + 1$个物品的物品组 ，其中费用为 $v$ 的物品价值为 $F_k[v - C_k] + W_k$ ,$v$ 的取值范围是 $C_k \leq v \leq V$ 。

然后再用分组背包的做法。

另一种：Solution [NOIP提高组2006]金明的预算方案

6、树形背包…

待补…

7、背包问题的变化

1）打印方案

我们设 $g[i][j]$表示当 $ f[i][j]$状态时的转移来源， $g[i][j]=0$即从 $ f[i-1][j]$ 转来的，$ g[i][j]=1$即从$ f[i-1][j-v[i]]$ 转移的.

1
2
3
4
5
fd(i,n,0)   // 这里应和求背包时的顺序相反
    if(g[i][V]){
        cout<<i<<" ";
        V -= c[i];
    }

2）求方案数

例题 1 ：小A点菜

只需要把转移方程改成 $ f[j]=\sum_{i=0}^n (f[j−v[i]]+w[i])$ 具体到就是 :

$f[i]=max(f[i],f[i-c]+w) \rightarrow f[i]=f[i]+f[i-c]$ , $f[0]=1$

例题 2 ：自然数累加问题

给定一个数 s ，在 1~to~n 中，求可累加任意数等于 s 的方案数。

例题3：P1832 A+B Problem（再升级）

给定一个正整数n，求将其分解成若干个素数之和的方案总数。

每个素数可以选若干次，如果可以。完全背包计数，正着计数

1
2
for(int i=c;i<=n;i++)//f[0]=1;
	f[i]+=f[i-c];

例题4：P1077 摆花

看着像多重背包计数？其实不是，对于每一种花，只能选择一个数量，比如选择了三个，不能拆成 2 + 1，否则会重复计数。其实更像分组背包，只能选择其中一个固定的值。

1
2
3
4
5
f[0]=1ll;
fi(i,0,n)
fd(j,m+1,1)
	for(int k=1;k<=a[i]&&k<=j;k++)
		f[j]+=f[j-k],f[j]%=MOD;

3）特定顺序的背包

例题：烹调方案

每件物品的价值和时间有关系。先排序后，套 01 背包。