九背包上的发言稿_01背包

从Tianyi Cui童鞋《背包问题讲9》。细微的变化，很容易理解。

01背包问题描写叙述

已知:有一个容量为V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。

限制:每种物品仅仅有一件，能够选择放或者不放

问题:在不超过背包容量的情况下，最多能获得多少价值或收益

相似问题:在恰好装满背包的情况下，最多能获得多少价值或收益

这里，我们先讨论在不超过背包容量的情况下。最多能获得多少价值或收益。

基本思路

01背包的特点:每种物品仅仅有一件，能够选择放或者不放

子问题定义状态

f[i][v] : 前i件物品放到一个容量为v的背包中能够获得最大价值

状态转移方程

f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + cost[i])

分析

考虑我们的子问题，将前i件物品放到容量为v的背包中。若我们仅仅考虑第i件物品时。它有两种选择，放或者不放。

1) 假设第i件物品不放入背包中。那么问题就转换为：将前i - 1件物品放到容量为v的背包中。带来的收益f[i - 1][v]

2) 假设第i件物品能放入背包中。那么问题就转换为：将前i - 1件物品放到容量为v - weight[i]的背包中，带来的收益f[i - 1][v - weight[i]] + cost[i]

代码

#include 
using namespace std;

const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值

int f[N + 1][V + 1] = {{0}};

int Max(int x,int y)
{
	return x > y ? x : y;
}

/*
目标：在不超过背包容量的情况下，最多能获得多少价值

子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值

状态转移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] + value[i]}

初始化:f数组全设置为0
*/
int Knapsack()
{
	//初始化
	memset(f,0,sizeof(f));
	//递推
	for (int i = 1;i <= N;i++) //枚举物品
	{
		for (int j = 0;j <= V;j++) //枚举背包容量
		{
			f[i][j] = f[i - 1][j];
			if (j >= weight[i])
			{
				f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i]);
			}
		}
	}
	return f[N][V];
}

int main()
{
	cout<
效率分析：
此算法的时间复杂度为O(N*V)，空间复杂度也为O(N*V)。当中，N 表示物品个数，V 表示背包容量这里，时间复杂度不能够在优化了。可是空间复杂度能够继续优化到O(V)
优化空间复杂度
上述的方法，我们使用二维数组 f[i][v] 保存中间状态，这里我们能够使用一维数组f[v]保存中间状态就能得到结果
分析
我们如今使用f[v]保存中间状态。我们想要达到的效果是。第i次循环后，f[v]中存储的是前i个物体放到容量v时的最大价值
在回想下之前讲过的状态转移方程：
f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + cost[i])
我们能够看到，要想得到 f[i][v]，我们须要知道 f[i - 1][v] 和 f[i - 1][v - weight[i]]，因为我们使用二维数组保存中间状态，所以能够直接取出这两个状态。

当我们使用一维数组存储状态时，f[v]表示。在运行i次循环后(此时已经处理i个物品)。前i个物体放到容量v时的最大价值。即之前的f[i][v]。与二维相比較，它把第一维隐去了，可是二者表达的含义还是同样的，仅仅只是针对不同的i。f[v]一直在反复使用。所以。也会出现第i次循环可能会覆盖第i - 1次循环的结果。
为了求f[v],我们须要知道，前i - 1个物品放到容量v的背包中带来的收益，即之前的f[i - 1][v]  和 前i - 1件物品放到容量为v - weight[i]的背包中带来的收益，即之前的f[i - 1][v - weight[i]] + cost[i]。
难点：由于我们仅仅使用一维数组存储，则在求这两个子问题时就没有直接取出那么方便了。由于，第i次循环可能会覆盖第i - 1次循环的结果。
如今我们来求这两个值
1）前i - 1个物品放到容量v的背包中带来的收益。即之前的f[i - 1][v] ：
因为，在运行在i次循环时。f[v]存储的是前i个物体放到容量v时的最大价值。在求前i个物体放到容量v时的最大价值(即之前的f[i][v])时，我们是正在运行第 i 次循环。f[ v ]的值还是在第 i - 1  次循环时存下的值，在此时取出的 f[ v ]就是前i - 1个物体放到容量v时的最大价值。即f[i - 1][v]。
2）前i - 1件物品放到容量为v - weight[i]的背包中带来的收益，即之前的f[i - 1][v - weight[i]] + cost[i]
因为，在运行第i次循环前。f[0 ~ V]中保存的是第i - 1次循环的结果。即是前i - 1个物体分别放到容量0 ~ V时的最大价值，即f[i - 1][0 ~ V]。
则。在运行第i次循环前。f 数组中v - weight[i]的位置存储就是我们要找的 前i - 1件物品放到容量为v - weight[i]的背包中带来的收益 (即之前的f[i - 1][v - weight[i]])，这里如果物品是从数组下标1開始存储的。
伪代码
for i=1..N //枚举物品
    for v=V..0 //枚举容量。从大到小
        f[v]=max{f[v],f[v-weight[i]] + cost[i]};
