我在理解动态规划方面遇到困难,所以我决定解决一些问题。我知道基本的动态算法,比如最长公共(public)子序列、背包问题,但我知道它们是因为我读过它们,但我不能自己想出一些东西:-(
例如,我们有自然数的子序列。我们可以加上或减去的每个数字。最后我们取这个和的绝对值。对于每个子序列,找到可能的最低结果。
in1: 10 3 5 4; 输出 1: 2
in2: 4 11 5 5 5; 输出 2:0
in3: 10 50 60 65 90 100; 输出 3: 5
第三个的解释:5 = |10+50+60+65-90-100|
更糟糕的是,我的 friend 告诉我这是一个简单的背包问题,但我在这里看不到任何背包。动态规划是不是很难,或者只有我有大问题?
最佳答案
正如 amit 所指出的,该算法可以理解为 partition problem 的一个实例.对于简单的实现,请查看此 Python 代码:
def partition(A):
n = len(A)
if n == 0:
return 0
k, s = max(A), sum(A)/2.0
table = [0 if x else 1 for x in xrange(n*k)]
for i in xrange(n):
for j in xrange(n*k-1, -1, -1):
if table[j-A[i]] > table[j]:
table[j] = 1
minVal, minIdx = float('+inf'), -1
for j in xrange(int(s)+1):
if table[j] and s-j < minVal:
minVal, minIdx = s-j, j
return int(2*minVal)
当使用问题中的输入之一调用时:
partition([10, 50, 60, 65, 90, 100])
它将按预期返回 5
。为了充分理解解决方案背后的数学原理,请查看此 examples并单击“平衡分区”链接。
关于algorithm - 动态规划的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9862178/