劳务派遣技术支持 东莞网站建设,网站建设有什么要求,网站推广哪家好,珠海科技网站建设转自#xff1a;刘毅https://www.61mon.com/index.php/archives/188/问题展开有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 Ci#xff0c;其价值是 Wi。求解#xff0c;在不超过背包容量情况下#xff0c;将哪些物品装入背包可使价值总和最大。基本思路这是最基… 转自刘毅https://www.61mon.com/index.php/archives/188/问题展开有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 Ci其价值是 Wi。求解在不超过背包容量情况下将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题特点是每种物品仅有一件。状态 F[i,v] 表示前 i 件物品中选择若干件放在容量为 v 的背包中可以取得的最大价值。转移方程对于第 i 件物品有放与不放两种选择。若选择不放F[i,v]F[i−1,v]若选择放v−Ci 确保有足够的空间随之 F[i,v]F[i−1,v−Ci]Wi。代码展开/** * * author 刘毅Limer * date 2017-03-17 * mode C */#include iostream#include algorithmusing namespace std;int main(){ const int N 6; // 物品个数 const int V 10; // 背包体积 // 第 i 个物品的体积下标从 1 开始 int C[N 1] { -1,5,6,5,1,19,7 }; // 第 i 个物品的价值 int W[N 1] { -1,2,3,1,4,6,5 }; // 状态 int F[N 1][V 1] { 0 }; // 对于第 i 个物品 for (int i 1; i N; i) for (int v 0; v V; v) { F[i][v] F[i - 1][v]; //第 i 个不放 // 如果比它大再放第 i 个 if (v - C[i] 0 F[i][v] F[i - 1][v - C[i]] W[i]) F[i][v] F[i - 1][v - C[i]] W[i]; } cout F[N][V] endl; return 0;}以上方法的时间和空间复杂度均为 O(VN)其中时间复杂度应该已经不能再优化了但空间复杂度却可以优化到 O(V)。先考虑上面讲的基本思路如何实现肯定是有一个主循环i ← 1 to N每次算出来二维数组 F[i,v] 的所有值。那么如果只用一个数组 F[v] 能不能保证第 i 次循环结束后 F[v] 中表示的就是我们定义的状态 F[i,v] 呢F[i,v] 是由 F[i−1,v] 和 F[i−1,v−Ci] 两个子问题递推而来能否保证在推 F[i,v] 时也即在第 i 次主循环中推 F[v] 时能够取用 F[i−1,v] 和 F[i−1,v−Ci] 的值呢事实上这要求在每次主循环中我们以v ← V to C[i]的递减顺序计算 F[v]这样才能保证计算 F[v] 时 F[v−Ci] 保存的是状态 F[i−1,v−Ci] 的值。优化后的代码如下/** * * author 刘毅Limer * date 2017-03-17 * mode C */#include iostream#include algorithmusing namespace std;int main(){ const int N 6; // 物品个数 const int V 10; // 背包体积 // 第 i 个物品的体积下标从 1 开始 int C[N 1] { -1,5,6,5,1,19,7 }; // 第 i 个物品的价值 int W[N 1] { -1,2,3,1,4,6,5 }; int F[V 1] { 0 }; // 状态 for (int i 1; i N; i) // 对于第 i 个物品 for (int v V; v C[i]; v--) F[v] max(F[v], F[v - C[i]] W[i]); cout 最大价值是 F[V] endl; return 0;}初始化的细节问题我们看到的求最优解的背包问题题目中事实上有两种不太相同的问法。有的题目要求 “恰好装满背包” 时的最优解有的题目则并没有要求必须把背包装满。这两种问法的实现方法只是在初始化的时候有所不同。如果是第一种问法要求恰好装满背包那么在初始化时除了 F[0] 为 0其它 F[1]...F[V] 均设为−∞这样就可以保证最终得到的 F[V] 是一种恰好装满背包的最优解。如果并没有要求必须把背包装满而是只希望价格尽量大初始化时应该将 F[0]...F[V] 全部设为 0。这是为什么呢可以这样理解初始化的 F 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被 “恰好装满”其它容量的背包均没有合法的解属于未定义的状态应该被赋值为 -∞了。如果背包并非必须被装满那么任何容量的背包都有一个合法解 “什么都不装”这个解的价值为 0所以初始时状态的值也就全部为 0 了。参考文献背包九讲。
