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, 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番目までで、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][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)

Submission status: Wrong Answer

Solution code:
N,W=[int(i) for i in input().split()]
w=[]
v=[]
for i in range(N):
    a,b=[int(i) for i in input().split()]
    w.append(a)
    v.append(b)
dic={}
for i in range(N):
    dic[v[i]]=w[i]
v.sort()
val=0
wei=0
i=N-1
while wei<W:
    if wei+dic[v[i]]<=W:
        wei+=dic[v[i]]
        val+=v[i]
        i-=1
    else:
        break
print(val)

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 i in range(N+1)]
for i in range(1,N+1):
    for w in range(W+1):
        if w-wv[i-1][0]>=0:
            dp[i][w] = max(dp[i-1][w-wv[i-1][0]]+wv[i-1][1],dp[i][w])
        else:
            dp[i][w] = dp[i-1][w]
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
mod=10**9+7  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max((li[a-1][1]+dp[a-1][b-li[a-1][0]]),dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v]%mod)

Submission status: Wrong Answer

Solution code:
import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(3)]
	w_v_list = [read() for i in range(n)]
	# for i in dp:print(*i)
	# print("\n")
	# print(w_v_list)
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i%3][j] = max(elem_v + dp[(i-1)%3][j - elem_w], dp[i%3][j-1], dp[(i-1)%3][j])
				# w_v_list[i][1] = 0
			else:
				dp[i%3][j] = max(dp[i%3][j-1], dp[(i-1)%3][j])
	# for i in dp:print(*i)
	print(dp[(n-1)%3][w])




if __name__ == "__main__":
	solve()

Submission status: Wrong Answer

Solution code:
import sys

N,W = list(map(int,input().split()))
data = []
for i in range(N):
  a = list(map(int,input().split()))
  data.append(a)

def knapsack1(n,w,d):
  note =  [[-1 for _ in range(w+1)] for _ in range(n+1)]
  note[0] = [0]*(w+1) #note[0]の⾏を0で初期化

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
ans = 0
n, w = map(int, input().split())
lst = [[0,0]]
for _ in range(n):
    a, b = map(int, input().split())
    lst.append([a,b])
dp = [[0] * (w+1) for _ in range(n+1)]

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

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
dp_pv = [0]*(W+1)

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(1,(N+1)):
    w, v = map(int, input().split())
    for j in range(1,W+1):

        if j-w<0:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        else:
            dp[i][j] = max(dp[i-1][j-w]+v,dp[i][j-1])

print(max(max(dp)))

Submission status: Wrong Answer

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
 