由上面伪代码可知，在运行第 i 次循环时。须要把背包容量由V..0都要遍历一遍，检測第 i 件物品能否放。
逆序枚举容量的原因：
注意一点，我们是由第 i - 1 次循环的两个状态推出 第 i 个状态的。并且 v  > v - weight[i]，则对于第i次循环，背包容量仅仅有当V..0循环时。才会先处理背包容量为v的状况。后处理背包容量为 v-weight[i] 的情况。

详细来说。因为，在运行v时，还没运行到v - weight[i]的，因此。f[v - weight[i]]保存的还是第i - 1次循环的结果。
即在运行第i次循环 且 背包容量为v时，此时的f[v]存储的是 f[i - 1][v] 。此时f[v-weight[i]]存储的是f[i - 1][v-weight[i]]。

相反。假设在运行第 i 次循环时，背包容量依照0..V的顺序遍历一遍。来检測第 i 件物品能否放。此时在运行第i次循环 且 背包容量为v时，此时的f[v]存储的是 f[i - 1][v] 。可是，此时f[v-weight[i]]存储的是f[i][v-weight[i]]。

由于。v  > v - weight[i]。第i次循环中。运行背包容量为v时。容量为v - weight[i]的背包已经计算过，即f[v - weight[i]]中存储的是f[i][v - weight[i]]。
即，对于01背包，依照增序枚举背包容量是不正确的。

代码
#include 
using namespace std;

const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值

int f[V + 1] = {0};

int Max(int x,int y)
{
	return x > y ? x : y;
}

/*
目标：在不超过背包容量的情况下。最多能获得多少价值

子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值

状态转移方程:f[j] = max{f[j],f[j - weight[i]] + value[i]}

初始化:f数组全设置为0
*/
int Knapsack()
{
	//初始化
	memset(f,0,sizeof(f));
	//递推
	for (int i = 1;i <= N;i++) //枚举物品
	{
		for (int j = V;j >= weight[i];j--) //枚举背包容量,防越界，j下限为 weight[i]
		{
			f[j] = Max(f[j],f[j - weight[i]] + value[i]);
		}
	}
	return f[V];
}

int main()
{
	cout<
可是，增序枚举背包容量会达到什么效果：它会反复的装入某个物品。并且尽可能多的，使价值最大，当然不会不超过背包容量
而逆序枚举背包容量：背包中的物品至多装一次，使价值最大，当然不会不超过背包容量
我们首先举例说明：
逆序枚举物品

当i = 2，我们要求 f [5]：表示检測物品2放入容量为5的背包的最大收益
上图表示，当i = 2。求f[5]时f数组的状况，
橙色为数组如今存储的值，这些值是i = 1时(上一次循环)存入数组 f 的。相当于f[i - 1][v]
而黄色使我们要求的值，在求f[5]之前，f[5]= 5。即f[i - 1][5] = 5
如今要求 i = 2 时的f[5] = f[5 - 2] + 10 = 5 + 10 = 15  >  f[i - 1][5] = 5
故，f[5] = 15；
注意一点，在求f[v]时，它引用的 f[v - weight[i]] 和 f[v]都是上一次循环的结果
顺序枚举物品

当i = 2，我们要求 f [5]：表示检測物品2放入容量为5的背包的最大收益
上图表示，当i = 2，求f[5]时f数组的状况，
橙色为数组如今存储的值。这些值是i = 2时(本次循环)存入数组 f 的。
相当于f[i][v]
这是因为。我们是增序遍历数组f的。在求f[v]时。v之前的值(0 ~ v - 1)都已经在第i次循环中求出。
而黄色使我们要求的值。在求f[5]之前，f[5]= 5，即f[i - 1][5] = 5
如今要求 i = 2 时的f[5] = f[5 - 2] + 10 =10+ 10 = 20 >  f[i - 1][5] = 5
故，f[5] = 20；
当中引用的f[3]是相当于f[i][3] 而不是正常的f[i - 1][3]
注意一点，在求f[v]时，它引用的 f[v - weight[i]]是本次循环的结果 而f[v]是上一次循环的结果
换个角度说。
在检測 背包容量为5时。看物品2是否增加
由状态转移方程可知。我们f[5]须要引用自己本身和f[3]
因为背包容量为3时，能够装入物品2，且收益比之前的大。所以放入背包了。
在检測f[5]时，肯定要加上物品2的收益，而f[5]在引用f[3]时，f[3]时已经加过一次物品2。
因此。在枚举背包容量时。物品2会增加多次。

进一步说：
我们观察一维状态转移方程：
f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + cost[i])
首先我们明白三个问题
1) v - weight[i] < v
2) 状态f[i][v] 是由 f[i - 1][v] 和 f[i - 1][v - weight[i]] 两个状态决定
3) 对于物品i。我们在枚举背包容量时，仅仅要背包容量能装下物品i 且 收益比原来的大。就会成功放入物品i。



