Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Wrong Answer

Solution code:
n,tot_weig = list(map(int,input().split()))
dd={}
for _ in range(n):
    w,v = list(map(int,input().split()))
    if w not in dd:
        dd[w]=v
    else:
        dd[w] = max(dd[w],v)
#print(dd)
dp = [[0]*(tot_weig+1) for i in range(len(dd.keys()))]
#print(dp)
for ii,i in enumerate(dd.keys()):
    for j in range(tot_weig+1):
        if j==0:
            continue
        if ii==0:
            if j<i:
                continue
            else:
                dp[ii][j] = dd[i]
        if j<i:
            dp[ii][j] = dp[ii-1][j]
        else:
            dp[ii][j] = max(dd[i]+dp[ii-1][j-i],dp[ii-1][j])
#print(dp)
print(dp[ii][j])

Submission status: Wrong Answer

Solution code:
def knapsack_1():
    n, w = list(map(int, input().split()))
    items = []
    items.append([0, 0])
    for _ in range(n):
        items.append(list(map(int, input().split())))
    dp = [[0]*(w+1)]*(n+1)
    def helper(pos, t_w):
        if t_w >= w:
            return 0
        maxi = 0
        if dp[pos][t_w] != 0:
            return dp[pos][t_w]
        for i in range(pos+1, len(items)):
            if t_w + items[i][0] <= w:
                maxi = max(maxi, items[i][1] + helper(i, t_w + items[i][0]))
        dp[pos][t_w] = maxi
        return maxi

    print(helper(0, 0))

knapsack_1()

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))

Sum_Weight = sum(map(lambda x:x[0],Goods_List))
dp = [[-1] * (W + 1) for i in range(N)]

