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:
# edpc d dfs tuple

import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
from functools import lru_cache

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める

@lru_cache(maxsize=None)
def dfs(total_w, total_v, w, x, i):
    if i == n or total_w + x[i][0] > w:
        return total_v
    return max(dfs(total_w + x[i][0], total_v + x[i][1], w, x, i + 1), dfs(total_w, total_v, w, x, i + 1))

n, w = map(int, input().split())
x = []
for i in range(n):
    a, b = map(int, input().split())
    x.append((a, b))
x = tuple(x)
# print(x)
# print(x[0])
# for i in range(n):
#     print(x[i][0], x[i][1])
print(dfs(0, 0, w, x, 0))

Submission status: Wrong Answer

Solution code:
# edpc d

import itertools
from math import factorial
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
def dfs(total_w, total_v, w, x, i):
    if i == n or total_w + x[i][0] > w:
        return total_v
    return max(dfs(total_w + x[i][0], total_v + x[i][1], w, x, i + 1), dfs(total_w, total_v, w, x, i + 1))

n, w = map(int, input().split())
x = [[] for i in range(n)]
for i in range(n):
    x[i] = list(map(int, input().split()))
# print(x)
print(dfs(0, 0, w, x, 0))

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
w=min(w,10000)
ans=[]
for i in range(n):
    z=list(map(int,input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
#driver code for finding out maximum of array
for i in range(n+1):
    for j in range(w+1):
        dps[i][j]=dp(j,i)
        maxa=max(maxa,dps[i][j])

print(maxa)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,w=map(int,input().split())
w=min(w,10005)
ans=[]
for i in range(n):
    z=list(map(int,input().split()))
    ans.append(z)
dps=[[0 for i in range(w+1)] for i in range(n+1)]
vi=[[0 for i in range(w+1)] for i in range(n+1)]
#first index denotes row number , second denotes coloumn number
inde=0
def dp(w,inde):
    
    if(w<=0):
        return 0;
    if(inde>=n):
        return 0;
    
    if(vi[inde][w]):
        return dps[inde][w];
    vi[inde][w]=1
    
    if(w-ans[inde][0]==0 or dp(w-ans[inde][0],inde+1)!=0):
        dps[inde][w]=max(dp(w,inde+1),(dp(w-ans[inde][0],inde+1)+ans[inde][1]))
    else:
        dps[inde][w]=dp(w,inde+1)
        
    return dps[inde][w];

maxa=0
#driver code for finding out maximum of array
for i in range(n+1):
    for j in range(w+1):
        dps[i][j]=dp(j,i)
        maxa=max(maxa,dps[i][j])

print(maxa)

Submission status: Wrong Answer

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

dp = [[0 for j in range(weight+1)] for i in range(n+1)]

for i in range(n+1):
    if i == 0:
        continue
    for j in range(weight+1):
        case1 = dp[i-1][j]
        if j - items[i-1][0] < 0:
            case2 = -1
        else:
            case2 = dp[i-1][j-items[i-1][0]] + items[i-1][1]
        dp[i][j] = max(case1,case2)

print(max([dp[i][weight-1] for i in range(n+1)]))

Submission status: Wrong Answer

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

dp = [[0 for j in range(weight+1)] for i in range(n+1)]

for i in range(n+1):
    if i == 0:
        continue
    for j in range(weight+1):
        case1 = dp[i-1][j]
        if j - items[i-1][0] < 0:
            case2 = -1
        else:
            case2 = dp[i-1][j-items[i-1][0]] + items[i-1][1]
        dp[i][j] = max(case1,case2)

print(max([dp[i][weight-1] for i in range(n)]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
from collections import defaultdict
n,w=map(int,stdin.readline().split())
d=defaultdict(int)
l1,l2=[],[]
for i in range(n):
    ww,v=map(int,stdin.readline().split())
    l1.append(ww)
    l2.append(v)
l3,l4=[l1[0]],[l2[0]]
for i in range(1,n):
    for j in range(len(l3)):
        l3.append(l1[i]+l3[j])
        l4.append(l2[i]+l4[j])
        d[l1[i]+l3[j]]=max(d[l1[i]+l3[j]],l2[i]+l4[j])
        l3.append(l1[i])
        l4.append(l2[i])
    d[l1[i]]=max(d[l1[i]],l2[i])
l3.sort()
val=0
for i in l3:
    if i>w:
        break
    val=max(val,d[i])
print val

Submission status: Wrong Answer

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


# この前段階で、荷物の数N、ウェイトの上限W、
# weightの表weightとvalueの表valueは用意しておく。
def knapsack(N, W, weight, value):
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(N):
        for w in range(W + 1):
            if w >= weight[i]:  # 荷物が加わる可能性がある
                # max関数の第一引数だと、既存の荷物の方がましな場合。
                # 第二引数だと、新入りを加えた方が良い場合。
                dp[i + 1][w] = max(dp[i+1][w], dp[i][w - weight[i]] + value[i])
            else:  # 加わる可能性はない
                dp[i + 1][w] = max(dp[i+1][w],dp[i][w])

    return dp[N][W]

print(knapsack(N, W, weight, value))

Submission status: Wrong Answer

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    N, W = map(int, input().split())
    weight, value = [0] * N, [0] * N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())

    # この前段階で、荷物の数、ウェイトの上限、weightとvalueを敷き詰めた表は用意しておく。
    def knapsack(N, W, weight, value):

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

        for i in range(N):
            for w in range(W + 1):
                if w>=weight[i]:  # 荷物が加わる可能性がある
                    # max関数の第一引数だと、既存の荷物の方がましな場合。
                    # 第二引数だと、新入りを加えた方が良い場合。
                    dp[i + 1][w] = max(dp[i+1][w],dp[i][w - weight[i]] + value[i])
                else:  # 加わる可能性はない
                    dp[i + 1][w] = dp[i][w]

        return dp[N][W]

    print(knapsack(N,W,weight,value))

resolve()

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]
 
dp = [0] * (w+1)
for wi, vi in wv:
    for sum_w in reversed(range(w)):
        dp[sum_w] = max(dp[sum_w], dp[sum_w - wi] + vi)
print(dp[w])

Submission status: Wrong Answer

Solution code:
def main():
    n, w = map(int, input().split())
    dp = {}
    dp[0] = 0
    ws = [None]*n
    vs = [None]*n
    for i in range(n):
        ws[i], vs[i] = map(int, input().split())
    for i in range(n):
        buf = []
        for v in dp.keys():
            if int(v) + ws[i] > w:
                continue
            if int(v) + ws[i] in dp.keys() and dp[v] + vs[i] > dp[v+ws[i]]:
                buf.append([int(v)+ws[i], dp[v] + vs[i]])
            else:
                buf.append([int(v)+ws[i], dp[v] + vs[i]])
        for j in range(len(buf)):
            dp[buf[j][0]] = buf[j][1]
    print(max(dp.values()))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

for n in range(1, N+1):
  for w in range(1, W+1):
    dp[n][w] = max(dp[n-1][max(0, w-WV[n-1][0])] + WV[n-1][1], dp[n-1][w])

print(max(dp[N]))

Submission status: Wrong Answer

Solution code:
import numpy as np

n, W = map(int, input().split())
w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())
ndp = np.zeros(W + 1, dtype=np.int64)

print(ndp)

for w, v in zip(w, v):
    # [:w]は品物の重量がナップサックの空きよりも重いので更新しない。
    # ndp[w:] は通常DPでのdp[i][w]=dp[i-1][w]。そのままでの更新。
    # ndp[:-w] + v は[:-w]が[w-weight]に相当。
    np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])

