解决在使用背包Dyanamic编程 [英] Solving Knapsack using Dyanamic Programming

问题描述

我使用，我发现在这个环节的背包

我还附上了算法的片段也在这里。

以下Python代码片段的算法我写。在这里，它是：

 高清背包（V，W，N，W）：
    V = [[无对于x范围内（W + 1）]对于x范围内（LEN（五）+1）]

    对于WY在范围（W + 1）：
        V [0] [WY] = 0

    对于i在范围（1，N + 1）：
        为WX在范围（W + 1）：
            ＃打印我，WX
            当w [1]  - ; = WX：

                v [电流] [蜡质] =最大值（V [I-1] [WX]，V [I] + V [I-1] [WX-瓦特[I]]）
            其他：
                v [电流] [蜡质] = V [I-1] [WX]
    返回V [n]的[W]

打印背包（ν= [10,40,30,50]，瓦特= [5,4,6,3]中，n = 4，W = 10）
 

我应该得到的输出的 90 在位置 [4,9] 。我在做什么错在这里？

解决方案

我不知道，但我认为错误的是

• 元素 V和W 0是基于指数（0到n-1）
• 您是迭代的范围 1到n
• 所以 W [N] 或 v [N] 将抛出 IndexError

更新code：

 高清背包（V，W，N，W）：
    V = [[无对于x范围内（W + 1）]对于x范围内（LEN（五）+1）]

    对于WY在范围（W + 1）：
        V [0] [WY] = 0

    对于i在范围（1，N + 1）：
        为WX在范围（W + 1）：
            ＃打印我，WX
            当w [I-1] = WX：

                v [电流] [蜡质] =最大值（V [I-1] [WX]，V [I-1] + V [I-1] [WX-瓦特[I-1]]）
            其他：
                v [电流] [蜡质] = V [I-1] [WX]
    返回V [n]的[W]

打印背包（ν= [10,40,30,50]，瓦特= [5,4,6,3]中，n = 4，W = 10）
 

输出现在 90 。

检查结果为： Ideone

I was implementing the snippet of Knapsack problem using the algorithm that i found in this link Knapsack Problem

I have also attached the snippet of the algorithm here too.

I have written following python snippet for the algorithm. Here it is:

def knapsack(v,w,n,W):
    V = [[None for x in range(W+1)] for x in range(len(v)+1)]

    for wy in range(W+1):
        V[0][wy] = 0

    for i in range(1,n+1):
        for wx in range(W+1):
            # print i,wx
            if w[i] <= wx:

                V[i][wx] = max(V[i-1][wx], v[i]+V[i-1][wx-w[i]])
            else:
                V[i][wx] = V[i-1][wx]
    return V[n][W]

print knapsack(v = [10,40,30,50],w=[5,4,6,3],n=4,W=10)

I am supposed to get output 90 at position [4,9] . What am I doing wrong here?

解决方案

I am not sure but i think the error is

• Elements v and w are 0-based index(0 to n-1)
• You are iterating in the range 1 to n
• So w[n] or v[n] will throw IndexError

Updated CODE:

def knapsack(v,w,n,W):
    V = [[None for x in range(W+1)] for x in range(len(v)+1)]

    for wy in range(W+1):
        V[0][wy] = 0

    for i in range(1,n+1):
        for wx in range(W+1):
            # print i,wx
            if w[i-1] <= wx:

                V[i][wx] = max(V[i-1][wx], v[i-1]+V[i-1][wx-w[i-1]])
            else:
                V[i][wx] = V[i-1][wx]
    return V[n][W]

print knapsack(v = [10,40,30,50],w=[5,4,6,3],n=4,W=10)

The output is now 90.

Check the results at Ideone

这篇关于解决在使用背包Dyanamic编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！