for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    dp[i][0] = 0
    if (i == 0) & (Current_Weight <= W) :
        dp[i][Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = [j for j, x in enumerate(dp[i-1]) if x > -1]
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        for k in range(len(Last_Search_List)):
            Last_Search_Weight =  Last_Search_List[k] 
            Current_Search_Weight = Current_Search_List[k] 
            dp[i][Last_Search_Weight] = dp[i-1][Last_Search_Weight]
            if Current_Search_Weight <= W:
                dp[i][Current_Search_Weight] = max((dp[i][Last_Search_Weight] + Current_Value),dp[i][Current_Search_Weight])


print(max(dp[N-1]))

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
    Goods_List[i].append(Goods_List[i][1]/Goods_List[i][0])

Goods_List.sort(key=lambda x:x[0] , reverse=True)
Goods_List.sort(key=lambda x:x[2] , reverse=True)
Goods_List.sort(key=lambda x:x[1] , reverse=True)

Knap_Sack_Weight = 0
Knap_Sack_Value = 0
for j in range(len(Goods_List)):
    Current_Weight = Goods_List[j][0]
    Current_Value = Goods_List[j][1]
    if Knap_Sack_Weight + Current_Weight <= W:
        Knap_Sack_Weight += Current_Weight
        Knap_Sack_Value += Current_Value
        
        
        
print(Knap_Sack_Value)

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
    Goods_List[i].append(Goods_List[i][1]/Goods_List[i][0])

Goods_List.sort(key=lambda x:x[2] , reverse=True)
Goods_List.sort(key=lambda x:x[1] , reverse=True)

Knap_Sack_Weight = 0
Knap_Sack_Value = 0
for j in range(len(Goods_List)):
    Current_Weight = Goods_List[j][0]
    Current_Value = Goods_List[j][1]
    if Knap_Sack_Weight + Current_Weight <= W:
        Knap_Sack_Weight += Current_Weight
        Knap_Sack_Value += Current_Value
        
        
        
print(Knap_Sack_Value)

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
    Goods_List[i].append(Goods_List[i][1]/Goods_List[i][0])

Goods_List.sort(key=lambda x:x[1] , reverse=True)

Knap_Sack_Weight = 0
Knap_Sack_Value = 0
for j in range(len(Goods_List)):
    Current_Weight = Goods_List[j][0]
    Current_Value = Goods_List[j][1]
    if Knap_Sack_Weight + Current_Weight <= W:
        Knap_Sack_Weight += Current_Weight
        Knap_Sack_Value += Current_Value
        
        
        
print(Knap_Sack_Value)

Submission status: Wrong Answer

Solution code:
# D_knapsack 1
N, W = input().split()
N = int(N)
W = int(W)
items = list()
for nn in range(N):
    h = [int(x) for x in input().split()]
    items.append( h )

dp = [[0]*(W+1) for x in range(N+1)]
for ii in range( N ):
    di = ii+1
    for ww in range( W ):
        dw = ww + 1
        if( ww >= items[ii][0] ): # if we can get ii-th item
            tmp1 = dp[di][dw]
            tmp2 = dp[di-1][dw-items[ii][0]+1] + items[ii][1]
            dp[di][dw] = max(tmp1, tmp2)

        dp[di][dw] = max( dp[di][dw], dp[di-1][dw] )
print( dp[-1][-1] )

Submission status: Wrong Answer

Solution code:
def main():
    n,w = map(int,input().split())
    dp = [[0]*(w+1) for j in range(n+1)] # DPテーブルの作成
    v = []
    W = []
    for i in range(n):
        w_,v_ = map(int,input().split())
        v.append(v_)
        W.append(w_)
    for i in range(n):
        for j in range(W[i],w+1):
            if j >= W[i]:
                dp[i+1][j] = max(dp[i][j],dp[i][j-W[i]]+v[i])
            else:
                dp[i+1][j] = dp[i][j]
    print(dp[n][w])
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    N, W = map(int, input().split())

    dp = defaultdict(int)
    dp[0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        keys = list(dp.keys())
        for key in keys:
            new_w = key + w
            if new_w <= W:
                dp[new_w] = max([dp[new_w], dp[key] + v])
    print(max(dp.values()))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#ナップサック問題
#dp[i][w]=i番目までのお菓子で、リュックの中身の重さがw以下となる、選び方の価値の最大値

n,w=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    f,s=map(int,input().split())
    weight.append(f)
    value.append(s)
dp=[[0 for i in range(w+1)]for j in range(n+1)]
for i in range(1,n+1):
    for j in range(w+1):
        #dp[i][j]=dp[i-1][j]
        if j-weight[i]<0:
            continue
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
print(max(dp[n]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

N, W = map(int, input().split())
w, v = [], []
# dp = [[0] * (W+1) for _ in range(N+1)]
dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    t1, t2 = map(int, input().split())
    w.append(t1)
    v.append(t2)

# Initialize dp[0]
for weight in range(W):
    if w[0] <= weight:
        dp[0][weight] = v[0]
    else:
        dp[0][weight] = 0

# print('dp[0]:', dp[0])

for idx in range(1, N):
    for weight in range(1, W+1):
        # Cannot select
        if weight - w[idx] < 0:
        # if weight - w[idx - 1] < 0:
            dp[idx][weight] = dp[idx - 1][weight]
            continue

        # Select
        v1 = dp[idx - 1][weight - w[idx]] + v[idx]
        # v1 = dp[idx - 1][weight - w[idx - 1]] + v[idx - 1]

        # Not Select
        v2 = dp[idx - 1][weight]

        dp[idx][weight] = max(v1, v2)

# for i in range(N):
#     print(dp[i])

# print(dp[N][W])
print(dp[N-1][W])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

N, W = map(int, input().split())
w, v = [], []
dp = [[0] * (W+1) for _ in range(N+1)]

for i in range(N):
    t1, t2 = map(int, input().split())
    w.append(t1)
    v.append(t2)

for idx in range(1, N+1):
    for weight in range(W+1):
        if weight - w[idx - 1] < 0:
            continue

        # Select
        # v1 = dp[idx - 1][weight - w[idx]] + v[idx]
        v1 = dp[idx - 1][weight - w[idx - 1]] + v[idx - 1]

        # Not Select
        v2 = dp[idx - 1][weight]

        dp[idx][weight] = max(v1, v2)

# for i in range(N+1):
#     print(dp[i])
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

N, W = map(int, input().split())
w, v = [], []
dp = [[0] * (W+1) for _ in range(N+1)]

for i in range(N):
    t1, t2 = map(int, input().split())
    w.append(t1)
    v.append(t2)

for idx in range(1, N):
    for weight in range(W+1):
        if weight - w[idx] < 0:
            continue

        # Select
        v1 = dp[idx-1][weight - w[idx]] + v[idx]

        # Not Select
        v2 = dp[idx-1][weight]

        dp[idx][weight] = max(v1, v2)

print(dp[N-1][W])

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[-1 for j in range(w+1)] for i in range(n+1)]
for i in range(n,-1,-1):
    for j in range(0,w+1,1):
        if i==n or j==0:
            dp[i][j]=0        
        elif li[i][0]>j:
            dp[i][w]=dp[i+1][w]
        else:
            dp[i][j]=max(dp[i+1][j-li[i][0]]+li[i][1],dp[i+1][j])
print(dp[i][w])

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[[-1,-1] for j in range(w+1)] for i in range(n)]
dp[n-1][0]=[li[n-1][1],li[n-1][1]]
for i in range(n-1,-1,-1):
    for j in range(w,-1,-1):
        if j==0:
            dp[i][j]=li[i][1],li[i][1]
        if i==(n-1):
            if li[i][0]<=j:
                dp[i][j]=li[i][1],li[i][1]
            else:
                dp[i][j]=0,0
        else:
            mx=li[i][1]
            for k in range(i+1,n):
                if (j-li[i][0])>=li[k][0]:
                    if dp[k][j-li[i][0]]==[-1,-1]:
                        val=recur(li,j,n,j-li[i][0],dp)
                        dp[k][j-li[i][0]]=val
                    else:
                        val=dp[k][w-li[i][0]]
                    mx=max(mx,val[0]+li[i][1])
            if dp[i+1][j]==[-1,-1]:
                val=recur(li,i+1,n,j,dp)
                dp[i+1][j]=val
            else:
                val=dp[i+1][j]
            overall=max(mx,val[1])
            dp[i][j]=[mx,overall]
print(dp[0][w][1])

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[[-1,-1] for j in range(w+1)] for i in range(n)]
dp[n-1][0]=[li[n-1][1],li[n-1][1]]
for i in range(n-1,-1,-1):
    for j in range(w,-1,-1):
        if j==0:
            dp[i][j]=li[i][1],li[i][1]
        if i==(n-1):
            if j<=li[i][0]:
                dp[i][j]=li[i][1],li[i][1]
            else:
                dp[i][j]=0,0
        else:
            mx=li[i][1]
            for k in range(i+1,n):
                if (j-li[i][0])>=li[k][0]:
                    if dp[k][j-li[i][0]]==[-1,-1]:
                        val=recur(li,j,n,j-li[i][0],dp)
                        dp[k][j-li[i][0]]=val
                    else:
                        val=dp[k][w-li[i][0]]
                    mx=max(mx,val[0]+li[i][1])
            if dp[i+1][j]==[-1,-1]:
                val=recur(li,i+1,n,j,dp)
                dp[i+1][j]=val
            else:
                val=dp[i+1][j]
            overall=max(mx,val[1])
            dp[i][j]=[mx,overall]
print(dp[0][w][1])

Submission status: Wrong Answer

Solution code:
import sys;
import math;
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

N,W = get_ints();
arr = [];
for i in range(N):
    tarr = get_array();
    arr.append(tarr);
dp = [[0 for i in range(W+1)] for i in range(N+1)];
for i in range(1,N+1):
    for j in range(1,W+1):
        if(j-arr[i-1][0])>=0:
            dp[i][j]=max(dp[i-1][j],arr[i-1][1]+dp[i-1][j-arr[i-1][0]]);

#for i in range(N+1):
#    print(*dp[i])
print(dp[N][W]);

Submission status: Wrong Answer

Solution code:
import sys
import math
import numpy as np
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    N ,W = I2()
    w = [0]*N
    v = [0]*W
    dp = np.zeros([N+1,W+1],dtype = "int64")
    for i in range(N):
        a,b = I2()
        w[i] = a
        v[i] = b
    for i in range(N):
        for j in range(0,W+1):
            if(j >= w[i]):
                dp[i+1][j] = max(dp[i+1][j],dp[i][j-w[i]] + v[i])
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
            print(dp)
    print(dp[N][W])

Submission status: Wrong Answer

Solution code:

def knapsack1(N,W,weight,value):
    DP = [[0]*(W+1) for i in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            if j-weight[i] >= 0:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j-weight[i]]+value[i])
            else:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j])
    return DP 