print(ndp[-1])

Submission status: Wrong Answer

Solution code:
import sys

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

WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = (-1)*10**13

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

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

Submission status: Wrong Answer

Solution code:
import sys

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

WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = (-1)*10**11

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

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

Submission status: Wrong Answer

Solution code:

import numpy as np  

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

dp = np.array([0] * w) 

for i in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np  

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

dp = np.zeros(w+1)

for i in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(dp[-1])

Submission status: Wrong Answer

Solution code:

import numpy as np  

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

dp = np.array([0] * w)

for i in range(n):
    weight, value = map(int, input().split())

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np  

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

dp = np.zeros(w+1)

for _ in range(n):
    weight, value = map(int, input().split())

    dp[w:] = np.maximum(dp[w:], dp[:-w] + value)

print(int(dp[-1]))

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
weight=[0]*N
value=[0]*N
for i in range(N):
    weight[i],value[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>=weight[i]):
            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])
for i in range(N+1):
    print(dp[i])

Submission status: Wrong Answer

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

dp = np.zeros((n+1, w), np.int64)


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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.zeros((W + 1))

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
f = [0 for m in range(M + 1)]
for n in range(N):
    for m in range(M + 1):
        if m >= W[n]:
            f[m] = max(f[m], f[m - W[n]] + V[n])
