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:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
# dp[m][w] mまで使ってwを超えない価値の最大値
dp = [[0] * (100100) for _ in range(110)]

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

print(dp[N][W])

Submission status: Wrong Answer

Solution code:
## https://atcoder.jp/contests/dp/tasks/dp_d
## TODO

def solution():
    # max value for picked 0..n items with current bag weight (0), value(1)
    res = [[-1,-1] for i in range(n)]
    res[0][0] = items[0][0]
    res[0][1] = items[0][1]
    print("res[{}] = {}".format(0, res[0]))
    for i in range(1,n):
        # res[i] = max_but_limited_of(res[i-1], res[i-2] + items[i], res[i-3] + items[i]....)
        currentWeight = res[i-1][0]
        maxValue = res[i-1][1]

        for j in range(i, -1, -1):
            if res[j][1] + items[i][1] > maxValue and res[j][0] + items[i][0] <=w:
                currentWeight = res[j][0] + items[i][0]
                maxValue = res[j][1] + items[i][1]

        res[i][0] = currentWeight
        res[i][1] = maxValue

        print("res[{}] = {}".format(i, res[i]))

    return res[-1][1]


if __name__ == "__main__":
    n, w = list(map(int, input().split(" ")))

    items = [[-1]*2 for i in range(n)]

    for i in range(n):
        items[i][0], items[i][1] = list(map(int, input().split(" ")))

    print("n = {} w = {} items = {}".format(n,w,items))
    print(solution())

Submission status: Wrong Answer

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

#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[0 for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],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())
w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
for i in range(1,N+1):
    w[i], v[i] = map(int, input().split())


#dp[i][j]:i番目までの品物を(0<=i<N)重さの総和がj以下となるように選ぶときの価値の総和の最大値
dp = [[0] * (W + 1) for i in range(N + 1)]

#配る
for i in range(N):
    for j in range(W + 1):
        if j + w[i+1] > W: continue
        dp[i+1][j+w[i+1]] = max(dp[i+1][j+w[i+1]], dp[i][j]+v[i+1])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[N][W])

# [print(d)for d in dp]

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
pre = [0] * w
ans = [0] * w

for i in range(n):
    wi, vi = map(int, input().split())
    for j in range(w):
        if wi > j:
            continue
        ans[j] = max(pre[j], pre[j-wi+1]+vi)
    pre = [j for j in ans]
print(max(ans))

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
pre = [0] * w
ans = [0] * w

for i in range(n):
    wi, vi = map(int, input().split())
    for j in range(w):
        if wi > j:
            continue
        ans[j] = max(pre[j], pre[j-wi+1]+vi)
    pre = [i for i in ans]
print(max(ans))

Submission status: Wrong Answer

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

#V = [0 for _ in range(10**5)]
V = []
W = []
dp = [[0 for _ in range(Weight)] for _ in range(N)]

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

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

            

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

Submission status: Wrong Answer

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

#V = [0 for _ in range(10**5)]
V = []
W = []

for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
def dp(i, w):
    if i<N and w-W[i]>=0:
        ans = max(dp(i+1, w), dp(i+1, w-W[i])+V[i])
    else:
        ans = 0
    return ans

print(dp(0, Weight))

Submission status: Wrong Answer

Solution code:
#tempt
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[-1 for i in range(w+1)] for j in range(n+1)]

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
n, max_w = map(int, input().split())
w = []
v = []
for i in range(n):
  t1, t2 = map(int, input().split())
  w.append(t1)
  v.append(t2)
dp = np.zeros((n, max_w+1)) #dp[item, load]
for i in range(w[0], max_w+1):
  dp[0,i] = v[0]
for i in range(1, n):
  for j in range(0, max_w+1):
    t1 = 0 
    if j >= w[i]:
      t1 = dp[i-1, j-w[i]] + v[i]
    t2 = dp[i-1, j]
    dp[i, j] = max(t1, t2)
print(dp[n-1, max_w])

Submission status: Wrong Answer

