syuntoku14の進捗

進捗を書きなぐります

AOJでPythonに慣れる(12問目)

問題
A Thief

所感
・リハビリがてらにナップサック問題
・簡単かと思ったけどなぜかTest Case 2でWAに
・何が間違ってるのか全然わからんのでギブアップ

コード

count=1
while True:
    vw=[[0,0]]
    W=int(input())
    if W==0:
        break
    n=int(input())
    for i in range(n):
        vw.append(list(map(int,input().split(','))))
    
    dp=[]
    weight=[]
    
    for _ in range(n+1):
        dp.append([0 for i in range(W+1)])
        weight.append([0 for i in range(W+1)])
    for i in range(1,n+1):
        for j in range(0,W-vw[i][1]+1):
            dp[i][j+vw[i][1]]=max(dp[i-1][j+vw[i][1]],dp[i-1][j]+vw[i][0])
            
            if dp[i-1][j+vw[i][1]]==dp[i-1][j]+vw[i][0]:
                weight[i][j+vw[i][1]]=min(weight[i-1][j]+vw[i][1],weight[i-1][j+vw[i][1]])  
            elif dp[i][j+vw[i][1]]==dp[i-1][j]+vw[i][0]:
                weight[i][j+vw[i][1]]=weight[i-1][j]+vw[i][1]
            else:
                weight[i][j+vw[i][1]]=weight[i-1][j+vw[i][1]]
    print('Case '+'{}'.format(count)+':')
    print(dp[n][W])
    print(weight[n][W])
    count+=1

コードが汚い...