print(f[M])

Submission status: Wrong Answer

Solution code:
import copy
N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp0=[0 for p in range(W+1)] 
dp1=[0 for p in range(W+1)] 
dp1[Wlist[0]]=Vlist[0]
for i in range(1,N):
  wi=Wlist[i]
  for j in range(W):
    if j+wi<=W:
      dp1[j+wi]=max(dp0[j]+Vlist[i],dp1[j+wi])
    dp1[j]=max(dp0[j],dp1[j])
  dp0=copy.copy(dp1)
print(max(dp1))

Submission status: Wrong Answer

Solution code:

def knapSack(W , wt , val , n): 

    # Base Case 
    if n == 0 or W == 0 : 
        return 0
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapSack(W , wt , val , n-1) 
    # Check for required value in lookup table first
    if (lookup[n][W]!=-1):
        return lookup[n][W]     
    # Add to lookup table and return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        x = max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), knapSack(W , wt , val , n-1))
        lookup[n][W] = x
        return x

n,W = map(int,input().split())
wt =[];val=[]
size = n+1
lookup = [[-1]*(W+1)]* size
for _ in range(n):
  wi , vi= map(int,input().split())
  wt.append(wi)
  val.append(vi)

result = knapSack(W,wt,val,n)
print(result)

Submission status: Wrong Answer

Solution code:
def knapsack(n,c):
  
  
  if n < 0 :
    return 0
  if dp[n][c]!=None:
    return dp[n][c]
  if w[n] > c:
    return knapsack(n-1,c)
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n])
    opt2 = knapsack(n-1,c)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

n,c = map(int,input().split())
w =[];v=[]
size = n+1
dp = [[None]*(c+1)]* size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n-1,c)
print(result)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def knapsack(n,c):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    dp[n][c]=0
    return dp[n][c]
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n])
    opt2 = knapsack(n-1,c)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [None]; v = [None]
size = n+1
dp = [[None]*(c+1)]* size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c)
print(result)

Submission status: Wrong Answer

Solution code:

def knapsack(n,c):
  
  
  if n < 0 :
    return 0
  if dp[n][c]!=None:
    return dp[n][c]
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n])
    opt2 = knapsack(n-1,c)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

n,c = map(int,input().split())
w =[];v=[]
size = n+1
dp = [[None]*(c+1)]* size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n-1,c)
print(result)

Submission status: Wrong Answer

Solution code:

def knapsack(n,c):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n < 0 :
    return 0
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n])
    opt2 = knapsack(n-1,c)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

n,c = map(int,input().split())
w =[];v=[]
size = n+1
dp = [[None]*(c+1)]* size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n-1,c)
print(result)

Submission status: Wrong Answer

Solution code:

def knapsack(n,c):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n < 0 or c == 0:
    return 0
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n])
    opt2 = knapsack(n-1,c)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

n,c = map(int,input().split())
w =[];v=[]
size = n+1
dp = [[None]*(c+1)]* size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n-1,c)
print(result)

Submission status: Wrong Answer

Solution code:

def knapsack(n,c):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    dp[n][c]=0
    return dp[n][c]
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n])
    opt2 = knapsack(n-1,c)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [None]; v = [None]
size = n+1
dp = [[None]*(c+1)]* size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c)
print(result)

Submission status: Wrong Answer

Solution code:

def knapsack(n,c,w,v,dp):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    dp[n][c]=0
    return dp[n][c]
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [-1]; v = [-1]
size = n+1
dp = [[None]*(c+1)]* size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)

Submission status: Wrong Answer

Solution code:

def knapsack(n,c,w,v,dp):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    return 0
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [-1]; v = [-1]
size = n+1
dp = [[None]*(c+1)]*size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)

Submission status: Wrong Answer

Solution code:

def knapsack(n,c,w,v,dp):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 :
    return 0
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [-1]; v = [-1]
size = n+1
dp = [[None]*(c+1)]*size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)