详细来说，枚举背包容量时，是以递增的顺序的话，因为 v - weight[i] < v,则会先计算 v - weight[i]。在背包容量为v - weight[i]时，一旦装入了物品i。因为求f[v]须要使用f[i - 1][v - weight[i]]，而若求f[v]时也能够装入物品i的话，那么在背包容量为v时，容量为v的背包就装入可两次物品。又若v - weight[i]是由之前的状态推出，它们也成功装入物品i的话，那么容量为v的背包就装入了多次物品i了。


注意，此时。在计算f[v]时，已经把物品i能装入的全装入容量为v的背包了，此时装入物品i的次数为最大啊



事实上，顺序枚举容量是全然背包问题最简捷的解决方式。
 
初始化的细节问题
求最优解的背包问题时，有两种问法：
1)在不超过背包容量的情况下。最多能获得多少价值
2)在恰好装满背包的情况下，最多能获得多少价值
基本的差别为是否要求恰好装满背包。但这两种问法的实现方法是在初始化的时候有所不同。

1)恰好装满背包的情况：使用二维数组f[i][v]存储中间状态。当中第一维表示物品。第二维表示背包容量
初始化时。除了f[i][0] = 0（第一列）外。其它全为负无穷。

原因：初始化 f 数组就是表示：在没有不论什么物品能够放入背包时的合法状态。
对于恰好装满背包，仅仅有背包容量为 0（第一列）。能够什么物品都不装就能装满，这样的情况是合法情况，此时价值为0。其它f[0][v]（第一列）是都不能装满的，此时有容量没物品。
而其它位置（除去第一行和第一列的位置），我们为了在计算中比較最大值，也要初始化为负无穷。我们从程序的角度上看，我们仅仅同意装入背包物品的序列的起始位置是从第一列開始，这些起始位置都是合法位置。且能恰好装满的情况收益均为正值，到f[N][V]终止。

注意，我们尽管是求恰好装满，还是须要枚举全部能够装入背包的物品，仅仅要能装入，还需装入。收益有添加。仅仅只是。因为恰好装满的物品的序列肯定是从第一列某行開始的，且之后的收益肯定是正值。对于非恰好装满的物品序列，事实上位置肯定是从第一行某位置開始的，因为此时被初始化为负无穷。在和那些恰好装满物品序列带来的价值时，肯定是小的。所以，我们最后能获得最大值。
代码：
#include 
using namespace std;

const int MinNum = 0x80000000;

const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值

int f[N + 1][V + 1] = {{0}};

int Max(int x,int y)
{
	return x > y ? x : y;
}

/*
目标：在恰好装满背包的情况下，最多能获得多少价值

子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值

状态转移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] + value[i]}

初始化:f数组全设置为0
*/
int Knapsack()
{
	//初始化
	for (int i = 0;i <= N;i++) //枚举物品
	{
		for (int j = 0;j <= V;j++) //枚举背包容量
		{
			f[i][j] = MinNum;
		}
	}
	for (int i = 0;i <= N;i++)
	{
		f[i][0] = 0;//背包容量为0时为合法状态
	}
	//递推
	for (int i = 1;i <= N;i++) //枚举物品
	{
		for (int j = 1;j <= V;j++) //枚举背包容量
		{
			f[i][j] = f[i - 1][j];
			if (j >= weight[i])
			{
				f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i]);
			}
		}
	}
	return f[N][V];
}

