用动态规划算法的变形方法 |
您所在的位置：网站首页 › 背包jansport4QUT7G7和47LW7G7区别 › 用动态规划算法的变形方法 |
|
使用备忘录方法解决0-1背包问题：
1.跟直接递归很相似，该算法能将递归遇到的子问题的解保存在一个表中，以便下一个递归遇到同样的子问题时快速求解。
2.为了区分一个子问题是否已经求解，可以通过查表的方式来判断，若子问题对应的表中元素的值为一个初始特殊值，说明该子问题还未求解；否则，表明该子问题曾经已求解过，直接获取子问题的解，不需要递归求解该值。 3.备忘录算法与动态规划算法的区别有： （1）备忘录方法的递归方式是自顶向下，而动态规划算法则是自底向上递归的。 （2）备忘录方法的控制结构与直接递归方法的控制结构相同，而动态规划算法的控制结构与循环迭代的控制结构相同。 （3）备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免相同子问题的重复求解；而动态规划算法则是建立一个表格，从最小的子问题开始向上求解较大的子问题，把每一个子问题的解全部填入表格中，直到表格中出现原问题的解为止。它们两者的共同特点是对子问题的求解都只解了一次，并记录了答案。 （4）当一个问题的所有子问题都至少要解一次时，用动态规划比用备忘录方法要好，此时，动态规划算法没有任何多余的计算。当子问题空间中的部分问题可不必求解时，用备忘录方法较有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题。
以下是源代码： #include "stdafx.h" #include #include using namespace std; const int N = 4; //物品数量 const int C = 7; //背包容量 int w[N] = {2,3,5,2}; int v[N] = {6,4,8,4}; int m[N][C+1]; //记录子问题的解的表格 int x[N]; void initial() { for (int i = 0; i < N; i++) { for (int j = 0; j = w[i]) { m[i][capacity] = v[i]; return v[i]; } else { m[i][capacity] = 0; return 0; } else { if(capacity >= w[i]) { int selected = KnapsackMemoMethod(i+1,capacity-w[i])+v[i]; int unselected = KnapsackMemoMethod(i+1,capacity); result = selected > unselected ? selected : unselected; m[i][capacity] = result; return result; } else //capacity < w[i] { result = KnapsackMemoMethod(i+1,capacity); m[i][capacity] = result; return result; } } } void Trace(int i, int capacity) { if(i == N-1) { if(m[i][capacity] == v[i]) x[i] = 1; else { x[i] = 0; } return; } else { if (m[i][capacity] == m[i+1][capacity]) { x[i] = 0; Trace(i+1, capacity); } else { x[i] = 1; Trace(i+1, capacity - w[i]); } } } int main() { initial(); cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |