动态编程在01背包问题中的应用

南京信息工程大学实验（实习）报告实验名称动态规划方法，用于01背包问题的日期2012.12.1分数指导老师指导老师计算机和软件学校软件工程等级2012问题描述给出C的负载能力背包和物体，物体i的重量为Wi，值为Vi，1in. 需要将这些物品包装到背包中，以使背包中物品的总价值最大化. 我们在此讨论的对象是不可分割的，而这些对象不可分割的背包问题通常称为01背包问题. 基本思想是，在0/1背包问题中，项目i要么装入背包，要么不装入背包. 令xi表示将物品i装入背包的情况. 当xi = 0时，表示未加载项i. 背包，当xi = 1时，表示将物品i装入背包. 根据问题的要求，存在以下约束和目标函数: 因此，问题归结为找到满足约束公式1并最大化目标函数公式2的解矢量X =（x1，x2，使用动态解决01背包算法的基本思想动态规划动态规划算法通常用于求解具有某些最优性质的问题. 在这种类型的问题中，可能存在许多可行的解决方案. 每个解决方案都对应一个值，并且我们希望找到最佳的价值解决方案，动态规划算法与分治法相似，其基本思想是将要解决的问题分解为几个子问题，首先解决子问题，然后从这些子问题的解决方案中获得原始问题的解决方案.

不同于分治法，它适用于通过动态编程解决的问题. 分解后获得的子问题通常彼此不独立. 如果使用分治法来解决这些问题，则通过分解获得的子问题的数量太大，并且某些子问题被重复计算多次. 如果我们可以保存已解决的子问题的答案并在需要时找到所需的答案，则可以避免大量重复计算并节省时间. 我们可以使用表格记录所有已解决子问题的答案. 不管将来是否使用该子问题，只要已计算出该子问题，结果都将填写在表中. 这是动态编程方法的基本思想. 具体的动态编程算法是多种多样的，但是它们具有相同的表格填充形式. 可以将算法设计0/1背包问题视为决策序列（x1，x2，xn）. 对于任何变量xi的决定是xi = 1还是xi =0. 在确定xi-1之后，已经确定了（x1，xi-1）. 在确定xi时，问题出在以下两种状态之一: （1）背包容量不足以装载物品i，则xi = 0，背包没有增加价值； （2）背包的容量可以加载项i，则xi = 1，背包的值增加vi. 在这两种情况下，背包的最大价值应为决定xi后的背包价值. 令V（i，j）代表前i个（1in）物品中可装入容量为j（1jC）的背包中物品的最大值，则可获得以下动态编程功能: 显示: put以前的i物品装一个容量为0的背包并将0物品装入容量为j的背包，其值为0.

的第一个公式

表明，如果第i个物品的重量大于背包的容量，则通过加载第i个物品获得的最大值与通​​过加载第i-1个物品获得的最大值相同，也就是说动态规划法 01背包，我无法将物品装载到背包中. 这意味着如果第i个物品的重量小于背包的容量，则将出现以下两种情况: （1）如果将物品装入背包，则该物品在背包中的价值为等于装在容量为j-Wi的背包中的前i-1个物品的值加上第i个物品的值Vi； （2）如果第i个物品未装入背包，则背包中物品的值等于将第i-1个物品装入容量为j的背包所获得的值. 显然，将两者中的较大值作为将物品装入容量为j的背包的最佳解决方案. 根据以下方法将阶段划分为: 在第一阶段，仅加载第一项以确定在各种情况下背包可获取的最大值；在第二阶段中，只有前两个项目被加载并以各种方式确定. 在这种情况下，背包的最大值可以类推到第n阶段. 最后，V（n，C）是将n个物品装入容量为C的背包中时获得的最大值. 为了确定装入背包的特定物品，请从V（n，C）的值向前推. 如果V（n，C）> V（n-1，C），则意味着将第一件物品装入背包，将前n -1件物品装入容量为C-Wn的背包中. 否则，第n-1件物品不会装进背包，而前n-1件物品会装进容量为C的背包.