def chmax(a,b):
    if a > b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,W = map(int,input().split())
    weight = [0]*N
    value = [0]*N
    #print(weight,value)
    for i in range(N):   
        lst = list(map(int,input().split()))
        #print(lst)
        weight[i] = lst[0]
        value[i] = lst[1]
        #max_w += lst[0]
    #print(weight,value)
    ans = knapsack1(N,W,weight,value)
    print(max(max(ans)))
    #print(max(ans[-1]))

Submission status: Wrong Answer

Solution code:

def knapsack1(N,W,H,max_W):
    #print(W,H,max_W)
    #print(H[1][0],H[1][1])
    DP = [[0]*(max_w+1) for i in range(N+1)]
    #print(DP[0][0],DP[0][1])
    for i in range(N):
        for j in range(max_w+1):
            if j-H[i][0] >= 0:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j-H[i][0]]+H[i][1])
            else:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j])
        #print(DP)
    #print(DP)
    return DP 

def chmax(a,b):
    if a > b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,W = map(int,input().split())
    H = [[0]*2 for i in range(N)]
    max_w = 0
    for i in range(N):   
        lst = list(map(int,input().split()))
        H[i] = lst
        max_w += lst[0]
    ans = knapsack1(N,W,H,max_w)
    finlst = []
    finans = 0
    for i in range(N+1):
        #print(ans[i][W])
        maxr = max(ans[i][:W+1])
        if maxr > finans:
            finans = maxr
    print(finans)
    #print(lstx)
    #print(max(ans[-1]))