dp = [[float('inf')]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0
 
for i in range(1, N+1):
  w, v = map(int, input().split())
  for j in range(10**5+1):
    dp[i][j] = dp[i-1][j]
    if j >= v:
      dp[i][j] = min(dp[i][j], dp[i-1][j-v]+w)
 
ans = 0
for j in range(10**5+1):
  if dp[N][j] <= W:
    ans = max(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())
dp = np.zeros((N, W+1), dtype = "int64")
for i in range(N):
    w, v = map(int, input().split())
    dp[i,-w:] = dp[i-1, -w:] #残りの重さW-w以上にするためには、荷物を入れられない。
    dp[i, :W-w+1] = np.fmax(dp[i-1, :W-w+1], dp[i-1, w:]+v)
dp[N-1, 0]

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w = []
v = []
for n in range(N):
    w1, v1 = map(int, input().split())
    w.append(w1)
    v.append(v1)

memo = [[0 for i in range(W+1)] for j  in range(N+1)]
def into(num, weight):
    if num >= N:
        return 0
    if weight < w[num]:
        return 0
    if memo[num][weight] != 0:
        return memo[num][weight]
    c= max( into(num+1, weight-w[num])+v[num], into(num+1, weight) )
    memo[num][weight] = c
    return c
print(into(0, W))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w = []
v = []
for n in range(N):
    w1, v1 = map(int, input().split())
    w.append(w1)
    v.append(v1)
memo = [0 for i in range(W+1)] 
def into(num, weight):
    if num >= N:
        return 0
    if weight < w[num]:
        return 0
    if memo[weight] != 0:
        return memo[weight]
    c= max( into(num+1, weight-w[num])+v[num], into(num+1, weight) )
    memo[weight] = c
    return c
print(into(0, W))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N, W = MI()
inp = LI2(N)
w = [inp[i][0] for i in range(N)]
v = [inp[i][1] for i in range(N)]
dp = FILL2(0,N+1,W+1)
for i in range(N):
    for j in range(W+1):
        if j+w[i]<=W:
            dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]],dp[i][j]+v[i])
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(max(dp[N]))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[[0 for e in range(W+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for k in range(0,w):
  ans[i+1][k]=ans[i][k]
 for j in range(w,W+1):
  ans[i+1][j]=max(ans[i][j-w]+v,ans[i][j])
print(max(ans[N]))
print(ans[N])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N,Max_W = map(int,input().split())
 
dp = [0 for _ in range(Max_W + 1)]
dp = np.array(dp)
 
for i in range(N):
    w,v = map(int,input().split())
    a = dp[:-w] + v
    b = dp[w:]
    m = np.maximum(a,b)
    dp[w:] = m

Submission status: Wrong Answer

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

Ws = []
Vs = []

for _ in range(N):
  w, v = map(int, input().split())
  Ws.append(w)
  Vs.append(v)


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

if Ws[0] < W:
  for i in range(Ws[0], W+1):
    S[0][i] = Vs[0]

for weight in range(W+1):
  for item_num in range(N-1):
    if weight - Ws[item_num+1] < 0:
      S[item_num+1][weight] = max(S[item_num+1][weight], S[item_num][weight])
    else:
      S[item_num+1][weight] = max(S[item_num+1][weight], S[item_num][weight-Ws[item_num+1]] + Vs[item_num+1], S[item_num][weight])

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

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
WV=[]
for i in range(N):
    WV.append(list(map(int,input().split())))
dp=[[0 for j in range(W+1)] for i in range(N+1)]
dp[0]=[-1e-30 for i in range(W+1)]
dp[0][0]=0
dp[0][WV[0][0]]=WV[0][1]
for i in range(1,N+1):
    for j in range(W+1):
        if j-WV[i-1][0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-WV[i-1][0]]+WV[i-1][1])
        else:
            dp[i][j]=dp[i-1][j]
print(int(dp[N][W]))

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
WV=[]
for i in range(N):
    WV.append(list(map(int,input().split())))
dp=[[-1e-30 for j in range(W+1)] for i in range(N)]
dp[0][0]=0
dp[0][WV[0][0]]=WV[0][1]
for i in range(1,N):
    for j in range(W+1):
        if j-WV[i][0]>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-WV[i][0]]+WV[i][1])
        else:
            dp[i][j]=dp[i-1][j]
print(int(dp[N-1][W]))

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
l=[]
for i in range(n):
    w1,v1=map(int,input().split())
    l.append([v1,w1])
s=0
a=sorted(l,reverse=True)
for i in range(n):
    if w-a[i][1]>=0:
        w-=a[i][1]
        s+=a[i][0]
print(s)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
dp=[[0]*(w+1) for i in range(n)]
wet=[]
val=[]
for i in range(n):
  we,va=map(int,input().split())
  wet.append(we)
  val.append(va)
for i in range(w+1):
  if(wet[0]==i):
    dp[0][i]=val[0]
  elif(wet[0]<i):
    break
for i in range(1,n):
  for j in range(w+1):
    dp[i][j]=dp[i-1][j]
    if(wet[i]<=j):
      dp[i][j]=max(dp[i][j],dp[i-1][j-wet[i]]+val[i])
print(dp[n-1][w])

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
index_point={}
w_v=[]
for i in range(n):
  line=list(map(int,input().split()))
  tmp_point=line[1]/line[0]
  index_point[i]=tmp_point
  w_v.append(line)

