- 01背包：（无下限的术式）

例题：采药

Description

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。

医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

Input Format

输入的第一行有两个整数 T(1 <= T <= 1000)T(1<=T<=1000) 和 n(1<=n<=100) ，用一个空格隔开，TT 代表总共能够用来采药的时 间，nn代表山洞里的草药的数目。

接下来的 nn 行每行两个整数 t,c,(1≤t,c≤100)，分别表示采摘某 株草药的时间和这株草药的价值。

Output Format

输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以

采到的草药的最大总价值。

Sample 样例输入

70 3

71 100

69 1

1 2

样例输出

3

分析： 试求在背包有一定限制的情况下，利用物品价值特性所能放入的最大值。

符合01背包的特点，每次有两种选择，即选择物品或不选。

采用压维后的一维数组f[j]存储背包容量为j是所能取的最大值。

状态转移方程：f[j]=max(f[j],f[j−t[i]]+c[i])f[j] = max(f[j],f[j-t[i]]+c[i])

例题代码：

#include <bits/stdc++.h>
using namespace std;

int T,n,t[1005],c[1005],f[1005];//f[i][j]表示前i件草药放进时间为j的背包的最大价值 
int main()
{
	cin >> T >> n;
	for (int i = 1; i <= n; i++) cin >> t[i] >> c[i];
	for (int i = 1; i <= n; i++)//从取1件到取n件
	{
		for (int j = T; j >= t[i]; j--)//枚举每一t
		{
			f[j] = max(f[j],f[j-t[i]]+c[i]);
		}
	}
	cout << f[T] << endl;
	return 0;
}

-完全背包：（无上限的术式）

1.朴素版本

例题：完全背包问题

Description

设有 n 种物品，每种物品有一个重量及一个价值。

但每种物品的数量是无限的，同时有一个背包，最大载重量为 M。

请从 n 种物品中选取若干件 (同一种物品可以多次选取)，

使其重量的和小于等于 MM，而价值的和为最大。

Input Format

第一行：两个整数，M (背包容量，M<=200 )和 N (物品数量，N<=30 )；

第 2..N+1 行：每行二个整数 Wi,Ci，表示每个物品的重量和价值。

Output Format

仅一行，一个数，表示最大总价值。

Sample

样例输入

10 4
2 1
3 3
4 5
7 9

样例输出

max=12

分析：完全背包之所以有异与01背包，是因为它具有自身

的选择独特性，即每种物品的选择数量没有上限,（但会因背

包容量的限制受限）。

具体的，例如01背包进行dp时，因为有压栈，所以需要使内层循环

逆序遍历，这样才能使上次dp后的状态保留下来，不会发生改变。

完全背包则不然。当进入其内层循环时，因为可选的数量没有限制。

所以需要使内层循环正序遍历，因为其保留了当前状态下所能取得的

最大值，所以f[j]之前的数都会对上一次的状态发生一定改变，

对应的f[j]也会在其基础上进行选择，从而完成了dp过程。

例题代码：

#include <bits/stdc++.h>
using namespace std;

int n,m,w[35],c[35],f[35][205];

int main()
{
	cin >> m >> n;
	for (int i = 1; i <= n; i++) cin >> w[i] >> c[i];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int k = 0; k*w[i] <= j; k++)
				f[i][j] = max(f[i-1][j],f[i-1][j-k*w[i]]+k*c[i]);
	cout << "max=" << f[n][m] << endl;
	return 0;
}

2.二进制拆分

原理：任何数字都可以表示成若干个2的k次方数字的和，例如7可

以用2º+2¹+2²表示；这很好理解，因为任何正数都可以转成二进

制，二进制就是若干个“1”（2的幂数）之和。

基于以上原理，所以在此，我们把完全背包的模型进行优化，

即每次不会使f[j]只加c[i]，而是加2的k次方乘c[i]。使时间复杂度降为O(n*log(V/v[i])).

代码实现：


for (int i = 1; i <= 1; i++)
    for (int k = 1; k <= V/v[i]; k<<=1)//等于k*=2
        for (int j = V; j >= k*v[i]; j--)
            f[j] = max(f[j],f[j-k*v[i]]+k*c[i]);

- 多重背包

1.朴素版本

例题：庆功会

Description 为了庆贺班级在校运动会上取得全校第一名成绩，

班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。

期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

Input Format

