01背包的原理和实际应用，有哪些独特的长尾词可以深入探讨？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1148个文字，预计阅读时间需要5分钟。
01背包+01背包问题+思路分析
1.当我们第一次看到题目的时候，很容易想到运用贪心的思想，每次选择性价比最高的物品。
+ 容易举出反例：3 76 10 / 1.666...5 8 / 1.62 3 / 1.52. 接着我们很自然地想到...
01背包01背包题目
思路剖析1.当我们第一次看到题目的时候，很容易想到运用贪心的思想，每次拿性价比最大的物品。
容易举出反例：
3 7
6 10 //1.666...
5 8 // 1.6
2 3 //1.5
2.接着我们很自然的就可以想到，既然运用贪心的思想不行，那么就枚举所有选取物品的情况，也就是组合。
于是我们就可以定义状态
\(dfs(i,v,ans)\) 表示我搜索到了第 \(i\) 个物品，此时已经选的物品的总体积为 \(v\) , 所得到的价值为 \(ans\) 。
当我们将 \(N\) 个物品全都搜完后，若 \(v \le M\) ，则更新我们的答案。
在这个过程中，我们可以发现 ， 对于一个状态 \(i,v,ans\) ,它可以从 \(i-1,v,ans\) 或 \(i-1,v-v_i,（ans-w_i）+w_i\) 转移过来(分别对应了我选不选第 \(i\) 个物品的情况)，但由于他所剩的物品个数一样，已经选的体积一样，所以尽管从两个不同的状态转移过来，所得的价值不同，但是之后能够遍历到的情况都是相同的。
显然有所得价值更大的状态，得到的结果优于价值更小的状态。
本文共计1148个文字，预计阅读时间需要5分钟。
01背包+01背包问题+思路分析
1.当我们第一次看到题目的时候，很容易想到运用贪心的思想，每次选择性价比最高的物品。
+ 容易举出反例：3 76 10 / 1.666...5 8 / 1.62 3 / 1.52. 接着我们很自然地想到...
01背包01背包题目
思路剖析1.当我们第一次看到题目的时候，很容易想到运用贪心的思想，每次拿性价比最大的物品。
容易举出反例：
3 7
6 10 //1.666...
5 8 // 1.6
2 3 //1.5
2.接着我们很自然的就可以想到，既然运用贪心的思想不行，那么就枚举所有选取物品的情况，也就是组合。
于是我们就可以定义状态
\(dfs(i,v,ans)\) 表示我搜索到了第 \(i\) 个物品，此时已经选的物品的总体积为 \(v\) , 所得到的价值为 \(ans\) 。
当我们将 \(N\) 个物品全都搜完后，若 \(v \le M\) ，则更新我们的答案。
在这个过程中，我们可以发现 ， 对于一个状态 \(i,v,ans\) ,它可以从 \(i-1,v,ans\) 或 \(i-1,v-v_i,（ans-w_i）+w_i\) 转移过来(分别对应了我选不选第 \(i\) 个物品的情况)，但由于他所剩的物品个数一样，已经选的体积一样，所以尽管从两个不同的状态转移过来，所得的价值不同，但是之后能够遍历到的情况都是相同的。
显然有所得价值更大的状态，得到的结果优于价值更小的状态。