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:
def knap(v,wt,n,w,dp):
    if n<0:
        return 0
    if n in dp:
        return dp[n]
    if wt[n]>w:
        dp[n]= knap(v,wt,n-1,w,dp)
        return dp[n]
    else:
        dp[n]= max(v[n]+knap(v,wt,n-1,w-wt[n],dp),knap(v,wt,n-1,w,dp))
        return dp[n]
n,w=map(int,input().split())
v,wt=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    v.append(b)
    wt.append(a)
dp={}
ans=knap(v,wt,n-1,w,dp)
print(ans)

Submission status: Wrong Answer

Solution code:
def knapsack(n,w,v,we,val,dp):
    if(dp[n-1][we]!=-1):
        return dp[n-1][we]

    if(we==0 or n==0):
        return val
    res=0
    if(we<w[n-1]):
        res=knapsack(n-1,w,v,we,val,dp)
    else:
        res=max(knapsack(n-1,w,v,we,val,dp),knapsack(n-1,w,v,we-w[n-1],val+v[n-1],dp))
        
    dp[n-1][we]=res
    return res
    

dp=[]
for i in range(101):
    x=[]
    for j in range(100001):
        x.append(-1)
    dp.append(x)

n,we=list(map(int,input().split()))  
w=[]
v=[]
for i in range(n):

    a,b=list(map(int,input().split()))
    w.append(a)
    v.append(b)
val=0
p=knapsack(n,w,v,we,val,dp)
print(p)

Submission status: Wrong Answer

Solution code:
import numpy as np

print('test')

Submission status: Wrong Answer

Solution code:
n, sum_w = map(lambda x: int(x), input().split())

# goods = list[]
all_weights = []
all_values = []
for _ in range(n):  
    w, v = map(lambda x: int(x), input().split())
    all_weights.append(w)
    all_values.append(v)
    

def max_value(i_item, remaining_weight):
    if i_item == n - 1:
        return all_values[i_item] if all_weights[i_item] <= remaining_weight else 0
            
    return max(all_values[i_item] + max_value(i_item+1, remaining_weight - all_weights[i_item]),
        max_value(i_item+1, remaining_weight))

print(max_value(0, sum_w))

Submission status: Wrong Answer

Solution code:
n, sum_w = map(lambda x: int(x), input().split())

# goods = list[]
all_weights = []
all_values = []
for _ in range(n):  
    w, v = map(lambda x: int(x), input().split())
    all_weights.append(w)
    all_values.append(v)
    

def max_value(i_item, remaining_weight):
    if i_item == n - 1:
        if all_weights[i_item] < remaining_weight:
            return all_values[i_item]
        return 0
            
    return max(all_values[i_item] + max_value(i_item+1, remaining_weight - all_weights[i_item]),
        max_value(i_item+1, remaining_weight))

print(max_value(0, sum_w))

Submission status: Wrong Answer

Solution code:
n, sum_w = map(lambda x: int(x), input().split())

# goods = list[]
all_weights = []
all_values = []
for _ in range(n):  
    w, v = map(lambda x: int(x), input().split())
    all_weights.append(w)
    all_values.append(v)
    

def max_value(i_item, remaining_weight):
    if i_item == n - 1:
        return 0 if all_values[i_item] < remaining_weight else all_values[i_item]
            
    return max(all_weights[i_item] + max_value(i_item+1, remaining_weight - all_weights[i_item]),
        max_value(i_item+1, remaining_weight))

print(max_value(0, sum_w))

Submission status: Wrong Answer

Solution code:
n, sum_w = map(lambda x: int(x), input().split())

# goods = list[]
all_weights = []
all_values = []
for _ in range(n):  
    w, v = map(lambda x: int(x), input().split())
    all_weights.append(w)
    all_values.append(v)
    

def max_value(i_item, remaining_weight):
    if i_item == n - 1:
        return 0 if all_values[i_item] < remaining_weight else all_values[i_item]
            
    return max(all_weights[i_item] + max_value(i_item+1, remaining_weight - all_weights[i_item]),
        max_value(i_item+1, remaining_weight))

max_value(0, sum_w)

Submission status: Wrong Answer

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

for i in range(n):
    temp_w,temp_v=map(int,input().split())
    w.append(temp_w)
    v.append(temp_v)
    

dp=[[0]*(W+1) for _ in range(n+1)]

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

Submission status: Wrong Answer

Solution code:
def getval():
    n,w = map(int,input().split())
    p = [list(map(int,input().split())) for i in range(n)]
    return n,w,p 

