Gausst松鼠会

这个屌丝很懒，什么也没留下！

热门标签

九种 0-1 背包问题详解_0-1背包问题

作者：Gausst松鼠会 | 2024-04-15 20:31:46

踩

0-1背包问题

前言

0-1 背包是一个经典的问题，之前也整理过一篇关于　0-1 背包的博客，当时只是整理了　0-1 背包问题的 4 种解决方法。最近在复习算法，发现有很多　0-1 背包问题的衍生问题。0-1 背包问题的限制条件既可以是重量，也可以是容量，或者两者同时限制。现在将这 9 种 0-1 背包问题与解决方法整理出来。这 9 种 0-1 背包问题实质上都是在问题 1 的基础上增添了新的条件，所以想弄清楚后面的问题，必须认真的学习并理解问题 1。

0-1 背包问题的 4 种解决方法&&算法策略：0-1 背包问题的 4 种解决方法&&算法策略_Tyler_Zx的博客-CSDN博客_背包问题的经典解决方法是

动态规划概念

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。

该算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问题所具有的这两个重要性质是该问题可用动态规划算法求解的基本要素。这对于在设计求解具体问题的算法时，是否选择动态规划算法具有指导意义。

最优子结构

设计动态规划算法的第一步通常是要刻画最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。

重叠子问题

可用动态规划算法求解的问题应具备的另一基本要素是子问题的重叠性质。在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常，不同的子问题个数随问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。

备忘录方法

备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下，而动态规划算法则是自底向上递归的。因此备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

动态规划算法适用于解最优化问题。通常可按以下4个步骤设计：


(1)找出最优解的性质，并刻画其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息，构造最优解。

问题1：0-1背包问题

动态规划解 0-1 背包问题的基本思想：

对于每个物品我们可以有两个选择，放入背包，或者不放入，有 n 个物品，故而我们需要做出 n 个选择，于是我们设 F[i][v] 表示做出第 i 次选择后，所选物品放入一个容量为 v 的背包获得的最大价值。现在我们来找出递推公式，对于第 i 件物品，有两种选择，放或者不放。

① 如果放入第 i 件物品，则 F[i][v] = F[ i-1 ][ v-w[i] ] + p[i] ，表示，前 i-1 次选择后所选物品放入容量为 v-w[i] 的背包所获得最大价值为 F[ i-1 ][ v-w[i] ] ，加上当前所选的第 i 个物品的价值 p[i] 即为 F[i][v] 。

② 如果不放入第 i 件物品，则有 F[i][v] = F[ i-1 ][ v ]，表示当不选第i件物品时，F[i][v] 就转化为前 i-1 次选择后所选物品占容量为 v 时的最大价值 F[i-1][v]。则：F[i][v] = max{ F[ i-1 ][v], F[ i-1 ][ v-w[i] ] + p[i] }。


#include <iostream>
using namespace std;
#define N 1005
int Asd[N][N];                               //Asd[i][j]表示前 i 个物品，背包容量是 j 的情况下的最大价值。
int Value[N];
int Vol[N];
 
int main()
{
	int n, Volume;
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
		cin >> Vol[i] >> Value[i];
 
	for(int i = 1; i <= n; i++) {              //n个物品
		for(int j = 1; j <= Volume; j++) {     //Volume是容量	
			Asd[i][j] = Asd[i-1][j]; 
			if(j >= Vol[i])
				Asd[i][j] = max(Asd[i][j], Asd[ i-1 ][ j-Vol[i] ] + Value[i]);
		} 
	}
	cout << Asd[n][Volume] <<endl;
	return 0;
}

优化：使用一维数组

其实状态转移每次只与上一层有关，所以可以用一维数组记录状态，转移方程：Asd[j] = max(Asd[j], Asd[ j-Vol[i] ] + Value[i]); ，此时第二层循环需要做出响应的变化，即第二层循环需要从大到小循环。


#include<iostream>
using namespace std;
#define N 1005
int Asd[N]; 
int Value[N];
int Vol[N];
 
int main()
{
	int n, Volume;
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
		cin >> Vol[i] >> Value[i];
		
	for(int i = 1; i <= n; i++){
		for(int j = Volume; j >= Vol[i]; j--)
			Asd[j] = max(Asd[j], Asd[ j-Vol[i] ] + Value[i]);
	}
	cout<< Asd[Volume] <<endl;
	return 0;
}

