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: Accepted

Solution code:
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# Knapsack 1

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

cost_list = [0 for i in range(W+1)]
max_cost = 0

# DP loop
for knap in knapsack_list:
    weight = knap[0]
    value = knap[1]
    for i in reversed(range(0, W+1)): # cost update
        loc = i - weight
        if loc<0:
            break
        new_cost = cost_list[loc] + value
        new_cost = max(cost_list[i], new_cost)
        cost_list[i] = new_cost

# max cost process
for cost in cost_list:
    if cost > max_cost:
        max_cost = cost

# print max cost
print(max_cost)

Submission status: Accepted

Solution code:
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

    for i in range(N):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j - w] + v)
 
    print(dp[N][W])
 
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

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

    for i in range(N-1,-1,-1):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w_v[i][0]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j], dp[i+1][j - w] + v)
 
    print(dp[0][W])
 
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from functools import lru_cache
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s

#main
N,w=map(int,input().split())
W=[0]*N
V=[0]*N
for a in range(N):
    W[a],V[a]=map(int,input().split())
dp=[[0 for _ in range(w+1)] for _ in range(N+1)]

for a in range(1,N+1):
    for b in range(1,w+1):
        if(b-W[a-1]>=0):dp[a][b]=max(dp[a-1][b],dp[a-1][b-W[a-1]]+V[a-1])
        else: dp[a][b]=dp[a-1][b]
print(dp[N][w])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    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>w[i-1]-1:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[N][W])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): #startline--------------------------------------------
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    dp = [[0]*(W+1) for i in range(N+1)]
    #dp[i][j]...i番目までの品物から重さがjを超えないよう選んだ時の勝ちの総和の最大値
    for i in range(W):
        dp[N][i] = 0
    for i in range(N-1,-1,-1):
        for j in range(W+1):
            if j < w[i]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

    print(dp[0][W])
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
#!/usr/bin/env python3 
# Knapsack問題

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

# calc
dp = [[0 for _ in range(W+1)] for _ in range(N+2)]

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

Solution code:
# Knapsack問題

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

# calc
dp = [[0 for _ in range(W+1)] for _ in range(N+2)]

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

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-1][j-w]+v, dp[i-1][j])

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

Submission status: Accepted

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, dp[i-1][j])

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

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): #startline--------------------------------------------
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(W):
        dp[N][i] = 0
    for i in range(N-1,-1,-1):
        for j in range(W+1):
            if j < w[i]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
    print(dp[0][W])
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

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

import numpy as np
dp = np.zeros(W+1, dtype=int)

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

print(dp[-1])

Submission status: Accepted

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

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

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

print(DP[M][W])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    n, W = map(int, input().split())
    dp = np.zeros(W + 1, dtype = np.int64)
    for i in range(n):
        w,v=map(int,input().split())
        dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    import numpy as np

    N, W = map(int, input().split())
    dp = np.zeros(W + 1, dtype = np.int64)

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

    print (dp[W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
n,mw = map(int,input().split())

dp = [[0 for _ in range(mw + 1)]for _ in range(n + 1)] #dp[i個目までを取る][重さ]

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

print(dp[n][mw])

Submission status: Accepted

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

Submission status: Accepted

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:W+1] = np.maximum(dp[0:W+1-w]+v,dp[w:W+1])
print(dp[-1])

Submission status: Accepted

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] = np.maximum(dp[w:W+1], dp[:W-w+1] + v)
    
print(dp[-1])

Submission status: Accepted

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[-1])

Submission status: Accepted

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[-1])

Submission status: Accepted

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((n+1, W+1), dtype=int)

for i in range(n):
    dp[i+1][:wv[i][0]] = dp[i][:wv[i][0]]
    dp[i+1][wv[i][0]:] = np.maximum(dp[i][:-wv[i][0]] + wv[i][1], dp[i][wv[i][0]:])
print(dp[n][W])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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] = max(dp[i][j], v+dp[i][j-w])

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

Submission status: Accepted

Solution code:
from collections import namedtuple


Item = namedtuple('Item', 'w v')

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

items = []

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

memo = [0] * (W + 1)

for item in items:
  for w in range(W, item.w - 1, -1):
    memo[w] = max(memo[w], memo[w - item.w] + item.v)
    
print(memo[W])

Submission status: Accepted

Solution code:
N, W=map(int, input().split())
WV=[list(map(int, input().split())) for i 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-w] == -1:
            continue
        dp[i] = max(dp[i], dp[i-w] + v)
print(max(dp))

Submission status: Accepted

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

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

Submission status: Accepted

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

