Tag: 动态编程

如何找到arrays元素与特定值的最接近可能总和？

在Java中，我应该如何找到arrays元素与特定值K的最接近（或相等）可能的总和？ 例如，对于数组{19,23,41,5,40,36}和K = 44，最接近的可能总和是23 + 19 = 42。 几个小时以来我一直在努力奋斗; 我对动态编程几乎一无所知。 顺便说一下，数组只包含正数。

动态规划和背包应用

我正在研究动态编程，并希望解决以下问题，可以在http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf找到： 给你一块尺寸为X×Y的矩形布，其中X和Y是正整数，以及可以使用布制作的n个产品列表。 对于[1，n]中的每个产品，您知道需要一个尺寸为ai by bi的矩形布料，并且该产品的最终销售价格为ci。 假设ai，bi和ci都是正整数。 你有一台机器可以将任何矩形布块水平或垂直切成两块。 设计一种算法，找到切割X×Y布料的最佳策略，以便由最终产品制成的产品给出最大的销售价格总和。 您可以根据需要自由制作给定产品的副本，如果需要，可以不制作任何副本。 （来自Dasgupta，Papadimitriou和Vazirani的算法。） 看起来我们有一种二维背包问题，但我认为通过将权重视为矩形区域，可以用传统的背包算法解决它。 这看起来像是一种合理的方法吗？ 这是我正在学习的课程的编程作业，所以请仅包括概念性讨论和/或伪代码来说明想法。

function范式中的动态编程

我正在寻找关于项目欧拉的问题三十一 ，请问，有多少不同的方法可以使用任意数量的1p，2p，5p，10p，20p，50p，£1（100p）和£的硬币赚2英镑2（200p）。 有递归解决方案，例如Scala中的这个解决方案（Pavel Fatin） def f(ms: List[Int], n: Int): Int = ms match { case h :: t => if (h > n) 0 else if (n == h) 1 else f(ms, n – h) + f(t, n) case _ => 0 } val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200) […]

动态编程 – 改变

我在查找动态硬币更改问题的最后一段代码时遇到了麻烦。 我已经包含了以下代码。 我无法弄清楚最后的else 。 我应该在那时使用贪婪算法，还是可以根据表中已有的值计算答案？ 我努力尝试理解这个问题，我觉得我很接近。 该方法通过创建表并使用存储在表中的结果来解决较大的问题而不使用递归，从而找到进行特定更改所需的最小硬币数量。 public static int minCoins(int[] denom, int targetAmount){ int denomPosition; // Position in denom[] where the first spot // is the largest coin and includes every coin // smaller. int currentAmount; // The Amount of money that needs to be made // remainingAmount = 0 ; denomPosition–) { for(currentAmount […]