问题2：完全背包问题

完全背包问题与 0-1 背包问题的区别在于完全背包问题中的物品可选无限次。

也是两种情况，选或不选，只不过每次可以选无限次，所以在 0-1 背包的基础上把

Asd[i][j] = max(Asd[i][j], Asd[ i-1 ][ j-Vol[i] ] + Value[i]); 改为： Asd[i][j] = max(Asd[i][j], Asd[ i ][ j-Vol[i] ] + Value[i]);


#include <iostream>
using namespace std;
#define N 1005
int Asd[N][N];       //Asd[i][j]表示前 i 个物品，背包容量是 j 的情况下的最大价值。
int Value[N];
int Vol[N];
 
int main()
{
	int n, Volume;
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
		cin >> Vol[i] >> Value[i];
 
	for(int i = 1; i <= n; i++) {              //n个物品
		for(int j = 1; j <= Volume; j++) {     //Volume是容量
			Asd[i][j] = Asd[i-1][j]; 
			if(j >= Vol[i]) 
				Asd[i][j] = max(Asd[i][j], Asd[ i ][ j-Vol[i] ] + Value[i]);
		} 
	}
	cout << Asd[n][Volume] <<endl;
	return 0;
}
 
 
优化：一维数组
#include<iostream>
using namespace std;
#define N 1005
int Asd[N]; 
int Value[N];
int Vol[N];
 
int main()
{
	int n, Volume;
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
		cin >> Vol[i] >> Value[i];
 
	for(int i = 1; i <= n; i++){
		for(int j = Vol[i]; j <= Volume; j++)
			Asd[j] = max(Asd[j], Asd[ j-Vol[i] ] + Value[i]);
	}
	cout<< Asd[Volume] <<endl;
	return 0;
}

问题3：多重背包问题

多重背包问题与 0-1 背包问题的区别在于多重背包问题中的物品数不唯一。

方法１：O(n^3) 解法

加一层循环，把 s 个物品的每种选择情况都尝试一遍，如果不拿，则还是 0-1 背包问题中不选择的情况。


#include <iostream>
using namespace std;
#define N 1005
int Asd[N][N];       //Asd[i][j]表示前 i 个物品，背包容量是 j 的情况下的最大价值。
int Value[N], Vol[N], S[N];
 
int main()
{
	int n, Volume;
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
		cin >> Vol[i] >> Value[i] >> S[i];
 
	for(int i = 1; i <= n; i++) {              //n个物品
		for(int j = 1; j <= Volume; j++) {     //Volume是容量
			for(int k = 1; k <= S[i] && j >= k*Vol[i]; k++){
				Asd[i][j] = Asd[i-1][j]; 
				if(j >= Vol[i]) 
					Asd[i][j] = max(Asd[i][j], Asd[ i-1 ][ j- k*Vol[i] ] + k*Value[i]);
			}
		} 
	}
 
	cout << Asd[n][Volume] <<endl;
	return 0;
}
 
 
优化：一维数组
#include <iostream>
using namespace std;
#define N 1005
int Asd[N]; 
int Value[N];
int Vol[N];
int S[N];
 
int main()
{
	int n, Volume;
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
		cin >> Vol[i] >> Value[i] >> S[i];
 
	for(int i = 1; i <= n; i++){
		for(int j = Volume; j >= Vol[i]; j--){
			for(int k = 1; k <= S[i] && j >= k*Vol[i]; k++)
				Asd[j] = max(Asd[j], Asd[ j - k*Vol[i] ] + k*Value[i]);
		} 
	}
	cout<< Asd[Volume] <<endl;
	return 0;
}

方法2：二进制优化

除了上面的方法外，我们可以换一种思路。这个题目给的物品数量不是唯一的，所以我们可以把一个物品的 S 份全放到数组中。即：第 i 个物品有 S 个，那么就可以将每个物品的容量和价值复制 S 份。例如：一个物品的容量是 2，价值是 3，有 5 个，那么就可以将 [Volume:2 Value:3] 这一条信息插入 5 次。这样就把多重背包问题转换成了最初的 0-1 背包问题，直接套用 0-1 背包问题即可解决该问题。