依次类推，直到您确定第一件物品是否在背包中. 因此，获得以下功能: 该公式指示对象i没有被加载到背包中；该公式表明，如果V（i，j）大于V（i-1，j），则将对象i装入背包；如果相等，则表示i背包中没有携带该物品. 根据这种关系，我可以类推得出i，直到将第一个对象加载到背包中，然后可以确定加载到背包中的特定对象. 存储结构该算法需要分别存储每个对象的重量和值动态规划法 01背包，并针对具有不同负载能力的背包分别计算对象，因此请考虑使用数组来实现. 对于对象i，使用W [i]表示权重，使用V [i]表示值，使用向量x [i]表示对象i是否已放置的解矢量，以及上述V（ i，j）使用二维数组的对应V [i] [j]表示对象数为n，背包的承载能力为C，数组V [n + 1] [C + 1]存储迭代结果. 算法实现int KnapSack（int //计算第i行，并执行第i次迭代V [i] [j] = V [i-1] [j]；否则V [i] [j] = max （V [i -1] [j]，V [i-1] [jw [i]] + v [i]）； j = jw [i]；}时空分析时间复杂度: 第一个的时间性能for循环为O（n），第二个for循环的时间性能为O（C），第三个循环为两层嵌套的for循环，其时间性能为O（nC），第四个时间性能for循环为O（n），因此算法的时间复杂度为O（nC）.

空间复杂度: 在该算法中，矩阵的大小为（n + 1）（C + 1），对象的权重，值和解向量的大小都等于对象的个数n ，因此该算法的空间复杂度为O（nC）. 算法优化在上述算法中，不再可以优化时间复杂度，但是可以继续优化空间复杂度. 在上述算法中，V [i] [j]的存储使用大小为（n +1）（C +1）的二维数组，但仔细观察发现，V [i] [j]为仅与V [i -1] [j]相关的与V [i-1] [j Wi]和V [k] [j]相关（k = 1，2，...，i-2，i + 1，... n，j = 1，2，...，C）是无关紧要的，因此考虑仅使用一维数组V'来存储，V'[j]等于V [i] [j ]. 考虑到V [i] [j]是由V [i-1] [j]和V [i-1] [j Wi]共同计算的，因此该算法的j循环是从后到前计算的，计算算法V'[]的设计如下: 显然，对于对象i，_optp [j]的计算不会影响_optp [0，1，...，weight [i] -1]，因此上述算法可以继续优化如下: 该算法在现实生活中的其他应用. 动态规划是算法中非常重要的方法，它是优化决策过程的数学方法. 自成立以来，动态规划已广泛应用于经济管理，生产调度，工程技术和最优控制.

例如，最短路径，库存管理，资源分配，设备更新，分类，装载等，使用动态编程方法比其他方法更方便. 示例: 动态规划算法在最佳路线规划中的应用. 隐藏，安全和高效的渡轮是战时船只成功完成各种运输任务的要求. 因此，在设计路线时，考虑到路线的安全性，还必须注意某条轮渡所需路线的隐蔽性能，以最终获得整个路线的最优规划. 传统的海员通常在纸质海图上手动设计航线. 这种人工操作方法不仅工作强度高，而且设计结果的质量完全取决于海员的经验，熟练程度和工作态度. 将给航程带来许多潜在的不安全因素. 所谓最优路径选择，就是根据制定导航计划的中心任务，选择最短，最经济，最安全的路径. 最佳路线取决于路点的选择，并且路点的不同布置形成了大量的替代路线. 基于此，可以将动态规划的思想应用于研究路线规划的自动实现，并可以设计出最优路线规划的数学模型. 该算法的优缺点总结了动态规划的优点: 从以上实例分析可以看出，使用动态规划解决多阶段决策问题的效率很高，思路清晰，思路清晰. 简单，并且易于实现. 动态规划方法的应用非常广泛，具有很强的实用性. 动态编程的缺点: 对于01背包问题，使用动态编程的解决方案很容易理解，但是这种方法有一些缺点. 从上述算法可以看出: 当物体的重量较大时，所需的物理空间较大；如果对象的权重不是整数，则不能使用数组来存储结构.

附加: 源程序#include #include #include int min（int inttemp; elsetemp returntemp; Intmax（int inttemp; elsetemp returntemp; voidknapsack（int intjmax（intjj jj ++）m）[n] [jj] m [i + 1] [j]；对于（int jj jj ++）m [i] [jj] max（m [i + 1] [jj]，m [i + 1] [jj-w [i]] + v [i]）； endl； cout

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-171913-1.html