用于无界背包的朴素Python递归算法 - 实现精确的容量

Question

我正在尝试仅使用递归来解决背包问题。容量是一个正整数，我还有一个值/好处列表，每个索引对应一个容量的连续部分。意思是重量i的值为val[i-1]。

我可以（而且应该）重复一些重量的物品。

另外，我必须完全填补这个能力。

根据我在这里和其他网站上找到的内容，这是我写的代码：

def knapsack(val, cap):
    n = len(val)
    return ks_exec(value, n, cap)


def ks_exec(val, i, cap):
    if cap==0 or i==0: 
        return 0
    if cap==1:
        return val[0]
    if i>cap:
        return ks_exec(val, i-1, cap)
    else:
        max(ks_exec(val[:-1],i-1,cap), \
            val[-1]+ks_exec(val,i-1,cap-i))   

但它不起作用。

谁能指出我失败的地方？

Answer 1

我想我明白了！

关键是指索引/权重（也表示值列表的长度）大于所需容量的情况 - 只需将函数减少到原始形式（权重等于容量，并且值列表一样大。

def knapsack(val, cap):
n = len(val)
return ks_exec(value, n, cap)


def ks_exec(val, i, cap):
    if cap==0 or i==0: 
        return 0
    if cap==1:
        return val[0]
    if i>cap:
        return ks_exec(val[:cap], cap, cap)
        ''' we have redundent values for partitions larger than the 
            capacity, so we must reduce to the original problem with the 
            current given capacity.
        '''
    else:
        return max(ks_exec(val[:-1],i-1,cap), \
                   val[-1]+ks_exec(val,i,cap-i))