def main(n,w,p):
    #DP[n][w] 
    dp = [[0 for i in range(w+1)]]
    for i in range(n):
        item = p[i]
        temp = []
        for j in range(w+1):
            cur = dp[i][j]
            if j>=item[0]:
                cur = max(cur,dp[i][j-item[0]]+item[1])
            temp.append(cur)
        dp.append(temp)
    print(dp[n][w])
                
if __name__=="__main__":
    n,w,p = getval()

Submission status: Wrong Answer

Solution code:
import numpy as np

n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = np.zeros((n, w + 1), dtype=np.int32)

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(np.max(dp[n - 1]))

Submission status: Wrong Answer

Solution code:
import numpy as np
INF = 2**60
N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = np.full((N+1, W+1), -INF, dtype = np.int64)
dp[0][0] = 0 # 初期条件
for i, (w, v) in enumerate(wv):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i+1][w:], dp[i][:-w] + v)
print(np.max(dp[N][:W]))

Submission status: Wrong Answer

Solution code:
import numpy as np
INF = 2**60
N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = np.full((N+1, W+1), -INF, dtype = np.int)
dp[0][0] = 0 # 初期条件
for i, (w, v) in enumerate(wv):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i+1][w:], dp[i][:-w] + v)
print(np.max(dp[N][:W]))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = np.zeros((N+1, W+1))
for i, (w, v) in enumerate(wv):
    for j in range(W+1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j-w >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w] + v)
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
wait = [""]*n
value = [""]*n
for i in range(n):
    wait[i],value[i] = map(int,input().split())
print(wait,value)

# dp[i][j]=(i番目までの品物を、重さがj以下になるように選んだときの価値の最大値)を考える
# dp[i][j]は、
# i番目の品物を使うとき      i−1番目までで重さが(j − w[i])以下の価値の最大値 + v[i]
#              使わないとき  i−1番目までの重さがj以下の価値の最大値

knapsak = [0]*(n+1)
for i in range(n+1):
    knapsak[i] = [0]*(w+1)

for i in range(1,n+1):
    for j in range(0,w+1):
        # print(j-wait[i-1])
        if(j-wait[i-1]>= 0):
            knapsak[i][j] = max(knapsak[i-1][j],knapsak[i-1][j-wait[i-1]]+value[i-1])
            # print(knapsak)
        else:
            knapsak[i][j] = knapsak[i-1][j]
print(knapsak[n][w])

Submission status: Wrong Answer

Solution code:
import math
n,W=map(int,input().split())
dp=[[0]*(W+1) for i in range(n+1)]
w=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

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

Submission status: Wrong Answer

Solution code:
x, y = map(int, input().split())
dp = [[0]*(y+1) for _ in range(x+1)]

for i in range(1, x+1):
    w, v = map(int, input().split())
    for j in range(w, y+1):
        num0 = dp[i-1][j]
        num1 = dp[i-1][j-w]+v
        if num1 > num0:
            dp[i][j] = num1
        else:
            dp[i][j] = num0
print(max(dp[-1]))

Submission status: Wrong Answer

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

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

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

print(max(dp[-1]))

Submission status: Wrong Answer

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

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

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

print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
def inpl(): return list(map(int,input().split()))
 
N, W = inpl()
dp = [[0]*W for _ in range(N+1)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
def knapsack(N,W,w,v):
    dp = [[0]*(W+1) for _ in range(N)]
    
    for i in range(N):
        for j in range(W+1):
            if j-w[i]>0:
                dp[i][j] = max(dp[i-1][j],v[i]+ dp[i-1][j-w[i]])
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[N-1][W]

N,W = map(int,input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int,input().split())

print(knapsack(N,W,w,v))

Submission status: Wrong Answer

Solution code:
#knapsack 문제
#가장 중요한 부분은 이 물건을 넣을꺼냐 멀꺼냐 transition



def solve(ar_w,ar_v,n,w):
    dp = [[0] * (w+1) for _ in range(n+1)]

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


    print(dp[n][w])


if __name__ == '__main__':
    n,w = map(int,input().split())
    ar_w = [0]
    ar_v = [0]
    for i in range(n):
        a,b = map(int,input().split())
        ar_w.append(a)
        ar_v.append(b)

    solve(ar_w,ar_v,n,w)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]

# dp = [[0] * (W + 1) for _ in range(N + 1)]
dp = np.zeros((N + 1, W + 1), dtype=int)

