标签: dynamic-programming

考虑2个序列X [1..m]和Y [1..n].记忆算法将在时间O(m*n)内计算LCS.有没有更好的算法来找出LCS时间？我想对角完成的memoization可以给我们O(min(m,n))时间复杂度.

从来没有必要处理DP.
我们有N块石头,重量为W_1,...,W_N.需要将所有宝石分成两部分,它们之间的差异很小.

由于我们有n = 6,而权重= 1,4,5,6,7,9,因此差异为0.

#include <iostream>

using namespace std;

int main()
{
    int     n; // numbers of stones
    int*    a; // array of weights
    int diff=0;
    cin >> n;
    a = new int[n];
    for(int i=0;i<n;i++)
        cin >> a[i];

    // And I don't know what's next, mee too

    delete[] a;
    system("PAUSE");
    return 0;
}

我有一个问题,表面看起来像0-1背包.我有一组可以选择(或不选择)的可能"候选人",每个候选人都有"权重"(成本)和潜在的"价值".如果这是整个问题,我会使用DP方法并完成它.但是这里是曲线球:对最终解决方案中可能的候选者存在"分区约束".

我的意思是候选空间被分成不连续的等价类.对于我的特殊问题,大约有300个候选人和12个可能的等同类.有"商务规则"说我只能说C1级的3名候选人和C2级的6名候选人.

这种约束建议使用分支定界技术或其他形式的修剪的图搜索类型方法,但是由于我只熟悉0-1背包的DP解决方案,我有点难以理解.哪些技术/方法可能适合这个问题？我也想过可能使用约束编程库但不确定它是否能够找到解决方案？

我正在研究动态编程,我正在寻求解决以下问题,可以在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的算法.)

看起来我们有一种二维背包问题,但我认为通过将权重视为矩形区域,可以用传统的背包算法解决它.这看起来像是一种合理的方法吗？

这是我正在学习的课程的编程作业,所以请仅包括概念性讨论和/或伪代码来说明想法.

我已经编写了这个Haskell程序来解决Eu​​ler 15(它使用一些非常简单的动态编程来运行得更快,所以我实际上可以运行它,但删除你期望它运行的O(2^n).

-- Starting in the top left corner of a 2×2 grid, and only being able to move to
-- the right and down, there are exactly 6 routes to the bottom right corner.
--
-- How many such routes are there through a 20×20 grid?

calcPaths :: Int -> Integer
calcPaths s
 = let  go x y
          | x == 0 || y == 0    = 1
          | x == y              = 2 * go x …

我碰到了这个问题,我不确定我的解决方案是否是最佳的.

问题

给定N加权(Wi)和可能重叠的间隔(表示会议时间表),找到进行所有会议所需的会议室的最小数量"&".

例

|---10------|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|---------8---------|

        |------8-----|          |----------10-----------|

                  |--------6-------|

对于上述时间表,我们需要两个10和10个容量的会议室.( 我对么 ？ )

我的解决方案

如果我们有一个容量大于需要的会议室使用它,如果没有符合标准的会议室,建立新房间或增加现有房间,请从一个房间,并从左侧穿过间隔.新的能力.

例:

10点开始 - {10}

8点开始 - {10,8}

10月底结束 - {10-free,8}

6点开始 - {10,8}

结束8 - {10,8-free}

10的开头= {10,8 + = 2}或{10,10}

等等.....

这基本上是贪心的..

• 有人可以证明这不是最优的吗？
• 如果这是非最佳的解决方案是什么？DP？

给定值N,如果我们想要改变N美分,并且我们每个S = {S1,S2,..,Sm}值硬币都有无限供应,我们可以通过多少方式进行更改？硬币的顺序无关紧要.

例如,对于N = 4和S = {1,2,3},有四个解:{1,1,1,1},{1,1,2},{2,2},{1, 3}.因此输出应为4.对于N = 10且S = {2,5,3,6},有五种解决方案:{2,2,2,2,2},{2,2,3,3}, {2,2,6},{2,3,5}和{5,5}.所以输出应该是5.

我在这里发现了3种方法.但是无法理解空间优化的动态编程方法,其中仅使用单维数组表[].

int count( int S[], int m, int n )
{
    // table[i] will be storing the number of solutions for
    // value i. We need n+1 rows as the table is consturcted
    // in bottom up manner using the base case (n = 0)
    int table[n+1];

    // Initialize all table values as 0
    memset(table, 0, sizeof(table));

    // Base case (If given value is …

我需要这个动态编程问题的帮助.

给定正整数k,找到求和的不同正整数的最大数量k.例如,6 = 1 + 2 + 3,因此答案为3,而5 + 1或4 + 2则为2.

我想到的第一件事是我必须找到一个子问题.因此,要找到最大总和k,我们需要找到小于的最大值k.所以我们必须迭代这些值1 -> k并找到这些值的最大总和.

令我困惑的是如何制作一个公式.我们可以定义M(j)为总和的最大不同值的数量j,但我如何实际为其编写公式？

到目前为止,我的逻辑是否正确,有人可以解释如何逐步完成这项工作吗？

最近我设计了一个儿童难题来解决.但是,我想现在最优解决方案.

问题如下:你有这个数字由小方块组成

你必须用更大的方块填充它,并使用下表进行评分:

| Square Size | 1x1 | 2x2 | 3x3 | 4x4 | 5x5 | 6x6 | 7x7 | 8x8 |
|-------------|-----|-----|-----|-----|-----|-----|-----|-----|
| Points      | 0   | 4   | 10  | 20  | 35  | 60  | 84  | 120 |

有很多可能的解决方案来检查它们.其他人建议动态编程,但我不知道如何将数字划分为较小的数字,这些数字放在一起具有相同的最优解.

我想找到一种方法,在合理的时间内找到解决这类问题的最佳方案(比如常规桌面上最多几天).到目前为止,使用猜测算法和一些手动工作找到的最高分是1112.

还可以理解组合子问题的类似问题的解决方案.我不需要写出所有代码.算法的概要或想法就足够了.

注意:可以容纳的最大正方形是8x8,因此不包括较大正方形的分数.

[[1,1,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,1,1],
 [1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1],
 [1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1],
 [0,0,0,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
 [0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1],
 [0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1],
 [1,0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1],
 [1,1,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1],
 [1,1,1,0,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,0,0],
 [0,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,1,0,0,0],
 [0,0,1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
 [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0],
 [0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1],
 [0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1],
 [0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],
 [0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0],
 [1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0],
 [0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0],
 [0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
 [0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
 [0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
 [0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1],
 [0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1],
 [0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1], …

医院正在改变他们对设备进行消毒的方式.此前,当地的外科医生保留了所有自己的设备并制作了自己的手术托盘.现在他们必须限制在全国范围内.他们想知道他们可以用现有库存制造多少新托盘,以及他们需要购买多少新设备.

医疗设备库存如下:

http://pastebin.com/rstWSurU

每家医院都有各种医疗设备的代码,然后是相应项目的数量

3个手术托盘及其相应的项目显示在这本词典中.

http://pastebin.com/bUAZhanK

共有144个不同的操作托盘

医院将被告知他们需要25个托盘x,30个托盘y等...

他们希望最大化他们可以用现有库存完成的托盘数量.他们还想知道他们需要购买哪些设备才能完成剩余的托盘.

我考虑过两种可能的解决方案,一种是将问题表示为线性规划问题.另一个解决问题的方法是通过循环蛮力解决问题的前90%,并通过多次随机算法解决剩余的10%,然后选择那些尝试的最佳解决方案.

我很想知道是否有人知道如何解决这个问题的聪明方法!