배낭 사용 Dyanmic 프로그래밍 나는 내가의 내가 점점에서 문제가 된 스택 오버플로에 이전과 같은 질문을 <a href="http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf" rel="nofollow noreferrer">Knapsack Problem</a></p> <p>이 링크에서 볼 수있는 알고리즘을 사용하여 배낭 문제의 조각을 구현했다

Question

정답을 제공하는 실패 return 문에서 출력. 여기에서 확인할 수 있습니다 Previous question

여기 알고리즘의 스 니펫도 첨부했습니다.

나는 알고리즘을 위해 다음과 같은 python 스 니펫을 작성했습니다. 여기있다 :

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

    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]]) 
       keep[i][wx] = 1 
      else: 
       V[i][wx] = V[i-1][wx] 
       keep[i][wx] = 0 
    K = W 
    # print keep 
    for i in range(n,0,-1): 
     if keep[i][K] == 1: 
      print i 
      K = K - w[i-1] 

    return V[n][W] 

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

는 나는 내 값으로 4,2을 얻을 생각하지만, 4,3을 얻고있다. 내가 잘못 가고있는 곳을 정정하십시오. 경우 statament에서

Answer 1

문제 :

당신이

  V[i][wx] = max(V[i-1][wx], v[i-1]+V[i-1][wx-w[i-1]]) 
      keep[i][wx] = 1 

doind하는 (w[i-1] <= wx) and (v[i-1]+V[i-1][wx-w[i-1]] <= V[i-1][wx]) 경우

 if w[i-1] <= wx: 

      V[i][wx] = max(V[i-1][wx], v[i-1]+V[i-1][wx-w[i-1]]) 
      keep[i][wx] = 1 
     else: 
      V[i][wx] = V[i-1][wx] 
      keep[i][wx] = 0 

하지만해야

  V[i][wx] = V[i-1][wx] 
      keep[i][wx] = 0