visited는 이미 계산한 값인지를 표시하는 flag,
value는 계산된 절박도이고요,
item index가 1부터 시작하고,
w=0일 때는 무조건 0 리턴이라 index를 i-1, w-1로 썼습니다.
처음에는 calc_m이 선택한 item의 list까지 반환하도록 작성했다가, 시간 초과되어서
value 계산한 후에 table가지고 list 뽑아내는 함수를 작성했어요.
그랬더니 시간 초과는 아니고 오답이 나오네요.
어디가 잘못된 걸까요?
아래 코드 주석을 보시면 쉽게 이해가 되리라 생각됩니다.
~~~
#!/usr/bin/python
import sys
rl = lambda: sys.stdin.readline()
ntc = int(rl()) # read number of testcases
def calc_m(i, w): # returns max value with given i, w
if w <= 0: # if no room for any items in knapsack
return 0 # no value at all
if visited[i-1][w-1] == 1: # already calculated?
return table[i-1][w-1] # get the value
else: # no stored value
if i==1: # if the first item
if vol[0] <= w: # got room to pack it in?
res = val[0] # yes
else:
res = 0 # no
else: # with multiple items
temp1 = calc_m(i-1, w) # calculate value excluding current item
w2 = w-vol[i-1]
if w2 < 0: # does current item fit in the kanpsack?
res = temp1 # no
else: # yes
temp2 = calc_m(i-1, w2) + val[i-1] # calculate value including current item
if temp1 > temp2: # which has the larger value?
res = temp1 # without current item
else:
res = temp2 # with current item
visited[i-1][w-1] = 1 # set flag
table[i-1][w-1] = res # store value
return res
def trackback(i, w): # determine if the ith item is packed in the optimized knapsack
if i==1: # termination condition
if table[0][w-1] == val[0]:
packed.insert(0, 0)
return 0
w2 = w-vol[i-1]
if w2 >= 0: # does current item fit in the knapsack?
if table[i-1][w-1] - val[i-1] == table[i-2][w2-1]: # if yes, was it packed?
packed.insert(0, (i-1)) # yes
trackback(i-1, w2) # continue search with ith items packed
else: # no
trackback(i-1, w) # continue search without ith item
for i in range(ntc):
n_item, w = map(int, rl().split())
item = []
vol = []
val = []
packed = []
# dp table
table =[[0 for col in range(w)] for row in range(n_item)]
visited =[[0 for col in range(w)] for row in range(n_item)]
for j in range(n_item):
t1, t2, t3 = rl().split()
item.append(t1)
vol.append(int(t2))
val.append(int(t3))
total_value = calc_m(n_item, w)
trackback(n_item, w)
print total_value, len(packed)
for j in packed:
print item[j]
~~~
10년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
pshan
안녕하세요 [[problem:PACKING]] 질문드립니다.
위키에서 0-1 knapsack 항목 참고해서 작성했습니다.
visited는 이미 계산한 값인지를 표시하는 flag,
value는 계산된 절박도이고요,
item index가 1부터 시작하고,
w=0일 때는 무조건 0 리턴이라 index를 i-1, w-1로 썼습니다.
처음에는 calc_m이 선택한 item의 list까지 반환하도록 작성했다가, 시간 초과되어서
value 계산한 후에 table가지고 list 뽑아내는 함수를 작성했어요.
그랬더니 시간 초과는 아니고 오답이 나오네요.
어디가 잘못된 걸까요?
아래 코드 주석을 보시면 쉽게 이해가 되리라 생각됩니다.
~~~
#!/usr/bin/python
import sys
rl = lambda: sys.stdin.readline()
ntc = int(rl()) # read number of testcases
def calc_m(i, w): # returns max value with given i, w
if w <= 0: # if no room for any items in knapsack
return 0 # no value at all
if visited[i-1][w-1] == 1: # already calculated?
return table[i-1][w-1] # get the value
else: # no stored value
def trackback(i, w): # determine if the ith item is packed in the optimized knapsack
if i==1: # termination condition
if table[0][w-1] == val[0]:
packed.insert(0, 0)
return 0
w2 = w-vol[i-1]
if w2 >= 0: # does current item fit in the knapsack?
if table[i-1][w-1] - val[i-1] == table[i-2][w2-1]: # if yes, was it packed?
packed.insert(0, (i-1)) # yes
trackback(i-1, w2) # continue search with ith items packed
else: # no
trackback(i-1, w) # continue search without ith item
for i in range(ntc):
n_item, w = map(int, rl().split())
item = []
vol = []
val = []
packed = []
# dp table
table =[[0 for col in range(w)] for row in range(n_item)]
visited =[[0 for col in range(w)] for row in range(n_item)]
for j in range(n_item):
t1, t2, t3 = rl().split()
item.append(t1)
vol.append(int(t2))
val.append(int(t3))
total_value = calc_m(n_item, w)
trackback(n_item, w)
print total_value, len(packed)
for j in packed:
print item[j]
~~~
10년 전