问题标签 [dynamic-programming]

是否有任何资源可以找到真正的代码来解决动态编程中的问题，例如 PHP 中的背包问题等等？

我想自己分析代码，因为我不太了解理论。而且我在 Google 中找不到任何代码。

非常感谢你。

n-puzzle问题是否有DP方法

谢谢大家，谢谢...

拉詹

这基本上是重复的：

如何将字符串拆分为单词。例如：“stringintowords”->“String Into Words”？

neverthelees，我在使用中使用了一个函数，例如：public int Word(x) {code}，对于字符串 x，它将返回一个整数（+ve 或 -ve），并且该整数将指示分区对于特定单词的好坏程度. 我应该返回给出最大数量的组合。

我想为此做的是创建一个 table(i,j) ，其中 i 和 j 具有单词的长度，并在 tern 中填写表格，如：

并填写表格，但是，我到底如何才能检索到最佳解决方案（以递归方式？）

任何帮助表示赞赏。

编辑：最佳路径是 word(x) 函数总和最高的路径，即如果我们有
一个 path(1,3)=10 , (3,6)=20, (6,7)=1 和
路径 (1,1)=0 , (2,5)=12, (5,7)=-1
然后第一条路径的总和 > 2nd

EDIT2：我希望每个人都知道，经过长时间的工作，我已经回答了这个问题，不要介意没有得到解决方案，我想自己得到它总是最好的：P

干杯！：）

我正在解决这个问题：

子集和问题将一组X = {x1, x2 ,…, xn}整数n和另一个整数作为输入K。问题是检查是否存在其元素总和的子X'集并找到子集（如果有）。例如，如果和那么答案是因为子集的总和为。为运行时间至少为 的子集和实现算法。XKX = {5, 3, 11, 8, 2}K = 16YESX' = {5, 11}16O(nK)

注意复杂性O(nK)。我认为动态编程可能会有所帮助。

我找到了一个指数时间算法，但它没有帮助。

有人可以帮我解决这个问题吗？

问题如下。

1. 关于“好”

   1）“ab”很好

   2) A 很好 => "a"+A+"b" 很好

   3) A 和 B 很好 => A+B 很好

2. 关于“~”

   1) "ab"~"ab"

   2) A~B => "a"+A+"b"~"a"+B+"b"

   3) A~B 和 C~D => A+C~B+D 和 A+C~D+B

现在最多有 1000 串 'a' 和 'b' 形成一个集合 S，找到 S 的最大子集，其中每个元素都必须是好的，并且对 (A,B) 中的任何一个都不包含 A~B。输出基数。

与我之前看到的问题有些不同：A+B+C+D~A+C+B+D~B+D+A+C 但是 A+B+C+D~B+D+A+C不成立。

对我来说有两个困难：

1. 如何检查S1~S2是否
2. 如果我知道每一对的“~”，我怎么能找到基数

更多细节：https ://www.spoj.pl/problems/ABWORDS/

好的，这是我必须做的

作为 MCI（猛犸蛋糕公司）的员工，您的工作是制作超大的分层生日蛋糕。分层生日蛋糕是通过将小的圆形蛋糕层并将它们堆叠在一起而制成的。

为了完成你的工作，你站在一条大传送带前，而不同大小的层从你面前经过。当你看到你喜欢的，你可以把它从传送带上拿下来，加到你的蛋糕上。

只要您遵循以下规则，您可以根据需要在蛋糕中添加任意数量的层：

一旦将一层添加到您的蛋糕上，它就无法移动。（它弄乱了糖衣。）因此，层只能添加到蛋糕的顶部。

每一层只在你面前经过一次。你可以接受也可以离开。如果你吃了，你必须把它加到蛋糕的顶部。如果你离开它，它会沿着传送带移动，永远不会回来。

蛋糕中的每一层都必须至少与下面的层一样小。您不能在较小的图层上放置较大的图层。

您将被提前告知从传送带上下来的层的直径（以英寸为单位）。你的工作是使用这些层创建最高的蛋糕。例如，假设以下列表表示沿传送带向下的层的直径： 8 16 12 6 6 10 5

假设您将第一层（直径为 8 英寸）用于蛋糕。这意味着您可能不会采用第二层（因为您已经有一个 8 英寸大小的层，并且 16 英寸 > 8 英寸）。同样，你不能拿第三层，但你可以拿第四层（因为 6” < 8”）。

之后，你也可以取第五层（规则很简单，上面的层不能更大；它可以是相同的大小）。以这种方式进行，我们可以创建一个高度为 4 层的蛋糕： 8 6 6 5 但是，如果我们让第一层继续并从第二层开始，我们可以创建一个高度为 5 的蛋糕： 16 12 6 6 5

您的程序将处理多个输入集，每行一个。每行都以整数 N 开头，然后是 N 个正整数，表示蛋糕层的大小，按照它们到达传送带的顺序排列。N 永远是一个非负整数，0 N 100,000。每层的直径在 1 到 100,000 之间，包括 1 到 100,000。N = 0 的行标志着输入的结束

问题：找到最高的蛋糕层

这是我到目前为止所写的：

一位讲师在课堂上提出了这个问题：[问题]

n 个整数的序列存储在数组 A[1..n] 中。如果一个整数 a 在 A 中出现超过 n/2 次，则称为多数。

可以设计一个 O(n) 算法来根据以下观察找到多数：如果原始序列中的两个不同元素被删除，则原始序列中的多数仍然是新序列中的多数。使用这种观察或其他方式，编写编程代码以在 O(n) 时间内找到大多数（如果存在）。

接受此解决方案的[解决方案]

我看不出所提供的解决方案如何是动态解决方案。而且我看不出他是如何根据措辞提取代码的。

This is a hard algorithms problem that :

Divide the list in 2 parts (sum) that their sum closest to (most) each other

list length is 1 <= n <= 100 and their(numbers) weights 1<=w<=250 given in the question.

For example : 23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

I have an algorithm but it didn't work for all inputs.

1. init. lists list1 = [], list2 = []
2. Sort elements (given list) [23 32 34 65 95 123 134]
3. pop last one (max one)
4. insert to the list which differs less

Implementation : list1 = [], list2 = []

1. select 134 insert list1. list1 = [134]
2. select 123 insert list2. because if you insert to the list1 the difference getting bigger
   3. select 95 and insert list2 . because sum(list2) + 95 - sum(list1) is less.

and so on...

这是另一个与动态规划相关的算法问题

这是问题所在：

找到给定矩阵的最小和，使得在每一行和每一列中选择一个

例如 ：

3 4 2

8 9 1

7 9 5

最小的一个：4 + 1 + 7

我认为解决方案是网络流量（最大流量/最小切割），但我认为它不应该像现在那么难

我的解决方案：单独到 n list[column], column1, column2 ... column n

然后起点 (S) -> column1 -> column2 -> ... -> column n -> (E) 终点并实施最大流量/最小切割

这是另一个动态规划问题，在给定矩阵 (mxn) 中找到最大 L(chess horse - 4 item) sum

例如 ：

1 2 3

4 5 6

7 8 9

L : (1,2,3,6), (1,4,5,6), (1,2,5,8), (4,5,6,9) ...

最大的和是 sum(L) = sum(7,8,9,6) = 30

最优解的 O(complexity) 是多少？

看起来像这个问题（最大和的子矩阵）

1. 说所有项目都是正面的

2. 积极的和消极的

欢迎任何想法！