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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, w = map(int, input().strip().split())
  Ws, Vs = numpy.array([[int(x) for x in input().strip().split()] for _ in range(n)]).T
  dp = numpy.zeros((n, w+1), dtype=numpy.int)
  dp[0, Ws[0]] = Vs[0]
  for i in range(1, n):
    dp[i] = dp[i-1,:]
    if w - Ws[i] + 1 > 0:
      dp[i, Ws[i]:w+1] = numpy.maximum(dp[i-1, Ws[i]:w+1], dp[i-1,:w-Ws[i]+1]+Vs[i])
  print(dp[n-1, w])


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, w = map(int, input().strip().split())
  Ws, Vs = numpy.array([[int(x) for x in input().strip().split()] for _ in range(n)]).T
  dp = numpy.zeros((n, w+1), dtype=numpy.int)
  dp[0, Ws[0]] = Vs[0]
  for i in range(1, n):
    dp[i] = dp[i-1,:]
    if w - (Ws[i]-1) > 0:
      dp[i, Ws[i]:w+1] = numpy.maximum(dp[i-1, Ws[i]:w+1], dp[i-1,:w-(Ws[i])+1]+Vs[i])
  print(dp[n-1, w])


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
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())
    
inf=float("inf")
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    dp[i+1][0] = -inf

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

Submission status: Wrong Answer

Solution code:
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())
    
inf=float("inf")
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = -inf

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    w, v = B[i]
    for j in range(W+1):
        if j+w <= W:
            dp[i+1][j+w] = max(dp[i][j+w], dp[i][j]+v)
        else:
            continue
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
baglist = [0]*(m+1)
for i in range(n):
    weight, value = map(int, input().split())
    for j in range(m,-1,-1):
        if (baglist[j] or j == 0) and j+weight <= m:
            baglist[j+weight] = max([baglist[j+weight], baglist[j]+value])
    print(baglist)
print(max(baglist))

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    import sys
    input = sys.stdin.readline

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

    dp = np.zeros((n+1,w+1),dtype="int64")
    for i in range(n):
        dp[i+1,l[i][0]:] = np.maximum(dp[i,l[i][0]:],dp[i,-l[i][0]]+l[i][1])
    print(dp[n][w])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
(n, W) = map(int,input().split())
a = [[0] * (W+1) for i 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):
      a[i][j] = a[i-1][j]
    else:
      a[i][j] = max(a[i-1][j], a[i-1][j-w] + v)
print(a[n-1][W])

Submission status: Wrong Answer

Solution code:
n, w_lim = map(int, input().split())
wight, value = [0], [0]
for _ in range(n):
    w, v = map(int, input().split())
    wight.append(w)
    value.append(v)
print(wight, value)
dp = [[0] * (w_lim+1) for _ in range(n+1)]

for item in range(1, n+1):
    for sum_w in range(1, w_lim+1):
        if sum_w - wight[item] >= 0:
            dp[item][sum_w] = max(dp[item-1][sum_w], dp[item-1][sum_w-wight[item]] + value[item])
        else:
            dp[item][sum_w] = max(dp[item-1][sum_w], dp[item][sum_w])

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

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
values = [0 for i in range(W)]
for i in range(N):
  print(values)
  w, v = map(int, input().split())
#  values = values[:w-1] + [max(values[j], v + values[max(0, j-w)]) for j in range(w-1, W)]

