标签: dynamic-programming

这是一个编程问题.

问题如下:

将给出一组数字以及我们必须除以的数字k.我们必须从该数组中选择元素,使得这些元素的总和可以被k整除.这些元素的总和应尽可能大.

输入:

在第一行n上,表示元素的数量.

在下一行,给出了n个数字.

在下一行,我们必须划分k.

输出:

通过从该数组st sum中选择元素,尽可能最大的和可被k整除.

样本输入:

5 
1 6 2 9 5
8

样本输出:

16

注意16可以通过多个数字组合获得,但我们这里只关注最大总和.

我建议的解决方案:

我遍历数组并在给定输入数组的数组b中维护累积和,如:

b=[1 7 9 18 23]

并将数组中的数字mod乘以k并存储到

c=[1 7 1 2 7]

现在数字在c中具有相同的值,即索引0和索引2; 索引1和索引4.现在我已经得到了所有解决方案,答案就是

max(b[2]-b[0],b[4]-b[1])

并且在一种情况下,三个索引在c中具有相同的值,即在其中的情况下

c=[1 2 3 1 1 2]

答案是

max(b[4]-b[0],b[5]-b[1])

基本上减去最右边出现的那个数字的最左边的出现.

我的解决方案只有在有连续元素时才有效.元素之和可以被k整除.期待对正确解决方案的描述

有一个有n个帖子的围栏,每个帖子都可以涂上一种k颜色.您必须绘制所有帖子,使得不超过两个相邻的栅栏柱具有相同的颜色.返回可以绘制栅栏的总方式.

diff - 具有不同颜色的组合的数量,
相同 - 具有相同颜色的组合的数量,
n - 发布的数量,
k - 颜色的数量.

对于n = 1:

diff = k;
same = 0;

对于n = 2:

diff = k * (k - 1);
same = k;

对于n = 3:

diff = (k + k * (k - 1)) * (k - 1);
same = k * (k - 1);

最后的公式是:

diff[i] = (diff[i - 1] + diff[i - 2]) * (k - 1);
same[i] =  diff[i - …

从来没有必要处理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,但我如何实际为其编写公式？

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

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

医疗设备库存如下:

http://pastebin.com/rstWSurU

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

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

http://pastebin.com/bUAZhanK

共有144个不同的操作托盘

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

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

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

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