int main()
{
	cout<
使用一维数组f[v]存储中间状态，维表示背包容量
初始化时，除了f[0] = 0。其它全为负无穷。

原因：仅仅有容量为0 的背包能够什么物品都不装就能装满，此时价值为0。其他容量的背包均没有合法的解，属于没有定义的状态，应该被赋值为负无穷了
代码
#include 
using namespace std;

const int MinNum = 0x80000000;//int最小的数

const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值

int f[V + 1] = {0};

int Max(int x,int y)
{
	return x > y ? x : y;
}

/*
目标：在恰好装满背包容量的情况下。最多能获得多少价值

子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值

状态转移方程:f[j] = max{f[j],f[j - weight[i]] + value[i]}

初始化:f数组全设置为0
*/
int Knapsack()
{
	//初始化
	for (int i = 0;i <= V;i++)
	{
		f[i] = MinNum;
	}
	f[0] = 0;//仅仅有背包容量为0时才是合法状态。由合法状态组成的结果才是合法的

	//递推
	for (int i = 1;i <= N;i++) //枚举物品
	{
		for (int j = V;j >= weight[i];j--) //枚举背包容量,防越界。j下限为 weight[i]
		{
			f[j] = Max(f[j],f[j - weight[i]] + value[i]);
		}
	}
	return f[V];
}

int main()
{
	cout<
2)不须要把背包装满，仅仅须要收益最大
使用二维数组f[i][v]存储中间状态。当中第一维表示物品。第二维表示背包容量
初始化时，除了f[i][0] = 0（第一列）外。其它全为负无穷。
使用一维数组f[v]存储中间状态，维表示背包容量
原因：假设背包并不是必须被装满。那么不论什么容量的背包都有一个合法解“什么都不装”，这个解的价值为0。所以初始时状态的值也就所有为0了。
代码在最前面已贴，不在此上传。
一个常数优化
一维数组描写叙述状态时的伪代码：
for i=1..N //枚举物品
    for v=V..0 //枚举容量。从大到小
        f[v]=max{f[v],f[v-weight[i]] + cost[i]};
观察可知，对于第i个物品，枚举背包容量下限时，能够到weight[i]为止。
原因：
1）对于第i物品。在求f[v]时，须要使用的状态是 v ~ v -  weight[i] 这么多。这是因为v取最大容量V时，使用的状态才是v - weight[i]，当v不取最大状态时。使用的状态肯定是在v ~ v -  weight[i]之间的。能够到weight[i]为止。
2）在到weight[i]为止时，还能够不进行if推断，操心v -  weight[i]是否越界
此时，伪代码为
for i=1..N //枚举物品
    for v=V..weight[i] //枚举容量，从大到小
        f[v]=max{f[v],f[v-weight[i]] + cost[i]};
注意。对 f 数组，假设是检測第i个物品能否放入，0 ~ weight[i] - 1的这些位置是不会遍历到的，则此时他们仍表示第i - 1次的状态。即二维的f[i - 1][v]。

还能够继续优化下界为
for i=1..N //枚举物品
	bound=max{V-sum{weight[i..n]},weight[i]}//确定须要枚举容量的下界
	for v=V..bound
		f[v]=max{f[v],f[v-weight[i]] + cost[i]};
原因：
1)网上的说法,不太懂,各位大牛能够指导下下。
对于第i次循环（指外循环），对于背包容量v = V(最大)时。对于f[v]的值，事实上仅仅要知道f[v-weight[i]]就可以。以此类推。对于背包容量为 j 时，我们仅仅须要知道到f[v-sum{weight[j..n]}]就可以
2)还有人说
假设比v-sum{weight[j..n]}这个小，那么即使后面物品的全要也装不满背包。
所以对于物品i。小于v-sum{weight[j..n]}的v值，无意义。
总之是不懂。智商啊
作者说。当V非常大是。效果好。
代码
#include 
using namespace std;

const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值

int f[V + 1] = {0};

int Max(int x,int y)
{
	return x > y ? x : y;
}

/*
目标：在不超过背包容量的情况下。最多能获得多少价值

子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值

状态转移方程:f[j] = max{f[j],f[j - weight[i]] + value[i]}

初始化:f数组全设置为0
*/
int Knapsack()
{
	int sum = 0;//存储还未处理物品的总容量
	int bound = 0;
	//初始化
	memset(f,0,sizeof(f));
	for (int i = 1;i <= N;i++)
	{
		sum += weight[i];
	}
	
	//递推
	for (int i = 1;i <= N;i++) //枚举物品
	{
		//设置下界
		if (i != 1)
		{
			sum -= weight[i - 1];
		}
		bound = Max(V - sum,weight[i]);

		for (int j = V;j >= bound;j--) //枚举背包容量
		{
			if (f[j] < f[j - weight[i]] + value[i])
			{
				f[j] = f[j - weight[i]] + value[i];
			}
		}
	}
	return f[V];
}

