【经典问题】精析：一文搞懂 动态规划解决 0-1背包问题

背包问题核心元素：

数量为n的物品，容量为size的背包，给出每个物品的重量weight和价值val，求背包能装的物品最大总价值。

求解思路的本质：

从小体量（少物品，少容量）的问题开始，不断求出局部最优解，然后以此为基础放大问题（求得较多物品，较大容量下最优解）

重复上述过程，直到求出题目要求的最优解（数量为n的物品，容量为size的背包条件下的）

//一下子无法理解没关系哈，接着往下看，时不时回来对照着看看这总结

概念意义的解析：

核心工具，在于我们自己初始化的一个二维数组

int arr[obj_num+1][bag_size+1] = {0};//所有元素均初始化为0

// 第 i 行：第 i 种物品 （其中物品从下标为1开始放，第 0 行全部初始化为0

// 第 j 列：背包容量为 j 

// 第 i 行 第 j 列数组的值（即arr[ i ][ j ]）：相当于上文提到的 “小体量背包问题  ：数量为n=i 的物品，容量为size=j 的背包，给出每个物品的重量weight和价值val，求背包能装的物品最大总价值。”的最优解

具体实现操作

为表述简介，记X = 该行对应物品

初始化：第0行全部初始化为0（可理解为，没有物品，背包容量再大也装不出任何价值）

接着，从第一行开始，逐行从左往右地遍历，在对arr[ i ][ j ]赋值前，做如下判断：

X能否装进空背包中（weight[i-1] <= j）//说明：weight数组第 i 个物品的下标为 i-1

0.若不能，则问题转化为： 求数量为 n = i-1 的物品（不考虑X），容量为size=j 的背包的最优解 ：

if(wei[i-1] > bag_size)
{
	arr[i][j] = arr[i-1][j]; continue;
} 

1.若能放进背包，那咱们就要比较第 i 种物品 放进背包&不放进背包 两种情况下的获利

        1.0不放进背包：跟上面一样，就是求数量为 n = i-1 的物品（不考虑当前行对应物品），容量为size=j 的背包的最优解 arr[i-1][j]。

        1.1放进背包，那么总最优价值就是： 该物品价值 + 数量为 n = i-1 的物品（不考虑当前行对应物品），容量为size=j - weight[ i-1 ] 的背包的最优解 arr[i-1][ j-weight[ i-1 ]]

arr[i][j] = max(arr[i-1][j], arr[i-1][j-wei[i-1]] + val[i-1]);

重复上述过程，最终求得的二维数组最右下角的值 arr[n][size] 就是数量为n的物品，容量为size的背包的最优解

总体代码见下（C++）：

#include<bits/stdc++.h>
using namespace std;
#define obj_num 5
#define bag_size 7
int main()
{
	int wei[obj_num] = {1, 2, 4, 6, 8};//物品重量
	int val[obj_num] = {4, 2, 1, 7, 5};//物品价值
	int arr[obj_num+1][bag_size+1] = {0};//所有元素均初始化为0
	
	for(int i = 0; i<=obj_num; i++ )
	{
		for(int j = 0; j<=bag_size; j++)
		{
			if(i == 0) continue;//第0行全是0
			if(wei[i-1] > bag_size)
			{
				arr[i][j] = arr[i-1][j]; continue;
			} 
			arr[i][j] = max(arr[i-1][j], arr[i-1][j-wei[i-1]] + val[i-1]);
		}
	}
	//打印arr
	for(int i=0; i<=obj_num; i++)
	{
		for(int j=0; j<=bag_size; j++) cout<<arr[i][j]<<" ";
		cout<<endl;
	}
	//
	cout<<"所求结果为："<<arr[obj_num][bag_size];
	return 0;
}

~希望对你有帮助~