但是这样做会增加问题的规模，时间复杂度仍然很高。此时需要用到二进制的思想。例如：数字 7 写成二进制形式是：111，意思是 7 = 1 + 2 + 4。对于一个有 7 份的物品而言，可以不拿( 0-1背包问题，不取就行了 )，可以拿以下这几种情况：


拿1个，即取１      
拿2个，即取2    
拿3个，即为：3 = 1+2  
拿4个，即为：4   
拿5个，即为：5 = 1+4   
拿6个，即为：6 = 2+4
拿7个，即为：7 = 1+2+4

按照原来的思路是将这个物品拆成一个一个的，需要将信息插入 7 次。而使用二进制的思想，只需要插入 3 条信息即可，这样做的好处是减少了问题的规模。


第一条：[Volume:2  Value:3]
第二条：[Volume:2*2  Value:3*2]
第三条：[Volume:2*4  Value:3*4]

比较特殊的情况，例如物品的份数是 10。如果按照二进制表示需要 4 位，但是 4 位二进制能表示 0-15，但是该物品并没有那么多。所以此时依然会使用 7 的表示方法，只是加上一条信息：[ Volume:2*3 Value:3*3 ]就可以表示 10 个物品，且不会超过物品的数量。从 1 到 10 的取法这里就不再赘述了。


#include <iostream>
#include <vector>
using namespace std;
#define N 1005
int Asd[N]; 
int n, Volume;
struct Good
{
	int volume;
	int value;
};
 
int main()
{
	vector<Good> goods;
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
	{
		int volume, value, s;
		cin >> volume >> value >> s;
		for(int k = 1; k <= s; k *= 2){
			s -= k;
			goods.push_back({volume*k, value*k});
		}
		if(s > 0) goods.push_back({volume*s, value*s});
	}
	
	for(auto good: goods){
		for(int j = Volume; j >= good.volume; j--)
				Asd[j] = max(Asd[j], Asd[ j - good.volume ] + good.value);
	}
 
	cout<< Asd[Volume] <<endl;
	return 0;
}

问题4：混合背包问题

混合背包问题是前几种背包问题的组合。对于混合背包，需要将该问题拆成多重背包和完全背包问题，然后再求解。


#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
 
struct Thing
{
		int kind;
		int volume, value;
};
 
int n, Volume;
vector<Thing> things;
int Asd[N];
 
int main()
{
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
	{
		int volume, value, s;
		cin >> volume >> value >> s;
		if(s < 0) things.push_back({1, volume, value});
		else if(s == 0) things.push_back({0, volume, value});
		else
		{
			for(int k = 1; k <= s; k <<= 1)
			{
				s -= k;
				things.push_back({1, volume*k, value*k});
			}
			if(s) things.push_back({1, volume*s, value*s});
		}
	}
	
	for(auto &thing: things)
	{
		if(thing.kind == 1)
		{
			for(int i = Volume; i >= thing.volume; i--)
				Asd[i] = max(Asd[i], Asd[ i - thing.volume ] + thing.value); 
		}
		else
		{   //无限物品
			for(int i = thing.volume; i <= Volume; i++)
				Asd[i] = max(Asd[i], Asd[ i - thing.volume ] + thing.value);
		}
	}
	cout<< Asd[Volume] <<endl;
	return 0;
}

问题5：二维背包问题

二维背包问题是加了一个重量的限制，该问题可以用递归的方法完成，递归方法的优点是易于理解，缺点是不适合应用于数据量较大的情况下，当数据量过大时会 Time Limit Exceeded。

方法1：递归


#include <iostream>
#include <cstdio>
using namespace std;
#define N 100
 
struct goods
{
    int volume; //物品体积
    int weight;  //物品重量
    int value;  //物品价值
};
 
int n, bestValue, cvalue, cweight, cvolume, C, D;
//物品数量，价值最大，当前价值，当前重量，当前容量，背包容量C，背包重量D
goods goods[N];
 
int Force(int i){
    if(i > n-1)  //结束递归的条件，不超过重量和容量的限制，且价值最大
    {
        if(bestValue < cvalue && cweight <= D && cvolume <= C)
            bestValue = cvalue;
        return bestValue;
    }
    //拿
    cweight += goods[i].weight;
    cvalue += goods[i].value;
	cvolume += goods[i].volume;
	
	if(cweight <= D && cvolume <= C)
		Force(i+1);
 
    //不拿
    cweight -= goods[i].weight;
    cvalue -= goods[i].value;
    cvolume -= goods[i].volume;
 
    Force(i+1);
    return bestValue;
}
 
