파이썬 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에 튜플과 출력 튜플이 무엇인지 모르겠습니다. 나는 이것을 잠시 보면서 코드가 무엇을 가리키고 있는지 이해하지 못한다. 어떤 도움을 주시면 감사하겠습니다.
목록 작성 기능은 필자가 작성한 기능이므로 이해할 수 있도록 가중치, 값 쌍 목록을 작성합니다. 합계 값에 대한 튜플 합당한 경우 실제 합계 값으로 전환하고 싶습니다. – idalsin