01背包问题 : 二维dp数组 + 图文

其实01背包问题，我之前跟着代码随想录的Carl学过，今天我看到另外一种定义dp数组的方式，我觉得思路也不错，所以我又来写一篇，大家再看此篇之后也可以看我的往期文章，非常感谢您的阅读：解决0-1背包问题（方案一）:二维dp数组_呵呵哒(￣▽￣)"的博客-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133207350?spm=1001.2014.3001.5501

伪代码：

C++代码： 

#include
#include 
using namespace std;
 
void test_0_wei_bag_problem() {
	vector<int> weight = { 1,3,4 };
	vector<int> value = { 15,20,30 };
	int bagWeight = 4;
	// 二维数组
	vectorint>> dp(weight.size()+1, vector<int>(bagWeight+1, 0));
 
	// weight数组的大小，就是物品个数
	for (int i = 1; i <= weight.size(); i++) { // 遍历物品
		for (int j = 1; j <= bagWeight; j++) { // 遍历背包容量
			if (weight[i - 1] > j) dp[i][j] = dp[i - 1][j];
			else dp[i][j] = max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
		}
	}
	cout << dp[weight.size()][bagWeight] << endl;
}
 
int main() {
	test_0_wei_bag_problem();
}

文章图文是参考B站这个视频：

[轻松掌握动态规划]4.01背包_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1uW4y1G7Gs/?spm_id_from=333.999.0.0&vd_source=a934d7fc6f47698a29dac90a922ba5a3