第一行二个数n(n<=500)，m(m<=6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。

接下来n行，每行3个数，v、w、s，

分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买0件到s件均可），

其中v<=100，w<=1000，s<=10。

Output Format

第一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

Sample

样例输入

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

样例输出

1040

分析：并无很大改变，只是由完全背包的无上限改为了规定数量。

只需将循环次数降为规定数量即可

例题代码：


#include <bits/stdc++.h>
using namespace std;

int n,m,v[505],w[505],s[505],f[6005];

int main()
{
	cin >> n >> m;//奖品的种类和背包的容量
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];//每种所占空间，价值和数量
	for (int i = 1; i <= n; i++)//枚举每一种类 
		for (int j = m; j >= 0; j--)//逆序遍历每一种背包容量（与01背包类似） 
			for (int k = 0; k*v[i] <= j && k <= s[i]; k++)//枚举每一次选取几个i种物品 
				f[j] = max(f[j],f[j-k*v[i]]+k*w[i]);
	cout << f[m] << endl;
	return 0;
}

2.二进制优化

原理与完全背包的二进制拆分一模一样，不再详细介绍。

具体操作：将第i种物品分成若干件物品，其中每件物品有一个系

数，这件物品的体积和价值均是原来的体积和价值乘以这个系数。

使这些系数分别为2º,2¹,2²,...,2的k-1次方,b[i]-2k+1，

且k是满足b[i]-2k+1>0的最大整数。

例如，如果b[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。

例题：逃亡的准备

Description

每个人小时候都有自己的理想，但随着时间推移，

渐渐的大多数人的理想变成了金钱、地位、面子... 于是大多数人 就变成了传说中的俗人。

但我们的中中始终有自己的梦想，他要环游世界！

在 20XX 年 X 月 X 日中中开始环游世 界的准备工作。

他开始准备自己的行囊，中中背包的容积为 m ，

中中有 n 样有用的东西 ，每样东西都有自己的价值 Wi ，和体积 Vi，

每一样物品有Ni​个 （ Ni=0 时表示有无限多个），

于是乎我们的问题就是（你应该已经猜到了）...中中能带走的 东西的最大价值。

Input Format

第 11 行: N,M --物品的种类和背包的容积

第 2−N+1 行： Vi,Wi，Pi --三个整数：每个物品的体积、价值、个数。

Output Format

单独的一行在给定的限制里可能得到的最大的价值。

Sample

样例输入

5 50 
1 1 50
2 4 3
48 49 1
1 51 1
3 3 3

样例输出

106

Hint 30% 数据满足 1 <= m,n <=10001<=m,n<=1000

100% 数据满足 1 <=m,n <= 100001<=m,n<=10000

例题代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int n,m,n1,v[MAXN],w[MAXN],p[MAXN],f[MAXN];
bool a[MAXN];

int main()
{
	cin >> n >> m;
	n1 = 0;
	for (int i = 1; i <= n; i++)
	{
		int x,y,s,t = 1;//每种物品的体积，价值，数量及其二进制优化后分成的指数堆 
		cin >> x >> y >> s;
		if (s == 0)//如果是完全背包 
		{
			v[++n1] = x;//正常赋值 
			w[n1] = y;
			a[n1] = 0;//标记为完全背包 
			continue;
		}
		while (s >= t)
		{
			n1++;//数组数加1 
			v[n1] = x*t;//存入指数堆代表的物品数量的相应空间和价值 
			w[n1] = y*t;
			a[n1] = 1;//标记为多重背包 
			s -= t;
			t *= 2;//指数加1 
		}
		n1++;
		v[n1] = x*s;//存入整体 
		w[n1] = y*s;
		a[n1] = 1;
	}
	for (int i = 1; i <= n1; i++)
		if (a[i])//大于零是多重背包 
			for (int j = m; j >= v[i]; j--)
				f[j] = max(f[j],f[j-v[i]]+w[i]);
		else
			for (int j = v[i]; j <= m; j++)
				f[j] = max(f[j],f[j-v[i]]+w[i]);
	cout << f[m] << endl;
	return 0;
}

- 综合练习：混合背包

例题：混合背包

Description

一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，

它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

Input Format

第一行：二个整数，V(背包容量，V<=200)，N(物品数量，N<=30)；

第2..N+1行：每行三个整数Wi,Ci,Pi，前两个整数分别表示每个物品的重量，价值，

第三个整数若为0，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数(Pi)。

Output Format

仅一行，一个数，表示最大总价值。

Sample

样例输入

10 3
2 1 0
3 3 1
4 5 4

样例输出

11

例题代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int m,n,w[MAXN],c[MAXN],p[MAXN],f[MAXN];

int main()
{
	cin >> m >> n;
	for (int i = 1; i <= n; i++) cin >> w[i] >> c[i] >> p[i];//该物品的体积，价值和属性（是否为完全背包）
	for (int i = 1; i <= n; i++)
		if (p[i] == 0)//为完全背包
			for (int j = w[i]; j <= m; j++)
				f[j] = max(f[j],f[j-w[i]]+c[i]);
		else
			for (int k = 1; k <= p[i]; k++)//01背包或多重背包 
				for (int j = m; j >= w[i]; j--)
					f[j] = max(f[j],f[j-w[i]]+c[i]);
	cout << f[m] << endl;
	return 0;
}

- 二维费用背包

先看题：

例题：NASA的食物计划

Description

航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,

在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.

Input Format

第一行两个数体积最大值(<400)和质量最大值(<400)

第二行 一个数 食品总数N(<50).

第三行－第3+N行

每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)

