题目
简单背包问题是一个经典的组合优化问题，在计算机科学和算法领域被广泛研究和应用。
问题描述如下：给定一组物品，每个物品有对应的重量和价值，以及一个固定的背包容量。目标是选择一些物品放入背包中，使得放入背包中的物品总重量不超过背包容量，同时使得物品总价值最大。
题解
简单背包是一个动态规划问题，那么我们来写状态转移公式~
动态规划的递推公式为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
1）dp数组的意思？dp[i][j]，前i件物品放入最多重量为j的最大价值
2）dp[i-1][j]表示第i-1个物品放入背包时的最大价值，即此时不放入第i件物品的最大价值。
3）dp[i-1][j-w[i]] + v[i]表示第i个物品放入背包时的最大价值，w[i]和v[i]分别表示第i个物品的重量和价值。j减去w[i]，为第i件物品腾出位置，之后再加上v[i]，即第i件放入的价值。
通过填充dp数组，最终dp[N][C]即为问题的最优解，表示在给定背包容量下放入N个物品的最大价值。文章来源：https://www.toymoban.com/news/detail-534589.html
另外附上优化后使用一维数组的关键代码：文章来源地址https://www.toymoban.com/news/detail-534589.html
for(int i=0;i<n;i++)//n次
for(int j=C;j>=w[i];j--)//倒着走，及时更新
dp[j]=max(dp[j],dp[j-w[i]]+v[i])
到了这里，关于【数据结构】简单的01背包 | 主要思想分析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
