동적 프로그래밍 접근법 - 배낭 퍼즐

Question

파이썬 3.x와 함께 다이나믹 프로그래밍 (DP) 방식으로 배낭 문제를 해결하려고합니다. 나의 TA는 머리를 시작하기 위해 this code을 향해 우리를 가르쳤다. 나는 아래와 같이 구현하려고 시도했다 :

def take_input(infile): 
    f_open = open(infile, 'r') 
    lines = [] 
    for line in f_open: 
     lines.append(line.strip()) 
    f_open.close() 
    return lines 

def create_list(jewel_lines): 
    #turns the jewels into a list of lists 
    jewels_list = [] 
    for x in jewel_lines: 
     weight = x.split()[0] 
     value = x.split()[1] 
     jewels_list.append((int(value), int(weight))) 
    jewels_list = sorted(jewels_list, key = lambda x : (-x[0], x[1])) 
    return jewels_list 

def dynamic_grab(items, max_weight): 
    table = [[0 for weight in range(max_weight+1)] for j in range(len(items)+1)] 

    for j in range(1,len(items)+1): 
     val= items[j-1][0] 
     wt= items[j-1][1] 
     for weight in range(1, max_weight+1): 
      if wt > weight: 
       table[j][weight] = table[j-1][weight] 
      else: 
       table[j][weight] = max(table[j-1][weight],table[j-1][weight-wt] + val) 

    result = [] 
    weight = max_weight 
    for j in range(len(items),0,-1): 
     was_added = table[j][weight] != table[j-1][weight] 

     if was_added: 
      val = items[j-1][0] 
      wt = items[j-1][1] 
      result.append(items[j-1]) 
      weight -= wt 

    return result 

def totalvalue(comb): 
    #total of a combo of items 
    totwt = totval = 0 
    for val, wt in comb: 
     totwt += wt 
     totval += val 
    return (totval, -totwt) if totwt <= max_weight else (0,0) 

#required setup of variables  
infile = "JT_test1.txt" 
given_input = take_input(infile) 
max_weight = int(given_input[0]) 
given_input.pop(0) 
jewels_list = create_list(given_input) 

#test lines 
print(jewels_list) 
print(greedy_grab(jewels_list, max_weight)) 
bagged = dynamic_grab(jewels_list, max_weight) 
print(totalvalue(bagged)) 

예제는 아래에있다. 그것은 나 다시 발생한다는 점에서

575 
125 3000 
50 100 
500 6000 
25 30 

이 코드의 논리에 관한 혼동 요 (중량 값) 형태이다 : [1] 라인 서식 라인 [0] = bag_max에 튜플과 출력 튜플이 무엇인지 모르겠습니다. 나는 이것을 잠시 보면서 코드가 무엇을 가리키고 있는지 이해하지 못한다. 어떤 도움을 주시면 감사하겠습니다.

Answer 1

나는 당신이 totalvalue에 의해 반환 된 튜플을 참조하고 createlist에 의해 반환 된 목록에 포함되어 있다고 가정합니다. 이 튜플은 모두 두 개의 정수를 포함합니다. 이 두 숫자 중 첫 번째 숫자는 보석의 가치이고, 두 번째 숫자는 보석 인 경우의 무게입니다.

totalvalue에 의해 반환되는 최종 튜플은 최대 무게를 초과하지 않고 입력 보석 목록에서 선택할 수있는 보석의 가능한 최대 값을 나타냅니다.

모든 보석의 가치를 원하면 totalvalue (jewels_list)를 찾아야합니다. 현재 튜플은 모든 보석의 값이 아니라 최대 무게 내에 들어있는 보석의 값입니다.

Answer 2

출력 튜플은 최종 솔루션의 총 값과 총중량을 나타냅니다.

bagged는 [[125,3000], [500,6000]]과 같은 목록입니다. 함수 합계 값은 모든 것을 더합니다.