相关疑难解决方法(0)

这是我上一个问题的后续行动.我仍然觉得这是一个非常有趣的问题,因为有一种算法值得我更多关注,我在这里发布它.

来自维基百科:对于每个xi都是正的并且由相同的常数界定的情况,Pisinger找到了线性时间算法.

有一篇不同的论文似乎描述了相同的算法,但对我来说有点难以阅读,所以请 - 有谁知道如何将伪代码从第4页(balsub)转换为工作实现？

以下是我目前收集的几个指针:

http://www.diku.dk/~pisinger/95-6.ps(该文件)
/sf/answers/696693161/
http://www.diku.dk/hjemmesider/ansatte/pisinger /codes.html

PS:我并不是真的坚持这个算法,所以如果你知道任何其他类似的性能算法,请随意建议它.

编辑

这是旧版本发布的代码的Python版本:

class view(object):
    def __init__(self, sequence, start):
        self.sequence, self.start = sequence, start
    def __getitem__(self, index):
        return self.sequence[index + self.start]
    def __setitem__(self, index, value):
        self.sequence[index + self.start] = value

def balsub(w, c):
    '''A balanced algorithm for Subset-sum problem by David Pisinger
    w = weights, c = capacity of the knapsack'''
    n = len(w)
    assert n > 0
    sum_w = 0
    r …

最近我对子集求和问题产生了兴趣,该问题是在超集中找到零和子集.我在SO上找到了一些解决方案,此外,我遇到了一个使用动态编程方法的特定解决方案.我根据他的定性描述在python中翻译了他的解决方案.我正在尝试对更大的列表进行优化,这会占用大量的内存.有人可以推荐优化或其他技术来解决这个特殊问题吗？这是我在python中的尝试:

import random
from time import time
from itertools import product

time0 = time()

# create a zero matrix of size a (row), b(col)
def create_zero_matrix(a,b):
    return [[0]*b for x in xrange(a)]

# generate a list of size num with random integers with an upper and lower bound
def random_ints(num, lower=-1000, upper=1000):
    return [random.randrange(lower,upper+1) for i in range(num)]

# split a list up into N and P where N be the sum of the negative values and P …

我完全陷入困境,不知道如何解决这个问题.假设我有一个阵列

arr = [1, 4, 5, 10]

和一个数字

n = 8

我需要从arr内等于n的最短序列.所以例如在arr等于n之后的序列

c1 = 5,1,1,1
c2 = 4,4
c3= 1,1,1,1,1,1,1,1

所以在上面的例子中,我们的答案是c2,因为它是arr中等于sum的最短序列.

我不确定找到上述解决方案的最简单方法是什么？任何想法或帮助将非常感激.

谢谢!

编辑:

• 修复了数组
• 数组可能只有正值.
• 我不确定子集问题如何解决这个问题,可能是由于我自己的无知.子集算法总是给出等于和的最短序列吗？例如,子集问题会将c2识别为上述场景中的答案吗？

在我目前的面试准备期间,我遇到了一个问题,我遇到了一些难以获得最优解的问题.
我们给出了一个数组A和一个整数Sum,我们需要找到所有不同的子序列,A其总和等于Sum.
例如.A={1,2,3,5,6} Sum=6然后回答应该是
{1,2,3}
{1,5}
{6}

现在我可以想到两种方法,

1. 使用递归(我认为这应该是面试问题的最后一件事)
2. 使用整数分区来分区Sum并检查分区的元素是否存在A

请引导我的想法.

该子集和问题是众所周知的是NP完全性,但也有不同的技巧,有些快速解决问题的版本.

通常的动态编程算法需要随目标总和增长的空间.我的问题是:我们可以减少这个空间要求吗？

我试图用适度数量的元素解决子集和问题,但目标总和非常大.对于指数时间算法(和快捷方法),元素的数量太大,并且目标总和对于通常的动态编程方法来说太大.

考虑这个解决问题的玩具问题.给定集合A = [2, 3, 6, 8]查找总和的子集数量target = 11.枚举所有子集我们看到答案是2:(3, 8)和(2, 3, 6).

动态编程解决方案当然会给出相同的结果 - ways[11]返回2:

def subset_sum(A, target):
    ways = [0] * (target + 1)
    ways[0] = 1
    ways_next = ways[:]
    for x in A:
        for j in range(x, target + 1):
            ways_next[j] += ways[j - x]
        ways = ways_next[:]

    return ways[target]

现在考虑定位target = 1100集合的总和A = [200, 300, 600, 800] …

这是我们算法期末考试的问题.这是逐字的,因为教授让我们把考试的副本带回家.

1. (20分)设I = {r1,r2,...,rn}是一组n个任意正整数,I中的值是不同的. 我没有按任何排序顺序给出.假设我们想找到一个子集I"的我,使得所有元素的总和I"正好是100*小区(N ^ .5)(中的每个元素我可以在最多出现一次I").提出一种O(n)时间算法来解决这个问题.

据我所知,它基本上是背包问题的一个特例,也就是称为子集和问题......两者都在NP中,理论上在线性时间内无法解决？

那么......这是一个棘手的问题吗？

这个SO帖子基本上解释了如果权重是有限的,可以进行伪多项式(线性)时间近似,但在考试问题中,权重不受限制,无论哪种方式考虑到考试的整体难度我都会感到震惊如果教授希望我们知道/想出一个模糊的动态优化算法.