Submission status: Wrong Answer

Solution code:

def knapsack1(N,W,H,max_W):
    #print(W,H,max_W)
    #print(H[1][0],H[1][1])
    DP = [[0]*(max_w+1) for i in range(N+1)]
    #print(DP[0][0],DP[0][1])
    for i in range(N):
        for j in range(max_w+1):
            if j-H[i][0] >= 0:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j-H[i][0]]+H[i][1])
            else:
                DP[i+1][j] = chmax(DP[i+1][j],DP[i][j])
        #print(DP)
    #print(DP)
    return DP 

def chmax(a,b):
    if a > b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,W = map(int,input().split())
    H = [[0]*2 for i in range(N)]
    max_w = 0
    for i in range(N):   
        lst = list(map(int,input().split()))
        H[i] = lst
        max_w += lst[0]
    ans = knapsack1(N,W,H,max_w)
    finlst = []
    for i in range(N+1):
        #print(ans[i][W])
        finlst.append(ans[i][W])
    #print(W,ans)
    #print(finlst)
    print(max(finlst))
    #print(max(ans[-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    w, v = map(int, input().split() )
    # dp[n][:] = dp[n-1][:]
    dp[n][w:W+1] = np.maximum(dp[n-1][w:W+1], dp[n-1][:W+1-w]+v )
    # for w_lim in range(1,W+1):
    #     if w_lim - wv[n][0] >= 0 :
    #         dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
    #     else :
    #         dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

n,we =I()
v=[0]*(n+1);w=[0]*(n+1)
dp=[[0]*(we+1) for i in range(n+1)]
for i in range(1,n+1):
	w[i],v[i] = I()
