问题：玩家背包里存在加速道具，加速的时长分别如下：
求解：当希望加速91个小时的时候，最优的道具使用组合（要求：1、浪费的时长最小；2、道具数量最少）
注：暂不考虑道具不够的情况。
原理：利用动态规划的思想来实现，转化为子问题去实现。
设道具列表为p = {5,7,21,30,......}
假设r[91]为需要求的最优解，那么
r[91]可以转化为：
说明：在已知前一个最优解r[90]的情况下，让这个最优解r[90]依次加上加速道具的时长，如果比期望的总时间91多，则这个是一个有效解，找到r[90]的所有有效解，最小的有效解就是一个最优解。（小优化：当 已经是最小的最优了，可以提前break掉，如果希望大道具优先，那我们对于q的遍历就可以从大到小来）
依次类推，我们找到r[89],r[88]....r[1]的最优解，在这些最优解中取最小的就是r[91]的最优解了。
算法及优化如下：
运行结果：
进一步优化：
问题：玩家背包里存在加速道具，加速的时长分别如下： 求解：当希望加速91个小时的时候，最优的道具使用组合（要求：1...
继续上一个动态最优解。 现实中背包里的道具数量有限，此时我们需要增加道具数量的限定，只需要在子问题的有效解上做限制...
动态规划 最优子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。即一个问题的最优解包含其...
动态规划 步骤 描述最优解的结构 递归定义最优解的值 按自底向上的方式计算最优解的值 //此3步构成动态规划解...
LeetCode基础算法-动态规划 LeetCode 动态规划 动态规划的核心步骤： 查看大问题的最优解能否使用小...
引言：动态规划介绍 什么时候可以使用动态规划：求最优解问题的时候动态规划的两个主要问题：最优子结构和重叠子问题，一...
贪婪和动态规划 贪婪算法和动态规划算法都是在多阶段决策最优解模型下求最优解。使用这两种算法可以算出来的，当然就可以...
与贪心算法求局部最优解相比，动态规划求的是全局最优解（但不是每个问题都有最优解，比如NP完全问题就没有最优解） 例...
【回溯算法】在 最优解、排列组合、解空间搜素 中存在典型应用 【动态规划】和【贪心算法】都要求 无后效性，即 子问...
function __Class:myTest(num) local cost = {5,21,10,8} ...
本文标题：动态最优解--道具的组合使用
本文链接：https://www.haomeiwen.com/subject/rulgqktx.html
网友评论