weight_value_point=[]
sorted_list=sorted(index_point.values(),reverse=True)
for i in sorted_list:
  for key,value in index_point.items():
    if i == value:
      weight_value_point.append(w_v[key])
      break
#print(weight_value_point)
max_value=0
for i in range(len(weight_value_point)):
  if weight_value_point[i][0]>w:
    continue
  tmp_value=weight_value_point[i][1]
  tmp_weight=weight_value_point[i][0]
  for j in range(len(weight_value_point)):
    if i==j:
      continue
    elif weight_value_point[j][0]+tmp_weight>w:
      continue
    else:
      tmp_weight+=weight_value_point[j][0]
      tmp_value+=weight_value_point[j][1]
  max_value=max(max_value,tmp_value)
for i in range(len(weight_value_point)):
  if weight_value_point[i][0]>w:
    continue
  tmp_value=weight_value_point[i][1]
  tmp_weight=weight_value_point[i][0]
  for j in range(i,len(weight_value_point)):
    if i==j:
      continue
    elif weight_value_point[j][0]+tmp_weight>w:
      continue
    else:
      tmp_weight+=weight_value_point[j][0]
      tmp_value+=weight_value_point[j][1]
  max_value=max(max_value,tmp_value)
print(max_value)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
index_point={}
w_v=[]
for i in range(n):
  line=list(map(int,input().split()))
  tmp_point=line[1]/line[0]
  index_point[i]=tmp_point
  w_v.append(line)

weight_value_point=[]
sorted_list=sorted(index_point.values(),reverse=True)
for i in sorted_list:
  for key,value in index_point.items():
    if i == value:
      weight_value_point.append(w_v[key])
      break
#print(weight_value_point)
max_value=0
for i in range(len(weight_value_point)):
  if weight_value_point[i][0]>w:
    continue
  tmp_value=weight_value_point[i][1]
  tmp_weight=weight_value_point[i][0]
  for j in range(i,len(weight_value_point)):
    if i==j:
      continue
    elif weight_value_point[j][0]+tmp_weight>w:
      continue
    else:
      tmp_weight+=weight_value_point[j][0]
      tmp_value+=weight_value_point[j][1]
  max_value=max(max_value,tmp_value)
print(max_value)

Submission status: Wrong Answer

Solution code:
n,wt=map(int,input().split())
v=[0]*n
w=[0]*n
for i in range(n):
    a,b=map(int,input().split())
    w[i]=a
    v[i]=b
def knp(wt,v,w,n):
    if(n==0 or wt==0):
        return 0
    
    if(w[n-1]>wt):
        return knp(wt,v,w,n-1)
    else:
        return v[n-1]+knp(wt-w[n-1],v,w,n-1)  
print(knp(wt,v,w,n))

Submission status: Wrong Answer

Solution code:
# D Knapsack 1
import copy

n, w = map(int, input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)] # n*2

dp = [float('-Inf')] * (w+2)
dp[0] = 0
buy_list = [[False] * n for j in range(w+2)] # (w+2)*n

for i in range(w):
    for j in range(n):
        if buy_list[i][j]:
            continue
        _w = wv_list[j][0]
        _v = wv_list[j][1]
        if i+_w > w:
            _w = w - i + 1
        if dp[i+_w] < dp[i]+_v:
            dp[i+_w] = dp[i]+_v
            buy_list[i+_w] = copy.deepcopy(buy_list[i])
            buy_list[i+_w][j] = True
            
print(max(dp[:w]))

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
index_point={}
w_v=[]
for i in range(n):
  line=list(map(int,input().split()))
  tmp_point=line[1]/line[0]
  index_point[i]=tmp_point
  w_v.append(line)

weight_value_point=[]
sorted_list=sorted(index_point.values(),reverse=True)
for i in sorted_list:
  for key,value in index_point.items():
    if i == value:
      weight_value_point.append(w_v[key])
      break