for i in range(1, N + 1):
    dp[i] = dp[i - 1]
    dp[i, wv[i - 1][0]: W + 1] = dp[i - 1, 0: W + 1 - wv[i - 1][0]] + wv[i - 1][1]

print(np.max(dp))

Submission status: Wrong Answer

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

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

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

m = 0
for i in range(N + 1):
    m = max(m, max(dp[i]))

print(m)

Submission status: Wrong Answer

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

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

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

print(max(max(dp)))

Submission status: Wrong Answer

Solution code:
N, W = [int(x) for x in input().split()]

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

for i in range(W + 1):
    if i >= w:
        dp[0][i] = v

for i in range(1, N):
    w, v = [int(x) for x in input().split()]
    for j in range(W + 1):
        if j >= w:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        else:
            dp[i][j] = dp[i - 1][j]

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

ans = dp[N - 1][W]

print(ans)

Submission status: Wrong Answer

Solution code:
N, W = [int(x) for x in input().split()]

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

for i in range(W + 1):
    if i > w:
        dp[0][i] = v

for i in range(1, N):
    w, v = [int(x) for x in input().split()]
    for j in range(W + 1):
        if j >= w:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        else:
            dp[i][j] = dp[i - 1][j]

ans = dp[N - 1][W]

print(ans)

Submission status: Wrong Answer

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

s=[tuple(map(int,input().split())) for _ in range(n)]

s.sort()

ans=[s[0]]

for i in range(1,n):
    q=-111
    Max=-100
    for j in range(i):
        if s[i][0]+ans[j][0]<=W and s[i][1]+ans[j][1]>Max :
            q=j
            Max=s[i][1]+ans[j][1]
    ans.append((s[i][0]+ans[q][0],s[i][1]+ans[q][1]))

print(max(ans,key= lambda x : x[1])[1])

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
import numpy as np
dp = np.zeros(W, dtype=int)
for i in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp.max())

Submission status: Wrong Answer

Solution code:
import numpy as np

N, W = map(int, input().split())
dp = np.zeros(W+1)
for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)
    print(dp)

print(int(dp.max()))

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
dp=[0]*(W+1)
for _ in range(n):
	w,v=map(int,input().split())
	for j in range(W-w+1):
		dp[j+w]=max(dp[j+w],dp[j]+v)
print(dp[W])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
dd=defaultdict(lambda:0)
for _ in range(n):
	w,v=map(int,input().split())
	r=v/w
	li.append(r)
	dd[r]=(w,v)
li=sorted(li)[::-1]
tw=0
tv=0
for i in li:
	w,v=dd[i]
	if tw+w<=W:
		tw+=w
		tv+=v
print(tv)

Submission status: Wrong Answer

Solution code:
a = [int(v) for v in input().split()]
l = []
d = []
e = []
for i in range(0, a[0]):
    d = [int(v) for v in input().split()]
    l.append(d)
d = []
for i in range(0, len(l)):
    d.append(l[i][0])
for i in range(0, len(l)):
    e.append(l[i][1])
s = 0
w = 0
m = []
k = 0
for i in range(0,a[0]):
    m.append([])
    for j in range(0,a[1]):
        m[i].append(0)

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


for j in range(0, len(m[i])):
    if d[0] <= j:
        m[0][j] = e[0]
        
for i in range(1, len(m)):
    for j in range(0, len(m[i])):
        if d[i] > j:
            m[i][j] = m[i-1][j]   
        else:
            m[i][j] = timmax(m[i-1][j], m[i-1][j-d[i]]+e[i])
print(m[len(m) - 1][len(m[0]) - 1])

Submission status: Wrong Answer

Solution code:
a = [int(v) for v in input().split()]
l = []
d = []
e = []
for i in range(0, a[0]):
    d = [int(v) for v in input().split()]
    l.append(d)
d = []
for i in range(0, len(l)):
    d.append(l[i][0])
for i in range(0, len(l)):
    e.append(l[i][1])
s = 0
w = 0
f = 0
for i in range(0, len(e)):
    s += e[i]
for i in range(0, len(d)):
    w += d[i]
while w > a[1]:
    f = e.index(min(e))
    w -= d[f]
    s -= e[f]
    d.remove(d[f])
    e.remove(e[f])
print(s)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)

n, w = map(int, input().split())
weights, values = [], []

for _ in range(n):
    wi, vi = map(int, input().split())
    
    weights.append(wi)
    values.append(vi)  

