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:
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])

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    N, W = map(int, readline().split())
    WV = (map(int, readline().split()) for _ in range(N))
    dp = [0] * (W+1)
    for w, v in WV:
        for i in range(W, w-1, -1):
            tmp_dp = dp[i-w] + v
            if dp[i] < tmp_dp:
                dp[i] = tmp_dp
    return max(dp)


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Accepted

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

dp=[[0 for i in range(W+1)] for j in range(N+1)] # dpリストを作る。dpの要素の数字は価値を表す。

for i in range(N): # １つ１つの商品について
    for w in range(W+1):
        if w>=list1[i][0]:
            dp[i+1][w]=max(dp[i][w],dp[i][w-list1[i][0]]+list1[i][1])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[-1][-1])

Submission status: Accepted

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

dp=[[0]*(W+1) for i in range(n+1)]
for i in range(n-1,-1,-1):
  for j in range(W+1):
    if j<items[i][0]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-items[i][0]]+items[i][1])

print(dp[0][W])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
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)]
inf = float('inf')
# dp[i][weight] 
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[n][W])

Submission status: Accepted

Solution code:
N,W = [int(i) for i in input().split()]
w = [] # limit weight to knapsack capacity
v = [] # maximize value
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
mem = [[0]*(W+1) for i in range(N)]
for i in range(w[0], W+1):
  mem[0][i] = v[0]
for i in range(1, N):
  for j in range(1, W+1):
    if w[i] > j:
      mem[i][j] = mem[i-1][j]
    else:
      mem[i][j] = max(mem[i-1][j], v[i] + mem[i-1][j - w[i]])
#print(mem)
print("%s" % mem[N-1][W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0])

# 重さをi、dp[i]を価値の最大値とする
dp = [0]*(W+1)
dp[0] = 0

for i in range(N):
    w, v = wv[i]
    # 前から埋めていくとさっき更新したやつをもとに更新してしまう（同じものを使ってしまう）ので逆から更新する
    for j in range(W, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)

print(dp[W])

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]

table = np.zeros((N + 1, W + 1), dtype=np.int64)
for n in range(N):
    tmp = np.zeros(W + 1, dtype=np.int64)
    tmp[goods[n][0]:] = table[n][:W + 1 - goods[n][0]] + goods[n][1]
    table[n + 1] = np.maximum(table[n], tmp)
print(table[N][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 _ in range(n):
    w, v = map(int, input().split())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])
  print(dp[-1])
  
if __name__ == "__main__":
  main()

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 _ in range(n):
    w, v = map(int, input().split())
    np.maximum(dp[:W-w+1]+v, dp[w:W+1], out=dp[w:W+1])
  print(dp[W])
  
if __name__ == "__main__":
  main()

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 _ in range(n):
    w, v = map(int, input().split())
    dp[w:W+1] = np.array((dp[:W-w+1]+v, dp[w:W+1])).max(axis=0)
  print(dp[W])
  
if __name__ == "__main__":
  main()

Submission status: Accepted

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

dp = [0]*(W+1) # dp[i][w]はi個までの品物を使い、w以下の重さ分詰めたときの価値の最大値

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

print(dp[-1])

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
ws = [0]*n
vs = [0]*n

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
ws = [0]*N
vs = [0]*N
for i in range(N):
  w, v = map(int, input().split()) 
  ws[i] = w
  vs[i] = v
 
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
  for sum_w in range(W+1):
    if sum_w - ws[i-1] >= 0:
    	dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w-ws[i-1]]+vs[i-1])
    dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
 
print(max(dp[-1]))

Submission status: Accepted

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

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

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

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

solve()

Submission status: Accepted

Solution code:
n,Capacity=list(int(i) for i in input().split())
maxv=0
W=[]
Values=[]
for i in range(n):
    w,v=list(int(i) for i in input().split())
    if v>maxv:
        maxv=v
    W.append(w)
    Values.append(v)
dp=[[0 for j in range(Capacity+1)]for i in range(n+1)]
for i in range(n+1):
    for w in range(Capacity+1):
        if i==0 or w==0:
            dp[i][w]=0
        elif w>=W[i-1]:
            dp[i][w]=max(dp[i-1][w],Values[i-1]+dp[i-1][w-W[i-1]])
        else:
            dp[i][w]=dp[i-1][w]