print(values[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
import numpy as np

dp=np.zeros([n+1,W+1],dtype=np.int64)
print(dp)
for i in range(n):
  w=items[i][0]
  v=items[i][1]
  dp[i+1][:w]=dp[i][:w]
  dp[i+1][w:]=np.maximum(dp[i][w:],dp[i][:-w]+v)
print(dp[-1][-1])

Submission status: Wrong Answer

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

W = []
V = []

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

memo = [-1 for _ in range(N)]
def rec(i = 0, w = 0):
    # 荷物がない
    if i >= N:
        return 0
    # メモ
    if memo[i] != -1:
        return memo[i]
    # もう持てない
    if w + W[i] > WMAX:
        return rec(i+1, w)
    else:
        memo[i] = max(rec(i+1, w + W[i]) + V[i], rec(i+1, w))
        return memo[i]

print(rec())

Submission status: Wrong Answer

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

W = []
V = []

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

def rec(i = 0, w = 0):
    # 荷物がない
    if i >= N:
        return 0
    # もう持てない
    if w + W[i] > WMAX:
        return 0
    return max(rec(i+1, w + W[i]) + V[i], rec(i+1, w))

print(rec())

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
weights, values = [0]*N, [0]*N
for i in range(N):
    weights[i], values[i] = map(int, input().split())

dp = [[0]*(W+1) for _ in range(N)]
for j in range(W+1):
    dp[0][j] = values[0]
for i in range(1,N):
    for j in range(W+1):
        if j - weights[i] >=0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

max_index = a[0]
max_weight = a[1]

dp = [ [0] * (max_weight + 1) for j in range(max_index + 1)]

def solve():
    for i in range(max_index - 1, -1, -1):
        for j in range(max_weight + 1):
            if (j < b[i][0]):
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max([dp[i + 1][j], dp[i + 1][j - b[i][0]] + b[i][1]])
    print(dp)

solve()

Submission status: Wrong Answer

Solution code:
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

max_index = a[0]
max_weight = a[1]

dp = [ [0] * (max_weight + 1) for j in range(max_index + 1)]

def solve():
    for i in range(max_index - 1, -1, -1):
        for j in range(max_weight):
            if (j < b[i][0]):
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max([dp[i + 1][j], dp[i + 1][j - b[i][0]] + b[i][1]])
    print(dp[0][max_weight - 1])

solve()

Submission status: Wrong Answer

Solution code:
# D
N, W = map(int, input().split())
 
import numpy as np

dp = np.zeros(W+1)

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

print(dp[-1])

Submission status: Wrong Answer

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

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

for i in range(N):
    for w in reversed(range(0, W+1)):
        if dp[w] != 0:
            if w + item[i][0] <= W:
                dp[w + item[i][0]] = max(dp[w +item[i][0]], dp[w] + item[i][1])
        else:
            if w + item[i][0] <= W:
                dp[w + item[i][0]] = dp[w] + item[i][1]
        # print(dp)
print(max(dp))

Submission status: Wrong Answer

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

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

for i in range(N):
    for w in reversed(range(0, W+1)):
        if dp[w] != 0:
            if w + item[i][0] <= W:
                dp[w + item[i][0]] = max(dp[w +item[i][0]], dp[w] + item[i][1])
        else:
            if w + item[i][0] <= W:
                dp[w + item[i][0]] = dp[w] + item[i][1]

print(dp[W])

Submission status: Wrong Answer

Solution code:
#DP-C

n,w=map(int,input().split())
l=[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 sum_w in range(w+1):
        if sum_w-l[i-1][0]>=0:
            dp[i][sum_w]=max(dp[i-1][sum_w],dp[i-1][sum_w-l[i-1][0]]+l[i-1][1])
        else:
            dp[i][sum_w]=dp[i-1][sum_w]

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

Submission status: Wrong Answer

Solution code:
#DP-D

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

#dp配列と重さを対応させる
dp=[[0]*(n) for i in range(w+1)]
for i in range(w+1):
    for j in range(n):
        for k in range(n):

            if l[j][0]+i<=w and j!=k:
                dp[l[j][0]+i][j]=max(dp[l[j][0]+i][j],dp[i][k]+l[j][1])

print(max(dp[-1]))

Submission status: Wrong Answer

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

for i in range(1,N+1):
    for j in range(1,W+1):
        m1=dp[i-1][j]
        m2=0
        if w[i]<=j:
            m2=dp[i-1][W-w[i]]+v[i]
        # print(W,w[i])
        dp[i][j]=max(m1,m2)
print(dp[N][W])

Submission status: Wrong Answer

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

dp = np.full(N*10**5+1, W+1, dtype = np.int64)
dp[0] = 0

for i in range(N):
    w,v = map(int,input().split())
    np.minimum(dp[:-v]+w, dp[v:], out = dp[v:])

for i in range(N*10**5+1):
    if dp[i] <= W:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline  #文字列入力では注意！

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

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(n)]
#dp[i][w] 重さwでの最高価値
dp=[[-1]*(w+1) for i in range(n+1)]
dp[0][0]=0
for j in range(n):
    dp[j][0]=0
for i in range(n):
    for j in range(w+1):
        if j-WV[i][0]>=0 and j-WV[i][0]<=w:
            dp[i+1][j]=max(dp[i][j-WV[i][0]]+WV[i][1], dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[n][w])

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
V = sorted([[int(x) for x in input().split()] for _ in range(N)])
dp = [0]*(W+1)
s = 0
for w,v in V:
    s += w
    for j in range(w-1,min(W,s)):
        if dp[j-w] + v > dp[j]:
            dp[j] = dp[j-w] + v
print(max(dp))

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
V = sorted([[int(x) for x in input().split()] for _ in range(N)])
dp = [0]*(W+1)
s = 0
for w,v in V:
    s += w
    for j in range(w-1,min(W,s)):
        if dp[j-w] + v > dp[j]:
            dp[j] = dp[j-w] + v
        print(dp)

print(max(dp))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:

def solve(N, W, weight_values):
    dp = [0 for _ in range(W + 1)]
    for i in range(N):
        wi, vi = weight_values[i]
        for w in range(W, wi - 1, -1):
            temp = dp[w - wi] + vi
            if temp > dp[w]:
                dp[w] = temp

    print(dp[W])


def iln():
    return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
    w_v.append(iln())

Submission status: Wrong Answer

Solution code:
n, w = map(int ,input().split())
items = []
for i in range(n):
    array = list(map(int, input().split()))
    items.append(array)

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([i, a, b])

    dp = [[0, set()] for _ in range(W + 1)]

    for i in range(1, W + 1):
        ma = 0
        cp = set()
        for j, w, v in shina:
            if i >= w:
                if j not in dp[i - w][1]:
                    tmp = ma
                    ma = max(ma, dp[i - w][0] + v)
                    if tmp != ma:
                        cp.clear()
                        cp = cp | dp[i - w][1]
                        cp.add(j)

        dp[i][0] = ma
        dp[i][1] = dp[i][1] | cp

    print(dp[W][0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,kapacitet=map(int,input().split())
tezine=[]
vrijednosti=[]
for i in range(n):
      tezina,vrijednost=map(int,input().split())
      tezine.append(tezina)
      vrijednosti.append(vrijednost)

print(vrijednosti,tezine)
def knapSack(kapacitet, tezine, vrijednosti, n):

    mat = [[0 for x in range(kapacitet + 1)] for x in range(n + 1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n + 1): 
        for j in range(kapacitet + 1): 
            if i == 0 or j == 0: 
                mat[i][j] = 0
            elif tezine[i-1] <= j: 
                mat[i][j] = max(vrijednosti[i-1] + mat[i-1][j-tezine[i-1]],  mat[i-1][j]) 
            else: 
               mat[i][j] = mat[i-1][j]   
    return mat[n][kapacitet]
print(knapSack(kapacitet, tezine, vrijednosti, n))

Submission status: Wrong Answer

Solution code:
n,kapacitet=map(int,input().split())
tezine=[0]
vrijednosti=[0]

for i in range(n):
      tezina,vrijednost=map(int,input().split())
      tezine.append(tezina)
      vrijednosti.append(vrijednost)
def knapSack(kapacitet, tezine, vrijednosti, n): 
    mat = [[0 for x in range(kapacitet + 1)] for x in range(n + 1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n + 1): 
        for j in range(kapacitet + 1): 
            if i == 0 or j == 0: 
                mat[i][j] = 0
            elif tezine[i-1] <= j: 
                mat[i][j] = max(vrijednosti[i-1] + mat[i-1][j-tezine[i-1]],  mat[i-1][j]) 
            else: 
               mat[i][j] = mat[i-1][j] 
  
    return mat[n][kapacitet]
print(knapSack(kapacitet, tezine, vrijednosti, n))

Submission status: Wrong Answer

Solution code:
def solve(N, W, weight_values):
  dp = [0 for _ in range(W + 1)]
  dp[0] = 0

  for i in range(N + 1):
    i_weight, i_value = weight_values[i - 1]
    for w in range(W, i_weight-1, -1):
      # dp[w] = max(dp[w - i_weight] + i_value, dp[w])
      temp = dp[w - i_weight] + i_value
      if temp > dp[w]:
        dp[w] = temp

  print(dp[W])


  
def iln(): return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)

Submission status: Wrong Answer

Solution code:
def solve(N, W, weight_values):
  dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
  dp[0][0] = 1

  for i in range(N + 1):
    i_weight, i_value = weight_values[i - 1]
    for w in range(i_weight, W + 1):
      dp[i][w] = max(dp[i - 1][w - i_weight] + i_value, dp[i - 1][w])

  print(dp[N][W])

  
def iln(): return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)

Submission status: Wrong Answer

Solution code:
def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]

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

solver()

Submission status: Wrong Answer

Solution code:
n, w = map(int,input().split())
maxi = 0
possibilities = []
for i in range(n):
    wi, vi = map(int, input().split())
    to_add =[[wi, vi]]
    for wp, vp in possibilities:
        wa = wp + wi
        if wa < w:
            va = vp + vi
            maxi = max(maxi,va)
            to_add.append([wp+wi, va])
        elif wa == w:
            va = vp + vi
            maxi = max(maxi, va)
    possibilities += to_add
print(maxi)

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] * (W + 1)
con = 0

for w, v in L:
  con += w
  for i in range(min(con, W), w - 1, -1):
    print(dp,v)
    if dp[i] < dp[i - w] + v:
      dp[i] = dp[i - w] + v

print(max(dp))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

INF = float('inf')
ww = [0]*n
vv = [0]*n
vm = 1000
dp = [[INF]*(n*vm+1) for _ in range(n+1)]

for i in range(n):
  ww[i],vv[i] = map(int,input().split())      

dp[0][0] = 0  
for i in range(1,n+1):
  dp[i][0] = 0
  for j in range(1,n*vm+1):        
    if j < vv[i-1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-vv[i-1]] + ww[i-1])        

ans = 0
for i in range(n*vm+1):
  if dp[n][i]<=w:
    ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
n, max_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 for _ in range(max_w+1)] for _ in range(n+2)]

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