int main()
{
	cout<
 输出方案
一般而言，背包问题是要求一个最优值，假设要求输出这个最优值的方案，能够參照一般动态规划问题输出方案的方法：记录下每一个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可依据这条策略找到上一个状态。从上一个状态接着向前推就可以。
这里我们首先给出01背包的二维状态转移方程
f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + cost[i])
对于状态f[i][v]，它来自两种策略，能够是f[i - 1][v],也能够是f[i - 1][v - weight[i]] + cost[i]
当中，对于另外一种情况，就是把物品i放入背包了。这里也是我们要找的情况
依据状态转移方程，我们能够给出两种实现方法
1) 借助存储状态的数组。直接依据状态转移方程倒着推，检測是否满足
f[i][v] == f[i - 1][v - weight[i]] + value[i]
假设满足。则把第i件物品放入了，此时我们要检測第i - 1件物品。背包容量为v - weight[i]
不满足则表示没有把第i件物品放入，直接检測第i - 1件物品，此时背包容量还是v
注意，这样的方法仅仅适用于存储状态数组不压缩的情况。压缩数组因为数据有覆盖。不能使用
代码
#include 
using namespace std;

const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值

int f[N + 1][V + 1] = {{0}};

int Max(int x,int y)
{
	return x > y ? x : y;
}

/*
目标：在不超过背包容量的情况下，最多能获得多少价值

子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值

状态转移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] + value[i]}

初始化:f数组全设置为0
*/
int Knapsack()
{
	//初始化
	memset(f,0,sizeof(f));
	//递推
	for (int i = 1;i <= N;i++) //枚举物品
	{
		for (int j = 1;j <= V;j++) //枚举背包容量
		{
			f[i][j] = f[i - 1][j];
			if (j >= weight[i])
			{
				f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i]);
			}
		}
	}
	return f[N][V];
}
/*
输出顺序:逆序输出物品编号
注意：这里借助状态数组f[i][v]
使用状态转移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] + value[i]}
*/
void PrintKnapsack()
{
	int i = N;//枚举物品
	int j = V;//枚举空间
	
	cout<<"增加背包的物品编号:"<
2) 另外开辟数组，在求解最大收益时做标记位。求解完最大收益后。依据这个新数组倒着推结果
思想：对于如今这个状态的位置。它存储的是该状态上一位置
注意：这样的方法均适用存储状态数组不压缩 和 压缩两种情况
代码：
#include 
using namespace std;

const int N = 3;//物品个数
const int V = 5;//背包最大容量
int weight[N + 1] = {0,3,2,2};//物品重量
int value[N + 1] = {0,5,10,20};//物品价值

int f[V + 1] = {0};

int G[N + 1][V + 1] = {{0}};//求背包序列

int Max(int x,int y)
{
	return x > y ?
 x : y;
}

/*
目标：在不超过背包容量的情况下。最多能获得多少价值

子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值

状态转移方程:f[j] = max{f[j],f[j - weight[i]] + value[i]}

初始化:f数组全设置为0
*/
int Knapsack()
{
	//初始化
	memset(f,0,sizeof(f));
	memset(G,0,sizeof(G));
	//递推
	for (int i = 1;i <= N;i++) //枚举物品
	{
		for (int j = V;j >= weight[i];j--) //枚举背包容量
		{
			if (f[j] < f[j - weight[i]] + value[i])
			{
				f[j] = f[j - weight[i]] + value[i];
				G[i][j] = 1;
			}
		}
	}
	return f[V];
}
/*
输出顺序:逆序输出物品编号
注意：这里另外开辟数组G[i][v],标记上一个状态的位置
G[i][v] = 1:表示物品i放入背包了。上一状态为G[i - 1][v - weight[i]]
G[i][v] = 0:表示物品i没有放入背包，上一状态为G[i - 1][v]
*/
void PrintKnapsack()
{
	int i = N;//枚举物品
	int j = V;//枚举空间
	
	cout<<"增加背包的物品编号:"<
小结：
01 背包背包问题是主要问题，它包括设计状态背包问题、最基本的思想公式。其他。其他类型的背包问题常常可以转化成01 背包问题。
我们必须小心经验可借鉴的方法的基本思想顶部，含义状态转移方程，如何优化空间复杂度。