蓝桥杯算法提高VIP-01背包(C++)

解题思路  现有N件物品和一个最多能承重M的背包，第i件物品的重量是wi，价值是vi。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求最大价值(每种物品只有一件)。因为每件物品只有选与不选两种状态，因此该问题又称01背包问题;
dp[i][j]的含义是在背包最大容积是j的前提下，从前i个物品中选能够得到的最大价值, 不难发现dp[N][M]就是本题答案;
如何计算dp[i][j]呢？我们可以将它划分为以下两部分:
 选第i个物品：由于第i个物品一定会被选择，那么相当于从前i-1个物品中选且总重量不超过j-w[i](总重量-第i件物品重量),对应dp[i-1][j-w[i]]+v[i](最大价值)。
不选第i个物品：意味着从前i-1个物品中选且总重量不超过j，对应dp[i-1][j]。
结合以上两点得到递推公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
由于下标不能是负数，所以上述递推公式要求j>=w[i].当j<w[i]时意味着第i个物品无法装入背包，此时dp[i][j]=dp[i-1][j].综上得出：
dp[i][j]=dp[i-1][j],j<w[i]; max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]),j>=w[i]
dp数组初始化：当背包承重为0时，显然装不下任何物品，所以dp[i][0]=0(1<=i<=N).若一个物品也不选(即从前0个物品中选)，此时最大价值也是0，所以dp[0][j]=0(0<=j<=M).由此可见，dp数组应当全0初始化，即声明为全局变量.
参考文献：动态规划专题——背包问题_动态规划背包问题https://blog.csdn.net/raelum/article/details/128996521 作者：Iareges

#include<iostream>
using namespace std;

const int N = 1008;
int w[N], v[N]; // w[i]表示第i个物品的价值，v[i]表示第i个物品的体积;
int dp[N][N]; // 创建dp数组;

int main()
{
	int n, m; // 物品数量，背包容积;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];

	for (int i = 1; i <= n; i++) // 物品总数
	{
		for (int j = 1; j <= m; j++) // 背包最大容积
		{
			if (j < v[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
		}
	}

	cout << dp[n][m] << "\n";
	return 0;
}