v=[x for _,x in sorted(zip(w,v))]
w.sort()
for i in range(1,n+1):
	for j in range(w[i],we+1):
		st = dp[i-1][j]
		dt=0
		if w[i]<=j:
			dt=v[i]+dp[i-1][j-w[i]]
		dp[i][j] = max(st,dt)
print(dp[n][we])

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
value=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    value.append(b)
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(n+1):
    for j in range(w+1):
        if wt[i-1]<=j:
            dp[i][j]=max(value[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][w])

Submission status: Wrong Answer

Solution code:
def main():
    n, W, *wv = map(int, open(0).read().split())
    dp = [0] * (W + 1)
    for i in range(n):
        w = wv[i * 2]
        v = wv[i * 2 + 1]
        pv = dp[w]
        dp = [max(dp[j], dp[j - w] + v) if j >= w else pv for j in range(0, W + 1)]
    print(dp[W])

main()

Submission status: Wrong Answer

Solution code:
def main():
    n, W, *wv = map(int, open(0).read().split())
    dp = [[0] * (W + 1)] * (n + 1)
    for i in range(n):
        w = wv[i * 2]
        v = wv[i * 2 + 1]
        pv = dp[i][w]
        dp[i + 1] = [max(dp[i][j], dp[i][j - w] + v) if j >= w else pv for j in range(0, W + 1)]
    print(dp[-1][W])

main()

Submission status: Wrong Answer

Solution code:
def main():
    n, W, *wv = map(int, open(0).read().split())
    dp = [[0] * (W + 1)]
    for i in range(n):
        w = wv[i * 2]
        v = wv[i * 2 + 1]
        pv = dp[i][w]
        dpj = [max(dp[i][j], dp[i][j - w] + v) if j >= w else pv for j in range(0, W + 1)]
        dp.append(dpj)
    print(dp[-1][W])

main()

Submission status: Wrong Answer

Solution code:
def main():
    n, W, *wv = map(int, open(0).read().split())
    dp = [[0] * (W + 1)]
    for i in range(n):
        w = wv[i * 2]
        v = wv[i * 2 + 1]
        pv = dp[i][w]
        dpj = [pv for _ in range(0, w)] + [max(dp[i][j], dp[i][j - w] + v) for j in range(w, W + 1)]
        dp.append(dpj)
    print(dp[-1][W])

main()

Submission status: Wrong Answer

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(0,len(dp)):
			#capacity=keys[i]
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					dp[i][j]=max(choices[keys[i]] + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0), dp[i-1][j])
				else:
					dp[i][j]=dp[i-1][j]
		print(dp)
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input().split())
choices={}
for _ in range(n):
	wi,v=map(int,input().split())
	choices[wi]=max(choices.get(wi,0),v)
print(choices)
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Wrong Answer

Solution code:
N, W = map(int,input().split())
v = []
w = []
for i in range(N):
    x,y = map(int,input().split())
    v.append(x)
    w.append(y)

dp = [[0]*(W+1) for j in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])

print(dp[N][W])

Submission status: Wrong Answer

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(len(dp[0])):
			dp[0][i]=max(choices[keys[0]]) if i+1>=keys[0] else 0
		for i in range(1,len(dp)):
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					dp[i][j]=max(max(choices[keys[i]]) + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0), dp[i-1][j])
				else:
					dp[i][j]=dp[i-1][j]
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input().split())
choices={}
for _ in range(n):
	wi,v=map(int,input().split())
	try:
		choices[wi].append(v)
	except:
		choices[wi]=[v]
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Wrong Answer

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(len(dp[0])):
			dp[0][i]=choices[keys[0]] if i+1>=keys[0] else 0
		for i in range(1,len(dp)):
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					dp[i][j]=max(dp[i-1][j],choices[keys[i]] + (dp[i][j-keys[i]] if j-keys[i]>=0 else 0))
				else:
					dp[i][j]=dp[i-1][j]
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input().split())
choices={}
for _ in range(n):
	wi,v=map(int,input().split())
	choices[wi]=v
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Wrong Answer

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(len(dp[0])):
			dp[0][i]=choices[keys[0]] if i+1>=keys[0] else 0
		for i in range(1,len(dp)):
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					dp[i][j]=max(choices[keys[i]],choices[keys[i]] + (dp[i][j-keys[i]] if j-keys[i]>=0 else 0))
				else:
					dp[i][j]=dp[i-1][j]
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input().split())
choices={}
for _ in range(n):
	wi,v=map(int,input().split())
	choices[wi]=v
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Wrong Answer

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(len(dp[0])):
			dp[0][i]=choices[keys[0]] if i+1>=keys[0] else 0
		for i in range(1,len(dp)):
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					dp[i][j]=max(choices[keys[i]],choices[keys[i]] + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0))
				else:
					dp[i][j]=dp[i-1][j]
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input().split())
choices={}
for _ in range(n):
	wi,v=map(int,input().split())
	choices[wi]=v
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Wrong Answer