#print(weight_value_point)
max_value=0
for i in range(len(weight_value_point)):
  if weight_value_point[i][0]>w:
    continue
  tmp_value=weight_value_point[i][1]
  tmp_weight=weight_value_point[i][0]
  for j in range(len(weight_value_point)):
    if i==j:
      continue
    elif weight_value_point[j][0]+tmp_weight>w:
      continue
    else:
      tmp_weight+=weight_value_point[j][0]
      tmp_value+=weight_value_point[j][1]
  max_value=max(max_value,tmp_value)
print(max_value)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
index_point={}
w_v=[]
for i in range(n):
  line=list(map(int,input().split()))
  tmp_point=line[1]/line[0]
  index_point[i]=tmp_point
  w_v.append(line)

weight_value_point=[]
sorted_list=sorted(index_point.values(),reverse=True)
for i in sorted_list:
  for key,value in index_point.items():
    if i == value:
      weight_value_point.append(w_v[key])
      break
#print(weight_value_point)
max_value=0
for i in range(len(weight_value_point)):
  tmp_value=weight_value_point[i][1]
  tmp_weight=weight_value_point[i][0]
  if tmp_weight>w:
    continue
  for j in range(len(weight_value_point)):
    if i==j:
      continue
    elif weight_value_point[j][0]+tmp_weight>w:
      continue
    else:
      tmp_weight+=weight_value_point[j][0]
      tmp_value+=weight_value_point[j][1]
  max_value=max(max_value,tmp_value)
print(max_value)

Submission status: Wrong Answer

Solution code:
n,W = map(int,input().split())
wv = []
for _ in range(n):
    weight,value = map(int,input().split())
    wv.append((weight,value))
dp = [[0] * (W+1) for _ in range(n+1)] #dp[i+1][weight]:品物0,1,2,,,iの中から重さweight以下になるように荷物を選んだ時の価値の最大値

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

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] >= 0:
      dp[i+1][j] = max(dp[i+1][j], dp[i][j-wv[i][0]] + wv[i][1])
    else:
      dp[i+1][j] = max(dp[i+1][j], dp[i][j])
 
ans = 0
 
for k in range(N+1):
  ans = max(ans, max(dp[k]))
 
print(ans)

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)]
dp[0][W] = 0

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

ans = 0

for k in range(N+1):
  ans = max(ans, max(dp[k]))

print(ans)

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)]
dp[0][W] = 0

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

ans = 0

for k in range(N):
  ans = max(ans, max(dp[k]))
  
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, w = list(map(int, input().split()))
wv = np.array([list(map(int, input().split(' '))) for _ in range(n)])

dp = np.zeros((w + 1, n))
dp[wv[0, 0]:, 0] = np.full(dp[wv[0, 0]:, 0].shape, wv[0, 1])
for i in range(1, n):
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i, 0], wv[i, 1]
    dp[wNew:, :] = np.fmax(dp[wNew:, :], vNew + dp[:-wNew, :])

print(dp[w, n - 1])

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().strip().split())
 
values = []
weights = []
 
for _ in range(N):
    w, v = map(int, input().strip().split())
    weights.append(w)
    values.append(v)
    
dp = [0]*(W+1)
for i in range(N):
    for w in range(W, weights[i] - 1, -1):
        dp[w] = max(dp[w], values[i] + dp[w - weights[i]])

Submission status: Wrong Answer

Solution code:
import numpy as np

#  入力
n, w = map(int, input().split())
wv = np.array([list(map(int, input().split())) for i in range(n)])


dp = np.zeros((w + 1, n + 1))
for i in range(1, n + 1):

    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i - 1, 0], wv[i - 1, 1]
    dp[wNew:, :] = np.fmax(dp[wNew:, :], vNew + dp[:-wNew, :])

print(dp[w, n])

Submission status: Wrong Answer