Output Format

一个数 所能达到的最大卡路里(int范围内)

Sample

样例输入

320 350
4
160 40 120
80 110 240
220 70 310
40 400 22

样例输出

550

分析：相比较之前的DP来说，背包容量的限制又多了一个维度，其实不必过多考虑，只需是dp数组进行调节，循环次数增加维度即可

费用加了一维，只需状态也加一维即可。设f[i][j][k]表示前i件物品付出两种代价分别为j和k时可获得的最大价值。

状态转移方程就是：$f[i][j][k]=max{f[i-1][j][k],f[i-1][j-a[i]][j-b[i]]+c[i]}$

至于问题是0/1背包、完全背包还是多重背包直接套用一维的方法即可。

例题代码：

#include <bits/stdc++.h>
using namespace std;

int W,V,n,f[405][405],v[55],w[55],c[55];

int main()
{
	cin >> V >> W >> n;//体积和质量最大值以及物品种类数 
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> c[i];//具体的数值 
	for (int i = 1; i <= n; i++)//枚举每一种物品 
		for (int j = V; j >= v[i]; j--)//第一种性质（用01背包重的逆序更新） 
			for (int k = W; k >= w[i]; k--)//第二种性质 
				f[j][k] = max(f[j][k],f[j-v[i]][k-w[i]]+c[i]);
	cout << f[V][W] << endl;
	return 0;
}

- 分组背包

例题：分组背包

Description

一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。

这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。

求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

Input Format

第一行：三个整数，V(背包容量，V<=200)，N(物品数量，N<=30)和T(最大组号，T<=10)；

第2..N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。

Output Format

仅一行，一个数，表示最大总价值。

Sample

样例输入

10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3

样例输出

20

分析：分组背包与01背包十分相似，不同之处是分组背包一组内只能选一个，所以在判断时稍加改动即可。

具体的，每组物品要么一件不取，要么只取其中的一件，确实跟0/1背包很类似，0/1背包是对单个物品而言，

而分组背包是对分组而言定义f[i][j]表示第i组物品在背包容量为j对第i组的第k个物品进行决策的最大价值。

动态转移方程为:$f[i][j]=max(f[i-1][j],f[i-1][j-w[g[i][k]]]+c[g[i][k]])$

例题代码：

#include <bits/stdc++.h>
using namespace std;

int V,n,T,w[35],c[35],p[35],g[15][35],f[205];

int main()
{
   cin >> V >> n >> T;//背包容量，物品数和组数 
   for (int i = 1; i <= n; i++)
   {
   	cin >> w[i] >> c[i] >> p[i];//每个物品的重量，价值，所属组号
   	g[p[i]][0]++;//统计每一组内有多少物品 
   	g[p[i]][g[p[i]][0]] = i;//表示第p[i]组第g[p[i]][0]个的编号 
   }
   for (int i = 1; i <= T; i++)//遍历每一组 
   	for (int j = V; j >= 0; j--)//背包容量逆序遍历 
   		for (int k = 0; k <= g[i][0]; k++)//遍历i组中的元素。由于j在此循环中不变，且j对于V是逆序遍历，所以f[j-w[x]]的数值虽然会随x的变化而变化，但它属于上一个j的状态是始终不变的，所以遍历完k后f[V]就会保留i组中只选一个的最优解，从而在局部上构成了01背包的模型
   		 
   		{
   			int x = g[i][k];
   			if (j >= w[x]) f[j] = max(f[j],f[j-w[x]]+c[x]);
   		}
   cout << f[V] << endl; 
   return 0;
}

完[1]

  1. 下一章：动态规划：线性DP ↩︎

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 53ms
  4. Powered by Hydro v4.19.1 Community