Solution code:
def main():
    N,W = map(int,input().split())
    wvlist = []
    dp =[[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        lista = list(map(int,input().split()))
        wvlist.append(lista)
    sumax = sum(wvlist[i][0] for i in range(N))
    sumin = min(wvlist[i][0] for i in range(N))
    vamax = sum(wvlist[i][1] for i in range(N))
    if sumax <= W:
        print(vamax)
    elif sumin > W:
        print(0)
    else:
        for i in range(N):
            for j in range(W+1):
                if wvlist[i][0] <= j:
                    dp[i+1][j] = max(dp[i+1][j],dp[i][j-wvlist[i][0]]+wvlist[i][1])
                else:
                    dp[i+1][j] = dp[i][j]
                    
        print(dp[N][W])
        
    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    N,W = map(int,input().split())
    wvlist = []
    dp =[[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        lista = list(map(int,input().split()))
        wvlist.append(lista)
    sumax = sum(wvlist[i][0] for i in range(N))
    sumin = min(wvlist[i][0] for i in range(N))
    vamax = sum(wvlist[i][1] for i in range(N))
    vamin = min(wvlist[i][1] for i in range(N))
    if sumax <= W:
        print(vamax)
    elif sumin > W:
        print(0)
    else:
        for i in range(N):
            for j in range(W+1):
                if wvlist[i][0] <= j:
                    dp[i+1][j] = dp[i][j-wvlist[i][0]]+wvlist[i][1]
                else:
                    dp[i+1][j] = dp[i][j]
                    
        print(dp[N][W])
        
    
    
main()

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N,W = map(int,input().split())
    wvlist = []
    dp =[[0 for i in range(N)] for j in range(N)]
    dpw = [[0 for i in range(N)] for j in range(N)]
    for i in range(N):
        lista = list(map(int,input().split()))
        wvlist.append(lista)
    sumax = sum(wvlist[i][0] for i in range(N))
    sumin = min(wvlist[i][0] for i in range(N))
    vamax = sum(wvlist[i][1] for i in range(N))
    vamin = min(wvlist[i][1] for i in range(N))
    if sumax <= W:
        print(vamax)
    elif sumin > W:
        print(0)
    else:
        dp[0] = [wvlist[i][1] for i in range(N)]
        dpw[0] = [wvlist[i][0] for i in range(N)]
        for j in range(1,N):
            for l in range(N):
                for k in range(N):
                    
                    if k == l:
                        continue
                    else:
                        dpw[j][l] = wvlist[k][0]+dpw[j-1][l]
                        if dpw[j][l] <= W:
                            dp[j][l] = max(dp[j][l],wvlist[k][1]+dp[j-1][l])
                        
                        
        print(np.amax(dp))
    
    
main()

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N,W = map(int,input().split())
    wvlist = []
    dp =[[0 for i in range(N)] for j in range(N)]
    dpw = [[0 for i in range(N)] for j in range(N)]
    for i in range(N):
        lista = list(map(int,input().split()))
        wvlist.append(lista)
    sumax = sum(wvlist[i][0] for i in range(N))
    sumin = min(wvlist[i][0] for i in range(N))
    vamax = sum(wvlist[i][1] for i in range(N))
    vamin = min(wvlist[i][1] for i in range(N))
    if sumax <= W:
        print(vamax)
    elif sumin > W:
        print(0)
    else:
        dp[0] = [wvlist[i][1] for i in range(N)]
        dpw[0] = [wvlist[i][0] for i in range(N)]
        for j in range(1,N):
            for l in range(N):
                for k in range(N):
                    if dp[j-1] == [0]*N:
                            break
                    if k == l:
                        continue
                    else:
                        dpw[j][l] = wvlist[k][0]+dpw[j-1][l]
                        if dpw[j][l] <= W:
                            dp[j][l] = max(dp[j][l],wvlist[k][1]+dp[j-1][l])
                        
                        
        print(np.amax(dp))
    
    
main()

Submission status: Wrong Answer

Solution code:
x,y=map(int,input().split())
yo=[]
yo0=[]
for __ in range(x):
    a,b=map(int,input().split())
    yo.append(a)
    yo0.append(b)
lol=[]
for i in range(2):
    lol.append([0]*(y+1))
for i in range(1,x+1):
    for j in range(1,y+1):
        if j<yo[i-1]:
            lol[i%2][j]=lol[(i-1)%2][j]
        else:
            lol[i%2][j]=max(lol[(i-1)%2][j],yo0[i-1]+lol[(i-1)%2][j-yo[i-1]])
print(lol[1][y])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return dp
print(DP())

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[0]*(m+2)

for i in range(n):  #商品を一つずつ見ていく。
  w,v=(map(int,input().split()))
  for j in range(m+1,w,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
    if dp[j-w]+v>dp[j]:
      dp[j]=dp[j-w]
    else:
      dp[j]=dp[j]
    
print(dp[m+1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
d=[ list(map(int,input().split()))  for i in range(n)]
dp=[0]*(m+2)

for i in range(n):  #商品を一つずつ見ていく。
  for j in range(m+1,d[i][0]-1,-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
    dp[j]=max(dp[j-d[i][0]]+d[i][1],dp[j]) #d[i][0]=w d[i][1]=v
    
print(dp[m+1])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
d=[ list(map(int,input().split()))  for i in range(n)]
dp=[0]*(m+1)

for i in range(n):  #商品を一つずつ見ていく。
  for j in range(m,d[i][0],-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
    dp[j]=max(dp[j-d[i][0]]+d[i][1],dp[j]) #d[i][0]=w d[i][1]=v
    
print(dp[m])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
d=[ list(map(int,input().split()))  for i in range(n)]
dp=[0]*(m+1)

for i in range(n):  #商品を一つずつ見ていく。
  for j in range(d[i][0],m): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
    dp[j]=max(dp[j-d[i][0]]+d[i][1],dp[j]) #d[i][0]=w d[i][1]=v
    
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 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>w[i]:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

for w,v in arr:
    print(dp[:-w],dp[w:])
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])
    print(dp)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
def napsack(n,weight,weights,values):
  dp=[[0]*(n+1) for i in range(weight+1)]
  for i in range(1,n+1):
    for j in range(weight+1):
      if j-weights[i-1]>=0:
        dp[j][i]=max(dp[j][i],dp[j-weights[i-1]][i-1]+values[i-1])
      else:
        dp[j][i]=max(dp[j][i-1],dp[j][i])

  return  dp[weight][n]
     
n,w=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
W=[items[i][0] for i in range(n)]
V=[items[i][1] for i in range(n)]
print(napsack(n,w,W,V))

Submission status: Wrong Answer

Solution code:
import numpy as np

def napsack(n,weight,weights,values):
  dp=[[0]*(n+1) for i in range(weight+1)]
  for i in range(1,n+1):
    for j in range(weight+1):
      if j-weights[i-1]>=0:
        dp[j][i]=np.maximum(dp[j][i],dp[j-weights[i-1]][i-1]+values[i-1])
      else:
        dp[j][i]=np.maximum(dp[j][i-1],dp[j][i])

  return  dp[weight][n]
     
n,w=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
W=[items[i][0] for i in range(n)]
V=[items[i][1] for i in range(n)]
print(napsack(n,w,W,V))

Submission status: Wrong Answer

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

import numpy as np

table = np.zeros((N+1, W+1))
def dp(N, W):
  for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(1, W+1):
      if w <= j:
        table[i][j] = max(table[i-1][j-w]+v, table[i-1][j])
      else:
        table[i][j] = table[i-1][j]
  return table[N][W]

print(dp(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 _ in range(n)]

dp = np.zeros(w+1,int)#w+1のint型配列
for i in range(n):
	W,V = WV[i]
	#print(str(dp)+":"+str(dp[W:])+":"+str(dp[:-W]))
	dp[W:] = np.maximum(dp[W:],dp[:-W]+V)
	print(str(dp))

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

N, W = map(int, raw_input().split())
dp = np.zeros((W+1, N))

w, v = map(int, raw_input().split())

dp[w][0] = v

for i in range(1, N):
    w, v = map(int, raw_input().split())
    for j in range(w, W+1):
        dp[j][i] = max(dp[j][i-1], dp[j-w][i-1]+v)

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

Submission status: Wrong Answer

Solution code:
#EDP-D, E
import sys
from collections import defaultdict
n, W = map(int, sys.stdin.readline().split())
dp = [defaultdict(int) for _ in range(n)]
#初期設定
w, v = map(int, sys.stdin.readline().split())
dp[0][w] = v
#print(dp)

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    dp[i][w] = max(dp[i-1].get(w, 0), v) 
    for w1, v1 in dp[i-1].items():
        dp[i][w1] = max(dp[i][w1], v1)
        if w+w1<=W:
            dp[i][w1+w] = max(dp[i][w1+w], v1+v)

Submission status: Wrong Answer

Solution code:
from itertools import count

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 w in range(W+1):
        if w - WV[i][0] >= 0:  # 品物を追加できるとき
            dp[i+1][w] = max(dp[i+1][w], dp[i][w-WV[i][0]] + WV[i][1])
        # できないとき
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
print(dp)
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    d = collections.defaultdict(int)
    d[0] = 0
    for ww, vv in wv:
        dd = sorted(d.items())
        for k, v in dd:
            if ww + k <= w:
                d[ww+k] = max(d[ww+k], d[k] + vv)
    t = 0
    for k, v in d.items():
        if k <= w:
            t = max(t, v)
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    d = collections.defaultdict(int)
    d[0] = 0
    for ww, vv in wv:
        dd = sorted(d.items())
        for k, v in dd:
            d[ww+k] = max(d[ww+k], d[k] + vv)
    t = 0
    for k, v in d.items():
        if k <= w:
            t = max(t, v)
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

for i in range(1,n+1):
    w,v=map(int,input().split())
    for j in range(m+1):
        if  j+w>m:
            continue
        dp[i][j+w]=max([dp[i][j+w],dp[i-1][j+w],dp[i-1][j]+v])
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(max(dp[n]))

Submission status: Wrong Answer

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

for i in range(1,n+1):
    w,v=map(int,input().split())
    for j in range(m+1):
        if  j+w>m:
            continue
        dp[i][j+w]=max(dp[i-1][j+w],dp[i-1][j]+v)
        dp[i][j]=max(dp[i][j],dp[i-1][j])

print(max(dp[n]))

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

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

Submission status: Wrong Answer

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

dp=[-1]*(W+1)
dp[0]=0
for w,v in WV:
  for i in range(W-w,-1,-1):
    if dp[i]!=-1:
      dp[i+w]=max(dp[i+w],dp[i]+v)
print(dp)
print(max(dp))

Submission status: Wrong Answer

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

weights = [0]*(N+5)
values = [0]*(N+5)

dp = [[0]*(W+5) for i in range(N+5)]

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w >= weights[i]:
            if dp[i+1][sum_w] < dp[i][sum_w-weights[i]]+values[i]:
                dp[i+1][sum_w] = dp[i][sum_w-weights[i]]+values[i]
        else:
            if dp[i+1][sum_w] < dp[i][sum_w]:
                dp[i+1][sum_w] = dp[i][sum_w]


print(max([max(row) for row in dp]))

Submission status: Wrong Answer

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

weights = [0]*(N+10)
values = [0]*(N+10)

dp = [[0]*(W+10) for i in range(N+10)]

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w >= weights[i]:
            dp[i+1][sum_w] = max(dp[i][sum_w-weights[i]]+values[i],
                                 dp[i+1][sum_w])
        else:
            dp[i+1][sum_w] = max(dp[i][sum_w],
                                 dp[i+1][sum_w])

print(max([max(row) for row in dp]))

Submission status: Wrong Answer

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

weights = [0]*(N+10)
values = [0]*(N+10)

dp = [[0]*(W+10) for i in range(N+10)]

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w >= weights[i]:
            dp[i+1][sum_w] = max(dp[i][sum_w-weights[i]]+values[i],
                                 dp[i+1][sum_w])
        else:
            dp[i+1][sum_w] = max(dp[i][sum_w],
                                 dp[i+1][sum_w])

print(dp[N][W])

Submission status: Wrong Answer

Solution code:
def main():
    N, W = map(int, input().split())
    wi, vi = map(int, input().split())
    dp = [0] * wi + [vi] * (W - wi)
    for _ in range(1, N):
        wi, vi = map(int, input().split())
        dp = dp[:wi] + [max(i + vi, j) for i, j in zip(dp[:W - wi], dp[wi:])]
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
array = [[0] * (W+1) for i in range((N+1))]
for i in range(N):
  wei,V = map(int,input().split())
  for j in range(W):
    if(wei<=j+1):
      if(array[i+1][j+1] < array[i+1][j-wei+1]+V):
        array[i+1][j+1]=array[i][j-wei+1]+V
      else:
        array[i+1][j+1]=array[i][j+1]
    else:
      array[i+1][j+1]=array[i][j+1]
print(array[N][W])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
num,weight=map(int,input().split())
lv=[]
lw=[]
for i in range(num):
  a,b=map(int,input().split())
  lv.append(b)
  lw.append(a)
dp=[[-1 for i in range(weight+1)] for j in range(num)]
for i in range(weight+1):
  if i<=lw[0]:
    dp[0][i]=0
  else:
    dp[0][i]=lv[0]
def nap(n,w):
  if dp[n][w]!=-1:
    return dp[n][w]
  else:
    res=0
    if lw[n]>w:
      res=nap(n-1,w)
    else:
      m1=nap(n-1,w)
      m2=nap(n-1,w-lw[n])+lv[n]   
      res=max(m1,m2)
    dp[n][w]=res
    return res
nap(num-1,weight)
print(dp[num-1][weight])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
num,weight=map(int,input().split())
lv=[]
lw=[]
for i in range(num):
  a,b=map(int,input().split())
  lv.append(b)
  lw.append(a)
dp=[[-1 for i in range(weight)] for j in range(num)]
for i in range(weight):
  if i<lw[0]:
    dp[0][i]=0
  else:
    dp[0][i]=lv[0]
def nap(n,w):
  if dp[n][w]!=-1:
    return dp[n][w]
  else:
    res=0
    if lv[n]>w:
      res=nap(n-1,w)
    else:
      m1=nap(n-1,w)
      m2=nap(n-1,w-lw[n])+lv[n]   
      res=max(m1,m2)
    dp[n][w]=res
    return res
nap(num-1,weight-1)
print(dp[num-1][weight-1])

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
#dp=[[0,0] for i in range(w+1)]
dp=[]
for i in range(w+1):
    dp.append([0,0])
dp[0][0]=1
it=[]
val=[]
for i in range(n):
    a,b=input().split()
    it.append(int(a))
    val.append(int(b))
for i in range(n):
    x=it[i]
   # dp2=dp[:]
    ac=[]
    for j in range(w-x+1):
        if dp[j][0]==1:
           # print(i,j)
            ac.append(j+x)
            dp[j+x][1]=max(dp[j+x][1],val[i]+dp[j][1])
   
    for i in ac:
        dp[i][0]=1
  #  print(dp,dp2)
print(max([i[1] for i in dp]))

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
#dp=[[0,0] for i in range(w+1)]
dp=[]
for i in range(w+1):
    dp.append([0,0])
dp[0][0]=1
it=[]
val=[]
for i in range(n):
    a,b=input().split()
    it.append(int(a))
    val.append(int(b))
for i in range(n):
    x=it[i]
    dp2=dp[:]
    ac=[]
    for j in range(w-x+1):
        if dp[j][0]==1:
           # print(i,j)
            ac.append(j+x)
            dp2[j+x][1]=max(dp[j+x][1],val[i]+dp[j][1])
    dp=dp2[:]
    for i in ac:
        dp[i][0]=1
  #  print(dp,dp2)
print(max([i[1] for i in dp]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
num,weight=map(int,input().split())
l=[]
for i in range(num):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(weight)] for j in range(num)]
for i in range(weight):
  if i<l[0][0]:
    dp[0][i]=0
  else:
    dp[0][i]=l[0][1]
def nap(n,w):
  if dp[n][w]!=-1:
    return dp[n][w]
  elif l[n][0]>w:
    dp[n][w]=nap(n-1,w)
    return dp[n][w]
  else:
    m1=nap(n-1,w)
    m2=nap(n-1,w-l[n][0])+l[n][1]    
    dp[n][w]=max(m1,m2)
    return dp[n][w]
nap(num-1,weight-1)
print(dp[num-1][weight-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
num,weight=map(int,input().split())
l=[]
for i in range(num):
  l.append(list(map(int,input().split())))
dp=[[-1 for i in range(weight)] for j in range(num)]
for i in range(weight):
  if i<l[0][0]:
    dp[0][i]=0
  else:
    dp[0][i]=l[0][1]
def nap(n,w):
  if dp[n][w]!=-1:
    return dp[n][w]
  elif l[n][0]>w:
    dp[n][w]=nap(n-1,w)
  else:
    m1=nap(n-1,w)
    m2=nap(n-1,w-l[n][0])+l[n][1]    
    dp[n][w]=max(m1,m2)
  return dp[n][w]
nap(num-1,weight-1)
print(dp[num-1][weight-1])

Submission status: Wrong Answer

Solution code:
def main(s):
    a = s.count("0")
    b = s.count("1")
    return 2*min(a,b)

s = input()


print(main(s))

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
cost=[0]*w
value=[tuple(map(int,input().split())) for i in range(n)]
for i in range(w):
  for j in value:
    if i+j[0]>n-1:break
    cost[i+j[0]]=max(cost[i+j[0]],cost[i]+j[1])
print(max(cost))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#メモ化したもの(修正版)
n,w=map(int,input().split())
a=[]
dp=[]
for i in range(n):
   a.append(list(map(int,input().split())))
x=[]
for m in range(w+1):
    x.append(-1)
for k in range(n+1):
   dp.append(x)
def rec(i,j):
   if dp[i][j]>=0:
       return dp[i][j]
   if i==n:
       res=0
   elif j<a[i][0]:
       res=rec(i+1,j)
   else:
       res=max(rec(i+1,j),rec(i+1,j-a[i][0])+a[i][1])
   dp[i][j]=res
   return res
print(rec(0,w))

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = dp[i][total_w-li[i][0]]+li[i][1]
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(li[i][0]-1,w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[n][w]
print(knapsack(n,w,li))

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w])
    return dp[n][w]
print(knapsack(n,w,li))

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w])
    return max(dp[-1])
print(knapsack(n,w,li))

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w])
    return dp[-1][-1]
print(knapsack(n,w,li))

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(li[i][0]-1,w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w])
    return dp[-1][-1]
print(knapsack(n,w,li))