Solution code:
import numpy as np
 
 
def main():
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.zeros((N, W + 1))
    dp[0, items[0, 0]:] = items[0, 1]
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, weight:] = np.fmax(
            dp[n, weight:],
            value + dp[n - 1, :(- weight)]
        )
    print(int(dp[N - 1, W]))

Submission status: Wrong Answer

Solution code:
import numpy as np

#  入力
n, w = map(int, input().split())
wvList = []
wv = np.array([list(map(int, input().split())) for i in range(n)])

#  考えるDPテーブルは
#  重さの総和と使う荷物に関するもの
#  行が重さの上限
#  列が使える荷物の数に相当
dp = np.zeros((w + 1, n + 1), dtype=np.int)
for i in range(1, n + 1):
    #  更新の発想(wに意味はない)
    #  使える荷物が増えたが，利用はしない
    #  dp[w, i] = dp[w, i - 1]
    #  荷物を新しく許可された荷物を使う
    #  dp[w, i] = dp[w - wNew, i-1] + newValue
    #  このうちの価値の大きい方を使う
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i - 1, 0], wv[i - 1, 1]
    dp[wNew:, :] = np.fmax(dp[wNew:, :], vNew + dp[:-w, :])

print(dp[w, n])

Submission status: Wrong Answer

Solution code:
import numpy as np

#  入力
n, w = map(int, input().split())
wvList = []
wv = np.array([list(map(int, input().split())) for i in range(n)])

#  考えるDPテーブルは
#  重さの総和と使う荷物に関するもの
#  行が重さの上限
#  列が使える荷物の数に相当
dp = np.zeros((w + 1, n + 1), dtype=np.int)
for i in range(1, n + 1):
    #  更新の発想(wに意味はない)
    #  使える荷物が増えたが，利用はしない
    #  dp[w, i] = dp[w, i - 1]
    #  荷物を新しく許可された荷物を使う
    #  dp[w, i] = dp[w - wNew, i-1] + newValue
    #  このうちの価値の大きい方を使う
    dp[:, i] = dp[:, i - 1]
    w, v = wv[i - 1, 0], wv[i - 1, 1]
    dp[w:, :] = np.fmax(dp[w:, :], v + dp[:-w, :])

print(dp[w, n])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(900000000)
def knap(n,w,weight,value,dp):
    #print(n,":",w,":",len(dp),":",len(dp[n]))
    x=dp[n][w]
    if x!=-1:
        return x
    if n==0:
      #  dp[n][w]=0
        return 0
    if w==0:
       # dp[n][w]=0
        return 0
    if w-weight[n-1]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n-1],weight,value,dp)+value[n-1]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>=tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2  
def main():
    n,W=map(int,input().split())
    weight=[]
    value=[]
    for i in range(n):
        a,b=map(int,input().split())
        weight.append(a)
        value.append(b)
    dp=[[-1]*(W+1)]*(n+1)
    print(knap(n,W,weight,value,dp))
    return 0
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(900000000)
def knap(n,w,weight,value,dp):
    #print(n,":",w,":",len(dp),":",len(dp[n]))
    x=dp[n][w]
    if x!=-1:
        return x
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n-1]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n-1],weight,value,dp)+value[n-1]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>=tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2  
def main():
    n,W=map(int,input().split())
    weight=[]
    value=[]
    for i in range(n):
        a,b=map(int,input().split())
        weight.append(a)
        value.append(b)
    dp=[[-1]*(W+1)]*(n+1)
    print(knap(n,W,weight,value,dp))
    return 0
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(900000000)
def knap(n,w,weight,value,dp):
    #print(n,":",w,":",len(dp),":",len(dp[n]))
    x=dp[n][w]
    if x!=-1:
        return x
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>=tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2  
def main():
    n,W=map(int,input().split())
    weight=[0]
    value=[0]
    for i in range(n):
        a,b=map(int,input().split())
        weight.append(a)
        value.append(b)
    dp=[[-1]*(W+1)]*(n+1)
    print(knap(n,W,weight,value,dp))
    return 0
