Problem:


Knapsack Problem

You have N kinds of items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

The total value of the items is as large as possible.

The items have combined weight at most W, that is capacity of the knapsack.

You can select as many items as possible into a knapsack for each kind.

Find the maximum total value of items in the knapsack.

Input

N W
v1 w1
v2 w2
:
vN wN

The first line consists of the integers N and W. In the following lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Constraints

 1 ≤ N ≤ 100
	

 1 ≤ vi ≤ 1000
	

 1 ≤ wi ≤ 1000
	

 1 ≤ W ≤ 10000
	

Sample Input 1

4 8
4 2
5 2
2 1
8 3

Sample Output 1

21

Sample Input 2

2 20
5 9
4 10

Sample Output 2

10

Sample Input 3

3 9
2 1
3 1
5 2

Sample Output 3

27



Sample input:
4 8
4 2
5 2
2 1
8 3


Sample output:
21

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N, W = list(map(int, input().split()))

values = []
weights = []

max_w = 0
weight_value_dict = defaultdict(int)
for i in range(N):
    v, w = list(map(int, input().split()))
    weight_value_dict[w] = max(v, weight_value_dict[w])
    values.append(v)
    weights.append(w)
# import IPython;IPython.embed()

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

for j in range(1, W+1):
    for weight, val in weight_value_dict.items():
        if j < weight:
            continue
        else:
            dp[j] = max(dp[j], dp[j-weight] + val)
print(dp[W])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N,W=map(int,input().split())
    v,w=[0]*N,[0]*N
    for i in range(N):
        v[i],w[i]=map(int,input().split())
    dp=[[0]*2*10**5 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]>=0:
                dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight-w[i]]+v[i])
                dp[i+1][weight]=max(dp[i+1][weight],dp[i+1][weight-w[i]]+v[i])
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

    N, W = iip()
    dp = [0] * (W+1)

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

    print(dp[-1])







#####################################################ライブラリ集ここから



def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        #print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            #print(r, l)
            l = x

    #print(l, r)
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:

def main():

    inf = 1<<29
    n,w = map(int,input().split())
    A = []
    for _ in range(n):
        a,b = map(int,input().split())
        A.append([a,b])
    dp = [0]*(w+1)
    for i in range(1,w+1):
        for j in range(n):
            if i-A[j][1]<0:continue
            dp[i] = max(dp[i],dp[i-A[j][1]]+A[j][0])
    res = 0
    for i in range(w+1):res = max(res,dp[i])
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, W = map(int, input().split())
    bag = []
    for _ in range(N):
        v, w = list(map(int, input().split()))
        bag.append((v, w))

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

    for i in range(N):
        iv, iw = bag[i]
        for w in range(iw, W+1):
            if dp[w-iw] == -1:
                continue
            else:
                dp[w] = max(dp[w-iw] + iv, dp[w])

    result = max(dp)

    print(result)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
item=[tuple(map(int,input().split())) for _ in range(N)]
#item=(v,w)
dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

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

Submission status: Accepted

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

V=[]
W=[]

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

DP=[[0]*(gw+1) for i in range(n+1)]

for i in range(n):
	for j in range(gw+1):
		if j-W[i]<0:
			DP[i+1][j]=DP[i][j]
		else:
			DP[i+1][j]=max(DP[i][j],DP[i+1][j-W[i]]+V[i])

print(DP[n][gw])

Submission status: Accepted

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

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

Submission status: Accepted

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


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


N, W = inpl()
VW = [inpl() for _ in range(N)]

dp = [0] * (W + 1)

for w in range(W + 1):
    for i in range(N):
        if w < VW[i][1]:
            continue

        dp[w] = max(dp[w], dp[w - VW[i][1]] + VW[i][0])

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

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

N, W = na()
weight = [0] * 110
value = [0] * 110
for i in range(N):
    v, w = na()
    weight[i], value[i] = w, v
