여행 짐싸기 문제 반복적 dp

  • riceluxs1t
    riceluxs1t

    아래는 제 코드입니다. 익히 알려진 문제라 반복적 형태로 dp로 짰습니다.
    하지만 오류를 뿌리는걸로 봐서 어딘가 잘못된 답이 출력되는것 같습니다.

    의심 되는 부분은
    1) 최대값을 내는 답 조합이 복수 일 때 아무거나 출력해도 된다고 했는데
    출력 되는 이름의 순서또한 상관 없습니까?

    예를 들어
    1
    3 10
    laptop 5 10
    camera 5 10
    money 10 20 일때

    1) 20, 1
    money와

    2) 20, 2
    laptop
    camera

    3) 20, 2
    camera
    laptop

    위 3개의 답안 모드 답으로 처리 되는지요

    2) 이 부분 외에는 오답이 뜰만한 이유가 생각이 나질 않습니다..

    제 코드는

    1) dp[i][j] = max(dp[i-1][j], dp[i-1][j - volume[i]] + value[i]) 의 점화식을 이용 했습니다. 2중 중첩문으로 구성되다 보니 현재 아이템 i를 고려할 때 i가 현재 넣을수 있는 무게보다 낮을 경우 넣는 경우와 넣지 않고 i-1번째 아이템까지만 고려한 경우 두가지를 비교합니다. i번째 아이템이 가방에 못넣고 무거운 경우는
    dp[i][j] = dp[i-1][j]로 따로 처리 했습니다.

    2) 나중에 아이템을 수집하는 과정은
    끝 아이템부터 시작해서 dp[i][j] != dp[i-1][j] 일 경우 item을 넣었는 경우이니 하나씩 모은 다음 출력합니다.

    코드가 가독성이 많이 떨어져서 주석 달았습니다. 한번 봐주시면 감사하겠습니다. ㅜ

    #dp 테이블
dp = []
for i in range(101):
    dp.append([0]*1001)

#dp 테이블 리셋하는 함수.
def resetDP(a,b):
    for i in range(a):
        for j in range(b):
            dp[i][j] = 0
"""
@all_in_one - (volume, need, name) 형식으로 0-indexed 입니다
@w - 전체 용량

"""
def packingDP(all_in_one, w):

    n = len(all_in_one)
    resetDP(n, w+1)
    #이중 중첩문은 1부터 n까지 셉니다. all_in_one은 0부터 세기때문에.. 조금 가독성이 떨어지네요
    for i in range(1, n+1):
        for j in range(0, w+1):

            if all_in_one[i-1][0] <= j:
                if dp[i-1][j] > dp[i-1][j - all_in_one[i-1][0]] + all_in_one[i-1][1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j - all_in_one[i-1][0]] + all_in_one[i-1][1]
            else:
                dp[i][j] = dp[i-1][j]
    item = n
    vol = w
    num = 0
    picked = []
    while item >= 0:
        if dp[item][vol] == dp[item-1][vol]:
            item -= 1
        else:
            vol -= all_in_one[item-1][0]
            picked.append(all_in_one[item-1][2])
            num += 1
            item -= 1
    print dp[n][w], num
    #picked.reverse()
    for i in picked: print i

for _ in xrange(input()):
    line = raw_input().split(' ')
    w = int(line[1])
    all_in_one = []
    for _ in range(int(line[0])):
        line = raw_input().split(' ')
        all_in_one.append((int(line[1]), int(line[2]), line[0]))
    packingDP(all_in_one, w)


    9년 전
2개의 댓글이 있습니다.
  • mongsiry014
    mongsiry014 
    while item >= 0:
    if dp[item][vol] == dp[item-1][vol]:
        item -= 1
    else:
        vol -= all_in_one[item-1][0]
        picked.append(all_in_one[item-1][2])
        num += 1

    이 while문은 문제가 있어요.
    item이 0일 때가 문제에요
    if dp[item][vol] == dp[item-1][vol]에서 item이 0이면
    if dp[0][vol] == dp[-1][vol]이 되죠.
    파이썬에서 배열에 -1이 들어가는것은 마지막 배열을 의미하죠
    코드를 보니 dp[0][vol]은 항상 0값을 갖고 있네요.
    하지만 dp[-1][vol]은 0이 아닌 경우가 있어요.
    언제냐면 물건의 개수가 100개 일때에요.
    물건의 개수 입력값이 1~100인데 즉 물건의 개수가 최대값으로 들어오는 경우 문제가 발생합니다.

    테스트를 위해서 코드를 초기화 부분 코드를 잠깐 수정해볼게요.
    #dp 테이블
    dp = []
    for i in range(101):
    dp.append([0]*1001)
    <---------- 이 부분을

    #dp 테이블
    dp = []
    for i in range(2+1):
    dp.append([0]*1001)
    item -= 1
    <---------- 이렇게 바꿔보고 테스트합니다.

    즉 물건의 개수 최대값이 100개가 아니라 2개라고 가정해보죠.

    입력 :
    1
    2 2
    a 5 5
    b 1 1

    출력 :
    1 2
    b
    b

    물건의 개수값이 최대로 입력이 들어왔을 때
    문제가 되는 while문에서 item이 0일 때도 물건 b를 리스트에 추가하여 최종적으로 b가 두번 추가되고 있어요
    dp의 크기를 101개로 하는게 아닌 102개로 하고 dp[-1][volume]이 항상 0이 되게 하던지, 문제가 되는 while문을 수정하던지 하면 될것 같네요.


    9년 전 link
  • riceluxs1t
    riceluxs1t

    와 그냥 방치해두고 있던 문제인데 정말감사합니다!


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.