01背包问题

题目链接

01背包问题

对于01背包,我也理解的感觉也不上特别透彻

视频讲解

下面是核心代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
//#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
const int N = 1005;

int	dp[N][N] = {0};
signed main () {
	int n, m;
	scanf("%d %d", &n, &m);
	int v[N], w[N];
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &v[i], &w[i]);
	}
	//i表示这个背包可以装前i个物品,j表示这个背包的最大容量,dp[i][j]的值为这个背包所能装下的最大的价值
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {//将这个背包分解成n*m个背包,
			if (v[i] > j) {//如果当前背包的重量不能放入当前这个物品
				dp[i][j] = dp[i - 1][j];//所以这个背包转换为可以装前i-1个物品,容量为j的背包
			} else {
				//如果当前的背包可以放下当前的物品
				//dp[i-1][j],这个背包是不取第i个物品
				//dp[i-1][j-v[i]],这个背包是取出第i个物品
				//最后取这两个的最大值
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
			}
		}
	}
	cout << dp[n][m] << '\n';//通过dp数组直接得出结果

//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
//		}
//}
	return 0;
}