dp = [[0] * 10010 for _ in range(110)]
for i in range(N):
    for w in range(W+1):
        if w >= weight[i]:
            dp[i+1][w] = max(dp[i+1][w-weight[i]] + value[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Accepted

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

dp=[-1]*(w+1)
dp[0]=0
for i in range(w+1):
    if dp[i]==-1:continue
    for V,W in vw:
        if i+W<=w:
            dp[i+W]=max(dp[i]+V,dp[i+W])
print(max(dp))

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,W = mi()
vl=[-1]*(W+1)
w_list=[]
for i in range(n):
    vt,wt =mi()
    if wt>W: continue
    vl[wt] = max(vl[wt], vt)
for k,i in enumerate(vl):
    if i!= -1:
        w_list.append(k)
dp = [0]*(W+1)
for i in w_list:
    w = i
    v = vl[w]
    for i in range(w,W+1):
        dp[i] = max(dp[i],dp[i-w]+v)
print(dp[W])

Submission status: Accepted

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

print(dp[W])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
vw = [input().split() for _ in range(n)]
vw = [(int(x[0]), int(x[1]))for x in vw]

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

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

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

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

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

Submission status: Accepted

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

v = [0] * (N)
w = [0] * (N)

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

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

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

ans = 0

for i in range(W + 1):
    ans = max(ans, dp[i])

print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
V = [0] * n
W = [0] * n
for i in range(n):
    vi, wi = map(int, input().split())
    V[i] = vi
    W[i] = wi
    
#dp = [[0]*(w+1) for _ in range(n+1)]
#dp[0] = [0]*(w+1)
dp = [-999999]*(w+1)
dp[0] = 0

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

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

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

Submission status: Accepted

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

v=[0]*N
w=[0]*N

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

dp=[0]*(W+1)

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

print(dp[W])

Submission status: Accepted

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

value, weight = [], []
for i in range(n):
    a, b = map(int,input().split())
    value.append(a)
    weight.append(b)

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

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

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

print(dp[n][w])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,W = LI()
    g = LIR(n)
    dp = [0]*(W+1)
    for i in range(n):
        v,w = g[i]
        for j in range(W):
            nj = j+w
            if nj <= W:
                nd = dp[j]+v
                if dp[nj] < nd:
                    dp[nj] = nd
    print(dp[W])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():

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

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

    print(max(dp[N]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


dp = [0] * (W + 1)

for i in range(1, W + 1):
    tmp = 0
    for v, w in VW:
        if i < w:
            continue
        tmp = max(tmp, dp[i - w] + v)

    dp[i] = tmp

print(dp[W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N,W = map(int,input().split(" "))
    dp = [0 for _ in range(W+1)]
    V = [tuple(map(int,input().split(" "))) for _ in range(N)]
    for i in range(W+1):
        for j in range(N):
            v,w = V[j]
            if i-w < 0:continue
            else:
                dp[i] = max(dp[i],dp[i-w]+v)
    print(max(dp))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, W = map(int, input().split())
    vw = [list(map(int, input().split())) for i in range(N)]

    dp = [0] * (W+1)

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

    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
VW = [list(map(int,input().split())) for i in range(N)]
Val = [VW[i][0] for i in range(N)]
Wei = [VW[i][1] for i in range(N)]

dp = [[0 for j in range(W+1)] for i in range(N+1)]
#dp[i][j]:i番目までで重さがjまででの価値の最大値

for i in range(1,N+1):
    for j in range(1,W+1):
        if j - Wei[i-1] >= 0:
            dp[i][j] = max(dp[i-1][j],dp[i][j-Wei[i-1]]+Val[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())
v = [0]
w = [0]
for _ in range(1,N+1):
    a,b = map(int,input().split())
    v.append(a)
    w.append(b)

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

print (dp[N][W])

Submission status: Accepted

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

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

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

ans = dp[N][W]
print(ans)

Submission status: Accepted

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

print(dp[N][W])

Submission status: Accepted

Solution code:
N, W = [int(i) for i in input().split(" ")]

vw = []
for i in range(N):
    vw.append([int(i) for i in input().split(" ")])
value = [i[0] for i in vw]
weight = [i[1] for i in vw]

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
def solve():
    n, w = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(n)]
    
    dp = [[float("inf") if i != 0 else 0 for i in range(w+1)] for j in range(n+1)]
    for i in range(w+1):
        dp[0][i] = 0

    for j in range(1, n+1):
        for k in range(1, w+1):
            if k - items[j-1][1] >= 0:
                dp[j][k] = max(dp[j-1][k], dp[j-1][k-items[j-1][1]] + items[j-1][0], dp[j][k-items[j-1][1]] + items[j-1][0])
            else:
                dp[j][k] = dp[j-1][k]

    return dp[-1][-1]

print(solve())

Submission status: Accepted

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

DP = [0] * (WE+1)
# DP = [0] * 20

# DP[j]: 重さjのときの価値の最大
DP[0] = 0

for i in range(N):
    for j in range(WE+1):
        if j + W[i] <= WE:
            DP[j+W[i]] = max(DP[j+W[i]], DP[j]+V[i])
    # print(DP)

print(DP[WE])

Submission status: Accepted

Solution code:
def run():
  N, W = map(int, input().split())
  vw = [list(map(int, input().split())) for n in range(N)]
  dp = [0]*(W+1)
  for w in range(W+1):
    for n in range(N):
      if w < vw[n][1]:
        continue
      else:
        dp[w] = max(dp[w], dp[w-vw[n][1]]+vw[n][0])
  print(dp[-1])
    
if __name__ == '__main__':
    run()

Submission status: Accepted

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

dp = [0]*(W+1)
for i in range(N):
    for j in range(W+1):
        if j < Weight[i]:
            continue
        dp[j] = max(dp[j], dp[j-Weight[i]]+Value[i])

print(dp[W])

Submission status: Accepted

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

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

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

print(dp[W])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
    n,wn=MI()
    dp=[0]*(wn+1)
    for _ in range(n):
        v,w=MI()
        for i in range(wn):
            if i+w>wn:break
            dp[i+w]=max(dp[i+w],dp[i]+v)
    print(dp[-1])

main()

Submission status: Accepted

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

# dp[i][j] := i番目の品物までで重さjとなるように選んだときの価値の最大値
# dp[i][j] := max(dp[i][j - w] + v, dp[i - 1][j])
#                   ~~~ 遷移前にすでにi番目の品物が入っている可能性を考慮
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 w[i] > j:  # 今選ぼうとしている品物の重さが制限jを超える場合には当然選べない
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i][j - w[i]] + v[i], dp[i - 1][j])
print(dp[N][W])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    n, w = list(map(int, input().strip().split()))
    dp = [[0] * (w+5) for _ in range(n+5)]
    items = [[] for _ in range(n)]
    for i in range(n):
        items[i] = list(map(int, input().strip().split()))
    for i in range(1, n+1):
        for j in range(1, w+1):
            if j-items[i-1][1] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-items[i-1][1]]+items[i-1][0])
    print(dp[n][w])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, W = iim()
    S = [iim() for i in range(N)]

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!



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

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

print(ans)

Submission status: Accepted

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

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

for _ in range(N):
    value,weight = map(int,input().split())
    for i in range(weight,W+1):
        if dp[i-weight] == -1:
            pass
        else:
            dp[i] = max(dp[i],dp[i-weight]+value)

ans = 0
for i in range(W+1):
    ans = max(ans,dp[i])

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

vw = []

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


dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
#i番目までで重さｊを作るときの最大価値
for i in range(N):
    for j in range(W+1):

        if vw[i][1] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j - vw[i][1]] + vw[i][0])


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