Solution code:
import numpy as np

n, w = map(int, input().split())
dp = np.zeros(w+1, dtype=int)

for _ in range(n):
    w, v = map(int, input().split())
    np.maximum(dp[w:], dp[:-w] + v, out=dp[w:])
    print(dp)

print(dp.max())

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

# 最大化問題なので0で初期化
dp = [[0] * (w + 1) for _ in range(n + 1)]

ans = 0
for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j - arr[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1])
            ans = max(ans, dp[i][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(ans)

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

# 最大化問題なので0で初期化
dp = [[0] * (w + 1) for _ in range(n + 1)]

# 品物iを選べる場合、前の行からsum_wから品物iの重さを引いた要素を参照する
for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j - arr[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1])
        else:
            dp[i][j] = dp[i - 1][j]

print(max(max(dp)))

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
dp=[-1]*(w+1)
dp[0]=0
for _ in range(n):
  a,d=map(int,input().split())
  for b in range(w,a-1,-1):
    if dp[b-a]!=-1:
    	dp[b]=max(dp[b],d+dp[b-a])
print(dp[w])

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
dp=[-1]*(w+1)
dp[0]=0
for _ in range(n):
  a,d=map(int,input().split())
  for b in range(w,a-1,-1):
    if dp[b-a]!=-1:
    	dp[b]=max(dp[b],d+dp[b-a])
print(dp[b])

Submission status: Wrong Answer

Solution code:
n,w = map(int, input().split())
high = [0] * (w + 1)
for i in range(n):
    weight, value = map(int, input().split())
    if weight <= w:
        renewal = high[:weight]
        renewal += [max([j+value, k]) for j,k in zip(high[:w-weight+1], high[weight:])]
        high = renewal
high.pop()

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wts = []

for i in range(n):
    wts.append(list(map(int, input().split())))
    
wts.sort()
dp = [[0]*(w+1) for i in range(n)]
dp[0][wts[0][0]] = wts[0][1]

for i in range(1, n):
    for j in range(1+w):
        if j >= wts[i][0]:
            dp[i][j] = max(dp[i-1][j], wts[i][1]+dp[i-1][j-wts[i][0]])
        else:
            dp[i][j] += dp[i-1][j]

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wts = []

for i in range(n):
    wts.append(list(map(int, input().split())))
    
dp = [[0]*(w+1) for i in range(n)]
dp[0][wts[0][0]] = wts[0][1]

for i in range(1, n):
    for j in range(1+w):
        if j >= wts[i][0]:
            dp[i][j] = max(dp[i-1][j], wts[i][1]+dp[i-1][j-wts[i][0]])
        else:
            dp[i][j] += dp[i-1][j]

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wts = []

for i in range(n):
    wts.append(list(map(int, input().split())))
    
dp = [[0]*(w+1) for i in range(n)]
dp[0][wts[0][0]] = wts[0][1]

for i in range(1, n):
    for j in range(1+w):
        if j >= wts[i][0]:
            dp[i][j] = max(dp[i-1][j], wts[i][1]+dp[i-1][j-wts[i][0]])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wts = []

for i in range(n):
    wts.append(list(map(int, input().split())))
    
dp = [[0]*(w+1) for i in range(n)]
dp[0][wts[0][0]] = wts[0][1]

for i in range(1, n):
    for j in range(1, 1+w):
        if j >= wts[i][0]:
            dp[i][j] = max(dp[i-1][j], wts[i][1]+dp[i-1][j-wts[i][0]])

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
NW = list(map(int, input().split()))
N = NW[0]
W = NW[1]
wv = []
for i in range(N):
    wv.append(list(map(int, input().split())))

valunable = []
for i in range(N):
    valunable.append([wv[i][1]/wv[i][0], wv[i][0]])

vPerw = sorted(valunable, key=lambda x:x[:][0], reverse=True)
results = []
for s in range(N):
    knapsack = 0
    result = 0
    for i in range(N-s):
        knapsack += vPerw[i+s][1]
        if knapsack>W:
            knapsack -= vPerw[i+s][1]
            continue
        result += vPerw[i+s][0] * vPerw[i+s][1]

    results.append(result)


print(int(max(results)))

Submission status: Wrong Answer

Solution code:
N, W = list(map(int, input().split()))

w = []
v = []
for _ in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

dp = [[0, 0]]
for i in range(1, W+1):
    max_t = 0
    flag = 0
    for j in range(N):
        if w[j] > i or dp[i-w[j]][1] & (1 << j):
            continue
        if max_t < dp[i-w[j]][0] + v[j]:
            max_t = dp[i-w[j]][0] + v[j]
            flag = dp[i-w[j]][1] | (1 << j)
    dp += [[max_t, flag]]
print(dp[W][0])

Submission status: Wrong Answer

Solution code:
n,w = list(map(int,input().strip().split()))

a = [[0] * 2 for i in [0] * n]

for i in range(n):
  a[i] = list(map(int,input().strip().split()))

weight_max = 0
for i in range(n):
  weight_max += a[i][0]

dp = [[0] * (w+1) for i in [0] * (n+1)]

for i in range(n):
  for sum_w in range(w+1):
    if sum_w >= a[i][0]:
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-a[i][0]]+a[i][1])
    dp[i+1][sum_w] = dp[i][sum_w]