DP = []
for w,v in F:
    if DP == []:
        DP = [0]*w+[v]*(W-w+1)
    else:
        dp = DP[::]
        for w2 in range(w,W+1):
            dp[w2] = max(DP[w2-w] + v, DP[w2])
        DP = dp
    #print(DP)
print(DP[-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N, WW = map(int, input().split())
W, V = [], []
for _ in range(N):
    _w, _v = list(map(int, input().split()))
    if _w > WW:
        continue
    W.append(_w)
    V.append(_v)

dp = [[0] * (WW+1) for _ in range(N+1)]
for i in range(1, N+1):
    # i := 1...N
    for j in range(1, WW+1):
        # j := 0...WW
        
        wi = W[i-1]
        vi = V[i-1]
        if j-wi < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)

print(dp[N][WW])

Submission status: Accepted

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())

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

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

Submission status: Accepted

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

# DP
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] >= 0:
      dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
    else:
      dp[i + 1][j] = dp[i][j]

print(dp[N][W])

Submission status: Accepted

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())

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]

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[-1][-1])

Submission status: Accepted

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: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][i] = 0
for i in range(1, n + 1):
    for j in range(0, w + 1):
        if j - wv[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wv[i][0]] + wv[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][w])

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(n):
  weight, value = map(int, input().split())
  for j in range(w, -1, -1):
    if j == 0 or dp[j] != 0:
      if j+weight <= w:
        dp[j+weight] = max([dp[j+weight], dp[j]+value])

print(max(dp))

Submission status: Accepted

Solution code:
N,W = [int(i) for i in input().split()]
dp = [0 for i in range(W+1)] # dp[i] is the the max value you have achieve with weight i
for i in range(N):
  w,value = [int(i) for i in input().split()]
  for weight in range(W-w, -1, -1): # range of kanpsack weight in which i can push the current item
    dp[weight + w] = max(dp[weight + w], dp[weight] + value)
print("%s" % dp[W])

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.readline

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

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

    for i in range(1, n + 1):  # i個目の品物を選ぶかどうか決めた後の価値の総和の最大値,1-indexed
        wi, vi = map(int, readline().split())
        for j in range(wi):
            dp[i][j] = dp[i - 1][j]
        for j in range(wi, w + 1):
            dp[i][j] = max(
                dp[i - 1][j],  # i-1にすることにdebugで気づいた
                dp[i - 1][j - wi] + vi
            )

    print(max(dp[n]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(1,n+1):
    weight,value = map(int,input().split())
    for j in range(w+1):
        if j < weight:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight]+value)

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

Submission status: Accepted

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]] = dp[i][:l[i][0]]
        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: Accepted

Solution code:
import numpy as np 
IN = lambda:map(int, input().split())
 
n, k = IN()
dp = np.zeros(k + 1)
 
for i in range(n):
    w, c = IN()
    dp[w:] = np.maximum(dp[w:], dp[:-w] + c)
    
print(int(dp[-1]))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w_L,v_L = [],[]

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

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

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

print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(dp[-1][W])

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    vdp = [[0 for _ in range(W+1)] for _ in range(N+1)]
    
    for i in range(N):
        for weight in range(W+1):
            # 品物iを（選べるなら）選ぶ
            if weight >= w[i]: vdp[i+1][weight] = max(vdp[i][weight - w[i]] + v[i], vdp[i][weight])
            # 品物iを選ばない
            vdp[i+1][weight] = max(vdp[i+1][weight], vdp[i][weight])
    print(vdp[N][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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

w, v = na()
dp[0][w] = v

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N, W = [int(item) for item in input().split()]
    item = np.array([[int(item) for item in input().split()] for _ in range(N)])

    dp = np.zeros((2, W+1), dtype='int64')

    for i in range(N):
        dp[i%2 ^ 1] = dp[i % 2]
        w, v = item[i]
        np.maximum(dp[i%2][:-w] + v, dp[i%2][w:], out=dp[i%2 ^ 1][w:])
        # print(dp[i+1])
    print(dp[N%2][W])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

Product_Num, Limit_of_the_weight = map(int, input().split())

dp = np.zeros(Limit_of_the_weight + 1)

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

print(int(np.max(dp)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N, W = [int(item) for item in input().split()]
    item = np.array([[int(item) for item in input().split()] for _ in range(N)])

    dp = np.zeros((N+1, W+1), dtype='int64')

    for i in range(N):
        dp[i+1] = dp[i]
        w, v = item[i]
        np.maximum(dp[i][:-w] + v, dp[i][w:], out=dp[i+1][w:])
        # print(dp[i+1])
    print(dp[N][W])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin

mod = 1000000007
inf = 1 << 60
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n, mw = na()
wv = [na() for i in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
dp = [(mw + 1) * [0] for i in range(n + 1)]

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

print(dp[n][mw])