main()

Submission status: Wrong Answer

Solution code:
#import sys
#sys.setrecursionlimit(40000000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Submission status: Wrong Answer

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

def knap(num,Wmax):
    #print(num,":",Wmax)
    if num==0:
      #  print("a")
        dp[Wmax][num]=0
        return 0
    if Wmax==0:
     #   print("b")
        dp[Wmax][num]=0
        return 0
    Wtmp=Wmax-w[num]
    #print(Wmax,"@",w[num])
    if Wtmp<1:
        #print("c")
        dp[Wmax][num]=knap(num-1,Wmax)
        return dp[Wmax][num-1]
    else:
       # print("d")
        tmp1=knap(num-1,Wtmp)+v[num]
        tmp2=knap(num-1,Wmax)
        dp[Wmax][num]=max(tmp1,tmp2)
        #print("add:",v[num])
        return dp[Wmax][num]

print(knap(n,W))
#print(dp)

Submission status: Wrong Answer

Solution code:
n,w = [int(x) for x in input().split(" ")]

dp = [0 for x in range(w+1)]
sf = [w]
ma = 0
for x in range(n):
    www,vvv = [int(x) for x in input().split(" ")]

    a =len(sf)
    for j in range(a):
        if sf[j]-www >= 0 and dp[sf[j]] + vvv > dp[sf[j]-www]:
            dp[sf[j]-www] = dp[sf[j]] + vvv
            sf.append(sf[j]-www)
            if dp[sf[j]] + vvv > ma:
                ma = dp[sf[j]] + vvv

print(ma)

Submission status: Wrong Answer

Solution code:
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[i][before_w] = max(dp_table[i][before_w], dp_table[i-1][before_w])
        #i番目の品物を選ぶ場合
        #if wv[i-1][0]+before_w <= w and dp_table[i-1][before_w] >= 0:
        #    dp_table[i][wv[i-1][0]+before_w] = max(dp_table[i][wv[i-1][0]+before_w], dp_table[i-1][before_w] + wv[i-1][1])
        #else:
        #    continue

result = 0

for y in range(w+1):
    tempresult = max(dp_table[n])
    result=max(result,tempresult)

print(result)

#pprint(dp_table)

Submission status: Wrong Answer

Solution code:
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        #dp_table[i][before_w] = max(dp_table[i][before_w], dp_table[i-1][before_w])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w and dp_table[i-1][before_w] >= 0:
            dp_table[i][wv[i-1][0]+before_w] = max(dp_table[i][wv[i-1][0]+before_w], dp_table[i-1][before_w] + wv[i-1][1])
        else:
            continue

result = 0

for y in range(w+1):
    tempresult = max(dp_table[n])
    result=max(result,tempresult)

print(result)

#pprint(dp_table)

Submission status: Wrong Answer

Solution code:
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[i][before_w] = max(dp_table[i][before_w], dp_table[i-1][before_w])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w and dp_table[i-1][before_w] >= 0:
            dp_table[i][wv[i-1][0]+before_w] = max(dp_table[i][wv[i-1][0]+before_w], dp_table[i-1][before_w] + wv[i-1][1])
        else:
            continue

result = 0

#for y in range(w+1):
#    tempresult = max(dp_table[n])
#    result=max(result,tempresult)
#
#print(result)

pprint(dp_table)

Submission status: Wrong Answer

Solution code:
from pprint import pprint

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

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


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[i][before_w] = max(dp_table[i][before_w], dp_table[i-1][before_w])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w and dp_table[i-1][before_w] >= 0:
            dp_table[i][wv[i-1][0]+before_w] = max(dp_table[i][wv[i-1][0]+before_w], dp_table[i-1][before_w] + wv[i-1][1])
        else:
            continue

result = 0

for y in range(w+1):
    tempresult = max(dp_table[n])
    result=max(result,tempresult)

print(result)

pprint(dp_table)