int main()
{
    cin >> n >> C >> D;
    for(int i = 0; i < n; i++)
        cin >> goods[i].volume >> goods[i].weight >> goods[i].value;
    
    int sum1 = Force(0);
	cout << sum1 <<endl;
    return 0;
}

方法2：动态规划


#include <iostream>
using namespace std;
#define N 1005
int Asd[N][N]; 
int Value[N];
int Vol[N];
int W[N];
 
int main()
{
	int n, Volume, Weight;
	cin >> n >> Volume >> Weight;
	for(int i = 1; i <= n; i++)
		cin >> Vol[i] >> W[i] >> Value[i];
 
	for(int i = 1; i <= n; i++){
		for(int j = Volume; j >= Vol[i]; j--){
			for(int k = Weight; k >= W[i]; k--)
				Asd[j][k] = max(Asd[j][k], Asd[ j - Vol[i] ][ k - W[i] ] + Value[i]);
		}
	}
	cout<< Asd[Volume][Weight] <<endl;
	return 0;
}

问题6：分组背包问题

分组背包问题是一组物品中只能选择一个，若一组有n个物品，则有 n+1 种决策(不选 + n种选择可能)。结局方法是加一层决策层，循环组内物品，判断是否选择该组内的物品，以及选择哪一个。其实上面的问题都可以理解成：循环物品，循环容量，循环决策这三步。


#include <iostream>
using namespace std;
#define N 1005
int Asd[N]; 
int Value[N];
int Vol[N];
 
int main()
{
	int n, Volume, Group;                      //Group是组内物品的数量
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)                //第一层循环，循环物品
	{
		cin >> Group;
		for(int j = 0; j < Group; j++)
			cin >> Vol[j] >> Value[j];
 
		for(int j = Volume; j >= 0; j--)       //第二层循环，循环体积
			for(int k = 0; k < Group; k++)     //加一层循环，在做决策的时候选择组内的物品
				if(j >= Vol[k])
					Asd[j] = max(Asd[j], Asd[ j - Vol[k] ] + Value[k]);
	}
	
	cout<< Asd[Volume] <<endl;
	return 0;
}

问题7：有依赖的背包问题 (困难)

问题8：背包问题求方案数

问题9：背包问题求具体方案

还是 0-1 背包问题，只不过是需要求出价值最大时，选择的物品的方案。此时需要使用数组来记录选择的物品的编号。


#include <iostream>
#include <cstdio>
#define N 100
#define MAX(a,b) a < b ? b : a
using namespace std;
 
struct goods{
    int volume;//物品重量
    int value;//物品价值
};
 
int n, cv, cw, Volume; 
//物品数量，价值最大，当前价值，当前重量，背包容量
int X[N],cx[N];          
//最终存储状态，当前存储状态
goods goods[N];
 
int Bag(int n, struct goods a[], int Volume, int x[]){
    int V[N][N+1];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= Volume; j++)
        if(j < a[i].volume)
            V[i][j] = V[i-1][j];
        else
            V[i][j] = max(V[i-1][j],V[i-1][ j-a[i].volume ] + a[i].value);
 
    for(int i = n, j = Volume; i > 0; i--){
        if(V[i][j] > V[i-1][j]){
            x[i-1] = 1;
            j = j - a[i].volume;
        }
        else
            x[i-1] = 0;
    }
    return V[n][Volume];
}
 
int main()
{
    cin >> n >> Volume;
    for(int i = 1; i <= n; i++){
        cin >> goods[i].volume >> goods[i].value;
    }
    int sum = Bag(n, goods, Volume, X);
    cout << "动态规划法求解 0/1 背包问题:\nX=[ ";
    for(int i = 0; i < n; i++)
        cout << X[i] <<" ";                    //输出所求X[n]矩阵
    printf("]  装入总价值[%d]\n", sum);
    return 0;
}

题目来源于AcWing题库：AcWing

学习视频：背包前6讲、背包后3讲

YXC NB!!!

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/429940