Submission status: Wrong Answer

Solution code:
n, max_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 for _ in range(max_w+1)] for _ in range(n+2)]

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

print(max(dp[n]))

Submission status: Wrong Answer

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

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tDPc/tasks"

################ DANGER ################
test = ""
test = \
"""
3 8
3 30
4 50
5 60
ans 90
"""

"""
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
ans 5000000000(>int32)
"""

"""
6 15
6 5
5 6
6 4
6 6
3 5
7 2
ans 17
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
# np.maximum(np.array([1,3,2]), np.array([2, 1, 3]))
N, W = map(int, input2().split())
WV = np.array([tuple(map(int, input2().split())) for _ in range(N)])

def main(N=N, W=W, WV=WV):
    dp = np.zeros(W + 1, dtype="int64")
    for w, v in WV:
        dp[W:w-1:-1] = np.maximum(dp[W:w-1:-1], dp[W-w::-1] + v)
        print(dp)

main()

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
weight=[]
money=[]
weight.append(0)
money.append(0)
for i in range(n):
    s,v=map(int,input().split())
    weight.append(s)
    money.append(v)
dp= [[-1 for i in range(w)] for j in range(n)]
for i in range(w):
    dp[0][i]=0

for i in range(1,n):
    for j in range(1,w):
        if j<weight[i]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j-weight[i]] + money[i],dp[i-1][j])
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N, W = map(int, input().split())
    dp = np.array([[0]*(W+1)]*N)
    w, v = map(int, input().split())
    dp[0][w:W+1] = v 
    for i in range(1, N):
        w, v = map(int, input().split())
        dp[i] = dp[i-1]
        for j in range(w, W+1):
                x = dp[i-1][j]
                y = dp[i-1][j-w] + v
                dp[i][j] = x if x > y else y
        print(dp)
    print(int(dp[N-1][W]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N, W = map(int, input().split())
    dp = np.array([[0]*(W+1)]*N)
    for i in range( N):
        w, v = map(int, input().split())
        for j in range(0, W-w+1):
            if i == 0:
                dp[i][j] = v
            else:
                x = dp[i-1][j]
                y = dp[i-1][j+w] + v
                dp[i][j] = x if x > y else y
    print(int(dp[N-1][0]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import pdb
input = sys.stdin.readline

N, W = map(int, input().split())
ws = []
vs = []
for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  vs.append(v)

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   # 新しい品物を入れられるとき
      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
    else:   # 新しい品物を入れられないとき
      # 価値を変えることはできない
      Value[num][load] = Value[num-1][load]
      # Value[num][load] = max(Value[num][load], Value[num-1][load])

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

Submission status: Wrong Answer

Solution code:
import sys
import pdb
input = sys.stdin.readline

N, W = map(int, input().split())
ws = []
vs = []
for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  vs.append(v)

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   # 新しい品物を入れられるとき
      # 本来はこれ。負の価値の品物があるならばこれが正しい
      # Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
      # すべての品物の価値が正なので、入れられるなら入れた方が良い
      Value[num][load] = max(Value[num][load], Value[num-1][load-ws[num]] + vs[num])
    else:   # 新しい品物を入れられないとき
      # 価値を変えることはできない
      # Value[num][load] = Value[num-1][load]
      Value[num][load] = max(Value[num][load], Value[num-1][load])

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

Submission status: Wrong Answer

Solution code:
import sys
import pdb
input = sys.stdin.readline

N, W = map(int, input().split())
ws = []
vs = []
for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  vs.append(v)

inf = 1e10

# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W+1)] for __ in range(N)]

for load in range(W+1):
  if load < ws[0]:
    # 1番目の品物を入れようがなければスキップ
    Value[0][load] = 0
  else:
    Value[0][load] = vs[0]

for num in range(1, N):
  for load in range(W+1):
    if load >= ws[num]:   # 新しい品物を入れられるとき
      # 本来はこれ。負の価値の品物があるならばこれが正しい
      # Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])
      # すべての品物の価値が正なので、入れられるなら入れた方が良い
      Value[num][load] = max(Value[num][load], Value[num-1][load-ws[num]] + vs[num])
    else:   # 新しい品物を入れられないとき
      # 価値を変えることはできない
      Value[num][load] = Value[num-1][load]
      # Value[num][load] = max(Value[num][load], Value[num-1][load])

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

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

for i in range(wv[0][0], w):
    dp[0][i] = wv[0][1]

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

Submission status: Wrong Answer

Solution code:
import collections


Item = collections.namedtuple("Item", ("weight", "value"))


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

    # i番目の品物についてループ
    for i in range(1, N+1):
        # 重さについてループ
        for sum_w in range(W + 1):
            if sum_w - items[i - 1].weight >= 0:
                dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w - items[i - 1].weight] + items[i - 1].value)
            else:
                dp[i][sum_w] = max(dp[i][sum_w], dp[i - 1][sum_w])

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

dp = [0]*(W + 1)
for s in items:
    used = set()
    for i in range(W):
        j = i + s[0]
        if j > W:
            break
        if dp[i] + s[1] > dp[j] and i not in used:
            dp[j] = dp[i] + s[1]
            used.add(j)

print(max(dp))

Submission status: Wrong Answer

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

dp = [0] * (W + 1)
cnt = 0

print(L)

for w, v in L:
    #重さを足し合わせていき合計を求める
    cnt = cnt + w
    #W=重さの制約とこれまでの重さの合計のうち、
    #小さい方から品物iの重さまで、逆順にfor文を回す
    ##3,8-5,...15-7
    for i in range(min(cnt, W), w - 1, -1):
        #同じ重さでより価値が高い組み合わせがあれば価値を更新する
        ## w < Wの制約があり、i - wとその値を参照してから更新しているため、
        ## Wの制約を満たさない値を持つことはない
        ### 方法上、持ち得ない重さに持ち得ない値がつくことがあるが、
        ### それらが解 = 最大値になることはない
        ### (解を求める過程でついでに足されたり足されなかったりするだけなので)
        if dp[i] < dp[i - w] + v:
            dp[i] = dp[i - w] + v

print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.readline

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

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

for i in range(1,N+1,1):
    for sum in range(1,W+1,1):
        if(sum-w[i]>=0):
            dp[i][sum]=max(dp[i][sum],dp[i-1][sum-w[i]]+v[i])
            continue
        dp[i][sum]=dp[i-1][sum]

print(max(dp[N][:]))

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
WV = [[0,0]] + [list(map(int,input().split())) for _ in range(N)]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1,N+1):
  tmpw, tmpv = WV[i]
  for w in range(W+1):
    if 0<=w-tmpw:
      dp[i][w] = max(dp[i][w], dp[i-1][w-tmpw]+tmpv)
    else:
      dp[i][w] = dp[i-1][w]
print(max([max(row) for row in dp]))

Submission status: Wrong Answer

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