print(dp[-1][-1])

Submission status: Accepted

Solution code:
ln = input()
n, cap = ln.split()
n = int(n)
cap = int(cap)

'''
weights = [[0 for x in range(2)] for y in range(n)] 
values = [[0 for x in range(2)] for y in range(n)] 
mat = [[0 for x in range(2)] for y in range(1000000)] 
'''
weights = [0 for x in range(n)] 
values =  [0 for x in range(n)] 
mat =  [0 for x in range(1000000)] 

for i in range(n):
    ln = input()
    ln = ln.split()
    weights[i] = int(ln[0])
    values[i] = int(ln[1])
 
for i in range(n):
    for j in range(cap,weights[i]-1,-1):
        '''
        print(j)
        print(values[i])
        print(mat[j-weights[i]])
        '''
        mat[j] = max(mat[j], mat[j-weights[i]] + values[i])
 
        
print(mat[cap])

Submission status: Accepted

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

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

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

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    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=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for weight in range(W+1):
            dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight])
            if weight>=w[i]:
                dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight-w[i]]+v[i])
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N, W = Scanner.map_int()
    V = [Scanner.map_int() for i in range(N)]
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if 0 <= j - V[i][0]:
                dp[i+1][j] = max(dp[i+1][j], dp[i][j - V[i][0]] + V[i][1])
    print(dp[N][W])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def knap_sack_1(weight_and_value, w):
    n = len(weight_and_value)
    dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
    for w in range(1, w + 1):
        for i in range(1, len(weight_and_value) + 1):
            w_i, v_i = weight_and_value[i-1]
            if w >= w_i:
                dp[i][w] = max(dp[i][w], dp[i-1][w - w_i] + v_i)
            dp[i][w] = max(dp[i][w], dp[i-1][w])
    return dp[-1][-1]

def get_input():
    n, k = list(map(int, input().split()))
    data = []
    for i in range(n):
        el = list(map(int, input().split()))
        data.append(el)
    return data, k

data, w = get_input()
print(knap_sack_1(data, w))

Submission status: Accepted

Solution code:
N, W, *t = map( int, open( 0 ).read().split() )
d = [[ 0 for _ in range( W + 1 ) ] for _ in range( N + 1 ) ]
ans = 0
 
i = 0
for w, v in zip( *[ iter( t )] * 2 ):
  for j in range( 1, W + 1 ):
    d[ i + 1 ][ j ] = d[ i ][ j ]
    if j - w >= 0:
      d[ i + 1 ][ j ] = max( d[ i ][ j - w ] + v, d[ i ][ j ] )
  i += 1
print( d[N][W])

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#DP-C

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

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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

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

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

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

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=[[-1]*(W+1) for _ in range(N+1)]

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

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

print(dp[N][W])

Submission status: Accepted

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

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

for i in range(n):
 for sum_w in range(w+1):

  if sum_w-l[i][0]>=0:
   dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])

  dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w])

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,W = list(map(int,input().split()))
w = [0]*N
v = [0]*N

for i in range(N):
	w[i],v[i] = list(map(int,input().split()))

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

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

Submission status: Accepted

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

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

print(dp[-1])

Submission status: Accepted

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    return b

  return a

N,W = map(int, input().split())
li = [list(map(int, input().split())) for i in range(N)]

dp = [[0] * (10**5+10) for i in [0] * (N+1)]

for n in range(N):
  for w in range(1, W+1):
    if (w - li[n][0] >= 0):
      dp[n+1][w] = chmax(dp[n+1][w], dp[n][w - li[n][0]] + li[n][1])

    dp[n+1][w] = chmax(dp[n+1][w], dp[n][w])


print(max(max(dp)))

Submission status: Accepted

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

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

for i in range(W+1):
    if wvl[0][0] <= i:
        dp[0][i] = wvl[0][1]

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

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        # i番目のitemを使わない場合
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        # i番目のitemを使う場合
        if j + items[i][0] > W:
            continue
        dp[i+1][j+items[i][0]] = max(dp[i][j] + items[i][1], dp[i+1][j+items[i][0]])
