Problem:


0-1 Knapsack Problem

You have N 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.

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 5
4 2
5 2
2 1
8 3

Sample Output 1

13

Sample Input 2

2 20
5 9
4 10

Sample Output 2

9



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


Sample output:
13

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

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][sum_w - w] + v)
        else:
            dp[i + 1][sum_w] = dp[i][sum_w]

print(dp[N][W])

Submission status: Accepted

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, W = i_l()

values = []
weigth = []
for _ in range(N):
    v, w = i_l()
    values.append(v)
    weigth.append(w)

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

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


print(dp[N][W])

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B


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

    d = {}

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

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

    print(max(dp[N]))

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-1][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:
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[i]: 重さj以下での価値の最大値
    dp = [0] * (W+1)
    for i in range(N):
        v, w = vw[i]
        if w <= W:
            for j in range(W-w, -1, -1):
                dp[w+j] = max(dp[w+j], dp[j] + v)
    print(dp[W])

if __name__ == "__main__":
    main()

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][j-W[i]]+V[i])

print(DP[n][gw])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(15000)
n,w = map(int,sys.stdin.readline().split())
dp = [0]*(w+1)
for i in range(n):
  vi,wi = map(int,sys.stdin.readline().split())
  for j in range(w+1)[::-1]:
    if 0 <= j-wi and j-wi <= w:
      #print(j-wi,vi)
      dp[j] = max(dp[j],dp[j-wi]+vi)
print(dp[-1])

Submission status: Accepted

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

for i in range(n):
    a,b = map(int,input().split())
    for j in range(w+1):
        if b > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j] , dp[i][j-b] + a)
            
print(dp[n][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][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:
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 _ in range(N + 1)]

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

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

Submission status: Accepted

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

# dp[i + 1][w] := i番目までの品物の中から重さがwを超えないように選んだときの、価値の総和の最大値
# 品物を選ぶとき: dp[i + 1][w] = dp[i][w - weigth[i]] + value[i]
# 品物を選ばないとき: dp[i + 1][w] = dp[i][w]

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

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

inf = float("inf")
dp = [[-inf for _ in range(W + 1)] for j in range(N + 1)]
# print(dp)

for w in range(W):
    dp[0][w] = 0

for i in range(N):
    for w in range(W + 1):
        if w >= goods[i][1]:
            dp[i + 1][w] = max(dp[i][w - goods[i][1]] + goods[i][0], 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())
items = [list(map(int, input().split())) for _ in range(N)]
Ws = [0]*(N+1)
Ws[0] = [0]*(W+1)

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

Submission status: Accepted

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

VW = tuple(map(int, input().split()) for _ in range(N))

dp = [0] * (W + 1)
for v, w in VW:
    for i in reversed(range(w, W + 1)):
        dp[i] = max(dp[i], dp[i - w] + v)

ans = dp[W]
print(ans)

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()
a = [tuple(int(i) for i in input().split()) for _ in range(n)]
dp=[0]*(w+1)
for v,ww in a:
    for i in range(ww,w+1)[::-1]:
        dp[i] = max(dp[i], dp[i-ww]+v)
print(dp[w])

Submission status: Accepted

Solution code:
n,lim = 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]*(lim+1) for _ in range(n+1)]
for i in range(n):
  for j in range(lim+1):
    if w[i] > j:
      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][lim])

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) for i in range(n)]

for i in range(n):
    for j in range(w+1):
        if i==0 and vw[i][1]<=w:
            dp[i][0]=0
            dp[i][vw[i][1]]=vw[i][0]
            break
        #入れない場合
        dp[i][j]=max(dp[i][j],dp[i-1][j])
        #入れる場合
        if not (0<=j-vw[i][1]<=w and dp[i-1][j-vw[i][1]]>=0):continue
        dp[i][j]=max(dp[i-1][j-vw[i][1]]+vw[i][0],dp[i][j])

print(max(dp[-1]))

Submission status: Accepted

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

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]

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

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

Submission status: Accepted

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

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

# print(*dp, sep='\n')
print(dp[N][W])

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 24 00:01:43 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, W = na()
vw = nan(n)

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

for i in range(n):
    v, w = vw[i]
    for j in range(W + 1):
        if j - w < 0:
            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])

Submission status: Accepted

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

print(dp[N][W])

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

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, -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:
# coding: utf-8
# Your code here!
s = input().split()
N = int(s[0])#num
W = int(s[1])#weight
values = []
weights = []

for n in range(N):
    s = input().split()
    values.append(int(s[0]))
    weights.append(int(s[1]))

max_value = [0 for i in range(W)]
contents = [[] for i in range(W)]

for i in range(W):
    if i == 0:
        buf = 0
    else:
        buf = max_value[i-1]
    for j in range(N):
        if i+1 < weights[j]:continue
        if i+1 == weights[j]:
            if buf < values[j]:
                contents[i] = [j]
                buf = values[j]
        if j in contents[i-weights[j]]:continue
        if buf < max_value[i-weights[j]]+values[j]:
            contents[i] = contents[i-weights[j]] + [j]
            buf = max_value[i-weights[j]]+values[j]
        
    if buf == max_value[i-1]:
        contents[i] = contents[i-1]
    max_value[i] = buf
    
print(max_value[W-1])

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)


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

Submission status: Accepted

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

Submission status: Accepted

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

# dp[i][j]: i番目までの商品から重さjまでの範囲で選んだ場合の価値の最大値
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    v_i, w_i = vw[i]
    for j in range(w+1):
        # 選ぶ場合
        if j - w_i >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w_i] + v_i)
        # 選ばない場合
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

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

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

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

for i in range(1,N+1):
  for j in range(1,W+1):

    if j<w[i-1]:
      nap[i][j]=nap[i-1][j]
    else:
      nap[i][j]=max(nap[i-1][j],nap[i-1][j-w[i-1]]+v[i-1])

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

Submission status: Accepted

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

print(dp[N][W])

Submission status: Accepted

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

value, weight = [], []

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

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][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,w1=map(int,input().split())
dp=[]
for i in range(n):
    temp=[]  
    for j in range(w1+1):
          temp.append(-1)
    dp.append(temp)
# dp=[[-1]*(w1+1)]*n
dp.append([0]*(w1+1))
# print(dp)
w=[]
v=[]
for i in range(n):
  a,b=map(int,input().split())
  v.append(a)
  w.append(b)

for i in range(n-1,-1,-1):
  for j in range(w1+1):
    # print(i,j,dp[i][j],dp[i+1][j],dp[i+1][j-w[i]],v[i])    
    
    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)
print(dp[0][w1])

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

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, W = MAP()
    VW = [LIST() for i in range(N)]

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

    print(dp[0][W])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for i in range(N)]
# for v, w in L:

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

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

Submission status: Accepted

Solution code:
from functools import lru_cache

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 j in range(N + 1)]

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

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()

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

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][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(" "))
    V = []
    dp = [0 for _ in range(W+1)]
    for _ in range(N):
        V.append(tuple(map(int,input().split(" "))))
    V =  tuple(V)
    for i in range(N):
        tmp = list(dp)
        v,w = V[i]
        for j in range(W+1):
            if 0 <= j+w <= W:
                tmp[j+w] = max(dp[j+w],dp[j]+v)
        dp = list(tmp)
    print(dp[-1])
if __name__ == "__main__":
    main()

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

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

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