@lru_cache(maxsize=1024)
def f(w, n):
    # if (w, n) in cache:
        # return cache[(w, n)]
    
    if w == 0 or n == 0:
        # cache[(w, n)] = 0
        return 0
    
    if w < weights[n-1]:
        return f(w, n-1)

    
    return max(f(w, n-1), f(w-weights[n-1], n-1) + values[n-1])

print(f.cache_info())
print(f(w, len(weights)))

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
dp = [0] * (W+1)

for i in range(N):
    tmp_w = w[i]
    tmp_v = v[i]
    for j in range(W):
        if dp[j] != 0:
            if j + tmp_w <= W:
                if dp[j + w[i]] < v[i]:
                    dp[j + w[i]] = dp[j] + v[i]
    if dp[w[i]] < v[i]:
        dp[w[i]] = v[i]
print(max(dp))

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
dp = [0] * (W+1)

for i in range(N):
    tmp_w = w[i]
    tmp_v = v[i]
    for j in range(W):
        if dp[j] != 0:
            if j + tmp_w <= W:
                if dp[j + tmp_w] < tmp_v:
                    dp[j + tmp_w] = dp[j] + tmp_v
    if dp[tmp_w] < tmp_v:
        dp[tmp_w] = tmp_v
print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    w = [0] * N
    v = [0] * N
    for i in range(N):
        w[i], v[i] = map(int, input().split())

    dp = np.zeros(shape=(N + 1, W + 1), dtype=np.int64)
    for i, (w_, v_) in enumerate(zip(w, v)):
        dp[i + 1, w_:] = np.maximum(dp[i, w_:], dp[i, :W + 1 - w_] + v_)

    ans = np.max(dp[-1])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
N, W = map(int, input().split())
w = []
v = []
for i in range(N):
    tmp_w,tmp_v = map(int,input().split())
    w.append(tmp_w)
    v.append(tmp_v)

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] = dp[i][j-w[i]] + v[i]
print(dp[N][W])

Submission status: Wrong Answer

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

dp = [[0]*(W+1) for j in range(N+1)] # DPテーブルの作成

for i in range(N):
    for j in range(W+1):
        if j < w[i]: # 選ばない時
            dp[i+1][j] = max(dp[i][j], dp[i+1][j] )
        else: # 選ぶ時
            dp[i+1][j] = max(dp[i+1][j],dp[i][j-w[i]]+v[i])

print(dp[N][W])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
wt,p=[],[] 
cache=[[-1]*101 for i in range(100001)]

def knapsack(W,n):
  if n==0 or W==0 :
    return 0
  elif cache[W][n] != -1:
    return cache[W][n]
  
  else:
    if wt[n-1]<=W:
      cache[W][n]=max(knapsack(W,n-1),p[n-1]+knapsack(W-wt[n-1],n-1))
      
    else:
      cache[W][n]=knapsack(W,n-1)
    
    return cache[W][n]

  
n,w=map(int,input().split())

for _ in range(n):
  temp_wt,temp_pr=map(int,input().split())
  wt.append(temp_wt)
  p.append(temp_pr)
print(1)
# print(knapsack(w,n))

Submission status: Wrong Answer

Solution code:
n, W = map(int,input().split())
items = [[0,0] for _ in range(n+1)]
for i in range(n):
    items[i+1] = list(map(int, input().split()))

dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    weight, value = items[i][0], items[i][1]
    for w_limit in range(1,W+1):
        if w_limit - weight >= 0:
            dp[i][w_limit] = max(dp[i-1][w_limit], dp[i-1][w_limit-weight] + value)
print(dp[n][W])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,W = IL()
data = ILL(N)

dp = [[0 for w in range(W+1)] for i in range(N+1)]

for i in range(N):
  w0,v0 = data[i]
  for w in range(W):
    if w+w0 <= W:
      dp[i+1][w+w0] = max(dp[i][w+w0],dp[i][w]+v0)

print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for wsum in range(1,w+1):
  	#print("i={}".format(i))    
    for i in range(n):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i+1][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
      else:
        dp[i+1][wsum] = dp[i][wsum]
  print(np.max(dp))

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]
#print(wl)
#print(vl)
Knapsack1(n,w,wl,vl)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for i in range(n):
  	#print("i={}".format(i))    
    for wsum in range(1,w+1):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i+1][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
      else:
        dp[i+1][wsum] = dp[i][wsum]
  print(np.max(dp))

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]