print(dp[N][W])

Submission status: Accepted

Solution code:
import sys

def main():
    _input = sys.stdin.readline

    N, W = map(int, _input().split())
    wv = [list(map(int, _input().split())) for _ in range(N)]

    wv.sort()

    DP = [-1] * (W+1)
    DP[0] = 0

    sum_w = 0
    for w, v in wv:
        sum_w += w
        for j in range(min(W, sum_w), w-1, -1):
            if DP[j-w] == -1:
                continue
            if DP[j] < DP[j-w] + v:
                DP[j] = DP[j-w] + v
    print(max(DP))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        w.append(tmpw)
        v.append(tmpv)

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

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

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    n,lim_w=map(int,input().split())
    wv = []
    for _ in range(n):
        tmp = list(map(int,input().split()))
        wv.append(tmp)
    dp = [[0] * (lim_w+1) for i in range(n+1)]

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

    print(dp[n][lim_w])
if __name__=='__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

ws, vs = zip(*[map(int, input().split()) for _ in range(n)])

dp = [0] * (w + 1)

for i in range(n):
  for j in reversed(range(w + 1)):
    if j + ws[i] <= w:
      dp[j + ws[i]] = max(dp[j + ws[i]], dp[j] + vs[i])
      
print(dp[w])

Submission status: Accepted

Solution code:

def main():
    n, w = map(int, input().split())
    weight = [0 for _ in range(110)]
    value = [0 for _ in range(110)]

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

    
    dp = [[0 for _ in range(110000)] for i in range(110)]

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

    print(dp[n][w]) 

main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, WW = map(int, input().split())
W = [0] * N
V = [0] * N
for i in range(N):
    w, v = map(int, input().split())
    W[i] = w
    V[i] = v
dp = [[0]*(WW+1) for _ in range(N+1)]
for n in range(1, N+1):
    w = W[n-1]
    v = V[n-1]
    for sum_w in range(WW+1):
        if sum_w <= WW - w:
            # n番目の商品を選ぶ
            dp[n][sum_w+w] = max(dp[n-1][sum_w] + v, dp[n][sum_w+w])
        dp[n][sum_w] = max(dp[n-1][sum_w], dp[n][sum_w])
print(dp[-1][-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def solve(N, W, weightValues):
    dp = [0] * (W + 1)
    s = 0
    for w, v in weightValues:
        s += w # why ?
        for i in range(min(W, s), w - 1, -1): # why min(W, s)
            if dp[i - w] + v > dp[i]:
                dp[i] = dp[i - w] + v

    print(max(dp))

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

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

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(2147483647)

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    N, W = MI()
    dp = [0] * (W+1)
    w = [0] * N
    v = [0] * N

    for i in range(N):
        w[i], v[i] = MI()

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

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def knapsack(N,W,weight,value):
    #初期化
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1): 
        dp[0][i]=0
    #DP
    for i in range(N):
        for w in range(W+1):
            if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
            else: #入る可能性はない
                dp[i+1][w]=dp[i][w]
    return dp[N][W]

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

print(knapsack(n,w,weight,value))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    N, W = MI()
    dp = [0] * (W+1)
    w = [0] * N
    v = [0] * N

    for i in range(N):
        w[i], v[i] = MI()

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

    print(max(dp))


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

inf = float("inf")
dp = [[-inf for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0

for i in range(N):
    weight = wv[i][0]
    value = wv[i][1]
    for w in range(W+1):
        # 重量に収まる場合のみ価値を加える
        if weight <= w:
            dp[i+1][w] = max(dp[i][w-weight] + value, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(max(dp[-1]))

Submission status: Accepted

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

dp = [[0]*(W+1) for _ in range(N+1)]
# dp[i][j] := i番目までの荷物を使って重さjの時の最大の価値
for i in range(N):
    for j in range(W+1):
        # i番目のitemを使わない場合
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        # i番目のitemを使う場合
        if j + items[i][0] > W:  # 重さがWを超えるならcontinue
            continue
        # 個数制限ありのパターン
        dp[i+1][j+items[i][0]] = max(dp[i][j]+items[i][1], dp[i+1][j+items[i][0]])
print(dp[N][W])