Submission status: Wrong Answer

Solution code:
def knapsack(n,c,w,v,dp):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    return 0
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [None]; v = [None]
size = n+1
dp = [[None]*(c+1)]*size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)

Submission status: Wrong Answer

Solution code:

def knapsack(n,c,w,v,dp):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    return n
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [-1]; v = [-1]
size = n+1
dp = [[None]*(c+1)]*size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)

Submission status: Wrong Answer

Solution code:

def knapsack(n,c,w,v,dp):
  if dp[n][c]!=0:
    return dp[n][c]
  
  if n == 0 or c == 0:
    return n
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [-1]; v = [-1]
size = n+1
dp = [[0]*(c+1)]*size
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)

Submission status: Wrong Answer

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

dp = {}
dp[0] = 0
for i in range(n):
    wi, vi = [int(v) for v in input().split()]
    tmp = []
    for wj, vj in dp.items():
        key = wi + wj
        if key > w:
            continue
        if key in dp:
            dp[key] = max(dp[key], vi + vj)
        else:
            tmp.append((key, vi + vj))

    for key, val in tmp:
        dp[key] = val

print(max(dp.values()))

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
l = []
for i in range(n):
      l.append(tuple(map(int,input().split())))
dp = [[0]*w]*n
for num in range(n-1):
      for wg in range(w):
            if wg - l[num][0] >=0:
                  dp[num+1][wg] = max(dp[num+1][wg],dp[num][wg-l[num][0]] + l[num][1])
            dp[num+1][wg] = max(dp[num+1][wg],dp[num][wg])
print(dp[n-1][w-1])

Submission status: Wrong Answer

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

K = [[0 for x in range(W+1)] for y in range(N+1)]

for i in range(N+1):
	for w in range(W+1):
		if i == 0 or w == 0:
			K[i][w] = 0
		elif wt[i-1] <= w:
#			print("ayo")
			K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w])
		else:
			K[i][w] = K[i-1][w]
print(K[N][W])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,w=mii()
wei,val=[0],[0]

for i in range(n):
    x,y=mii()
    wei.append(x)
    val.append(y)

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

dp = [0]*(w+1)

for _ in range(n):
  wei, v = map(int, input().split())
  dp_1 = dp[:]
  for j in range(w + 1):
    if j - wei >= 0:
      dp[j] = dp_1[j-wei] + v if (dp_1[j-wei] + v) > dp_1[j] else dp[j]
  print(dp)
print(dp[w])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())
wv = []
for _ in range(N):
  wv += list(map(int, input().split()))
wv = np.array(wv).reshape(N,2)
dp = np.zeros((110, 100100))
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[:N+1,:W+1])
print(int(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 i in range(N+1)]

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

ret = 0
for i in dp:
    ret = max(ret, i[-1])
print(ret)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)

DP = [[0] * M for _ in range(W + 3)]

for i in range(1, W+2):
    for j, (weight, value) in enumerate(WEIGHTS):
        if i - weight >= 0:
            DP[i+1][j] = max(x if index != j else 0 for index, x in enumerate(DP[max(i - weight, 0)])) + value

print(max(DP[W + 2]))

# 0 1 2 3  4  5  6  7  8  9   10  11  12
#       30 30 30 30 80 90 90  90  90  140
#       0  50 50 50 80 80 110 110 110 140
#       0  0  60 60 60 90 110 110 110 140

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

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 _ in range(N)], dtype="int64")
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)
    
print(dp[-1])

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

Submission status: Wrong Answer

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

dp = [[float('inf') for _ in range(W+1)] for _ in range(n+1)]
dp[0][0] = 0

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

ans = 0
for val in dp[-1]:
    if val == float('inf'): continue
    else: ans = max(ans, val)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
mer=[list(map(int,input().split())) for i in range(n)]
dp=[[0]*w for i in range(n+1)]
for i in range(1,n+1):
    for j in range(w):
        if j>=mer[i-1][0]:
            dp[i][j]=mer[i-1][1]+dp[i-1][j+1-mer[i-1][0]]
        dp[i][j]=max(dp[i][j],dp[i-1][j])
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())
print(w)
print(v)
dp = [[0 for i in range(W)] for j in range(N)]

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

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