Knapsack1(n,w,wl,vl)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for i in range(n):
  	#print("i={}".format(i))    
    for wsum in range(1,w+1):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i+1][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
      else:
        dp[i+1][wsum] = dp[i][wsum]
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]
#print(wl)
#print(vl)
Knapsack1(n,w,wl,vl)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for i in range(n):
  	#print("i={}".format(i))    
    for wsum in range(1,w+1):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i+1][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
      else:
        dp[i+1][wsum] = dp[i][wsum]
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:x[1])
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]

Knapsack1(n,w,wl,vl)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(N)]
item.sort(key=lambda x: x[1])
ans = 0
total_weight = 0

for i in range(N):
    while item:
        weight, value = item.pop()
        if weight <= W - total_weight:
            ans += value
            total_weight += weight
            break
    if not item:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
import numpy as np
n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]

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


for i in range(n):
      #print("重さ：{}".format(wsum))
  for wsum in range(1,w+1):
    #print("i={}".format(i))
    if wsum >= wv[i][0]:
        #print("選ぶ, (重さ：{}, 価値：{})".format(wl[i], vl[i]))
        dp[i][wsum] = max(dp[i-1][wsum], dp[i-1][wsum-wv[i][0]]+wv[i][1])
    else:
      dp[i+1][wsum] = dp[i][wsum]
    #pprint(dp)

dp=np.array(dp)
print(np.max(dp))

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l =  sorted(l, reverse=True, key=lambda x: x[1])

tmp_w = 0
tmp_v = 0

for e in l:
    if tmp_w + e[0] > w:
        continue
    else:
        tmp_w += e[0]
        tmp_v += e[1]

print(tmp_v)

Submission status: Wrong Answer

Solution code:
n,w=[int(i) for i in input().split()]
wi=[]
val=[]
for i in range(n):
    k=[int(i) for i in input().split()]
    wi.append(k[0])
    val.append(k[1])
dp=[[-1]*10**5]*105
def solve(pos,we):
    if we>w:
        return float("-inf")
    if pos>=n:
        return 0
    if dp[pos][we]!=-1:
        return dp[pos][we]
    ans=max(solve(pos+1,we+wi[pos])+val[pos],solve(pos+1,we))
    dp[pos][we]=ans
    return ans
print(solve(0,0))

Submission status: Wrong Answer

Solution code:
n,w=[int(i) for i in input().split()]
wi=[]
val=[]
for i in range(n):
    k=[int(i) for i in input().split()]
    wi.append(k[0])
    val.append(k[1])
dp=[[-1]*10**5]*105
print(wi,val)
def solve(pos,we):
    if we>w:
        return float("-inf")
    if pos>=n:
        return 0
    if dp[pos][we]!=-1:
        return dp[pos][we]
    ans=max(solve(pos+1,we+wi[pos])+val[pos],solve(pos+1,we))
    dp[pos][we]=ans
    return ans
print(solve(0,0))

Submission status: Wrong Answer

Solution code:
N, W = map(int,input().split())
dp = [0]*-~W
for _ in [None]*N:
  w, v = map(int,input().split())
  for j in range(w, -~W):
    dp[j] = max(dp[j], dp[j - w] + v)
print(max(dp))

Submission status: Wrong Answer

Solution code:
(N, W), *D = [list(map(int, o.split())) for o in open(0)]
w, v = 0, 1
dp = [[0]*-~W for _ in [0]*-~N]
for i in range(N):
  for j in range(W + 1):
    dp[i + 1][j] = dp[i][j] if j < D[i][w] else dp[i][j - D[i][w]] + D[i][v]
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, W = map(int, input().split())
    dp = [[0] * (N + 1) for _ in range(W + 1)]
    for i in range(1, N + 1):
        w, v = map(int, input().split())
        for j in range(w,W + 1):
            dp[j][i] = max(dp[j][i - 1], dp[j - w][i-1] + v)

    print(dp[W][N])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
wt=[]
value=[]
for i in range(n):
    x,y=map(int,input().split())
    value.append(x)
    wt.append(y)
dp = [0] * (W + 1)
for i in range(n):
    for j in range(W, wt[i], -1):
        dp[j] = max(dp[j], value[i] + dp[j - wt[i]]);
print(dp[W])

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w, v = zip(*(map(int, input().split()) for _ in range(N)))

dp = [0] * (W+1)

for i in range(N):
    for j in range(W,0,-1):
        if j - w[i] >= 0:
            dp[j] = dp[j - w[i]] + v[i] #jは重さ、w[i]も重さ、dp[j]は重さjの時の価値、v[i]は重さw[i]の時の価値
    if dp[w[i]] == 0 or dp[w[i]] < v[i]:
        dp[w[i]] = v[i]
print(max(dp))