print(dp[n][w])

Submission status: Wrong Answer

Solution code:
import numpy as np
N0,W0 = map(int,input().split())

import copy
def exec_dp(N,W):
  dp = np.zeros(W+1,dtype=np.int64) 
  for i in range(N):
    w,v = map(int,input().split())
    prev = copy.copy(dp)
    for j in range(W+1):
      if j >= w:
        dp[j] = np.maximum(prev[j-w]+v, prev[j])
    print(dp)
  print(dp[-1])

exec_dp(N0,W0)

Submission status: Wrong Answer

Solution code:
import sys,io
from functools import lru_cache
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
N,W=reads()
w,v=[0]*N,[0]*N
for i in range(N):
    w[i],v[i]=reads()
price=[[ 0 for _ in  range(W+1) ] for _ in range(N+1)]
print(price)
for i in range(N):
  for k in range(1,W+1):
        if k-w[i]>=0:
            com=price[i][k-w[i]]+v[i]
        else:
          com=0
        price[i+1][k]=max(com,price[i][k]) 
print(price)
print("{}".format(price[N][W]))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
a = list()
a.append([0, 0])
inf = float('inf')
for _ in range(N):
  x = list(map(int, input().split()))
  a.append(x)
print(a)
dp = [[-inf for _ in range(W+1)]for _ in range(N+1)]
# dp[i][w] : i-1番目までで、wを超えないように選んだ時の価値の最大値
for w in range(W+1):
  dp[0][w] = 0
for i in range(1, N+1):
  for w in range(W+1):
    # i番目を選ぶかもしれないとき
    if w - a[i][0] >= 0:
      dp[i][w] = max(dp[i-1][w], dp[i-1][w-a[i][0]] + a[i][1])
      print('a',i,w,dp[i][w])
    # i番目を選ばないとき
    else:
      dp[i][w] = dp[i-1][w]
      print('b',i,w,dp[i][w])
print(dp)