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:
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def MAP(): return [int(s) for s in input().split()]

"""
配列再利用によりdpの次元削減を行うパターン
"""

N, W = MAP()

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

for _ in range(N):
	v, w = MAP()
	for sum_w in range(W+1):
		#print(item, sum_w)
		if sum_w >= w:
			dp[sum_w] = max(dp[sum_w-w]+v, dp[sum_w])
		else:
			dp[sum_w] = dp[sum_w]

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

Submission status: Accepted

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

print(dp[N][W])

Submission status: Accepted

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


def knapsack(N, weight):
    dp = [0] * (weight + 1)
    for _ in range(N):
        v, w = map(int, readline().split())
        ww = w
        while ww <= weight:
            dp[ww] = max(dp[ww], dp[ww - w] + v)
            ww += 1
    return dp[-1]

if __name__ == "__main__":
    n_goods, weight = map(int, input().split())
    print(knapsack(n_goods, weight))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
Data = []
for _ in range(N):
    v,w = map(int,input().split())
    Data.append([v,w])
Data.sort(key=lambda x:x[1])
DP = [[0]*(W+1) for _ in range(N+1)]

for n in range(1,N+1):
    for w in range(1,W+1):
        tv,tw = Data[n-1]
        if tw <= w:
            DP[n][w] = max(DP[n][w],DP[n][w-tw]+tv)
        DP[n][w] = max(DP[n][w],DP[n-1][w])
print(DP[N][W])

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(max(dp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(100000)
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)

"""
def rec(pos, rest):
    if pos == N:
        return 0
    ans = 0
    for i in range(0, rest//w[pos]+1):
        ans = max(ans, rec(pos+1, rest-w[pos]*i)+v[pos]*i)
    return ans

print(rec(0, W))
"""

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
a=[0]*(w+1)
for i in range(n):
    s,t=map(int,input().split())
    for j in range(t,w+1):
        a[j]=max(a[j-t]+s,a[j])
print(a[-1])

Submission status: Accepted

Solution code:
_,W,*L=map(int,open(0).read().split())
l=[0]*(W+1)
for v,w in zip(*[iter(L)]*2):
	for i in range(w,W+1):
		l[i]=max(l[i],l[i-w]+v)
print(l[W])

Submission status: Accepted

Solution code:
def main():
    n,W=map(int,input().split())
    vw=[list(map(int,input().split())) for _ in [0]*n]
    memo=[0]*(W+1)
    for i in range(W):
        for v,w in vw:
            if i+w<=W:
                memo[i+w]=max(memo[i+w],memo[i]+v)
    print(max(memo))  
        
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys


if __name__ == "__main__":
    N, W = map(lambda x: int(x), input().split())
    items = [(0, 0)] * N
    for i in range(N):
        v, w = map(lambda x: int(x), input().split())
        items[i] = (v, w)
    table = [-sys.maxsize] * (W + 1)
    table[0] = 0

    for weight in range(W):
        for idx in range(N):
            if (-sys.maxsize == table[weight]):
                continue
            if (weight + items[idx][1] <= W):
                table[weight + items[idx][1]] = max(
                    table[weight + items[idx][1]], table[weight] + items[idx][0])

    print(max(table))

Submission status: Accepted

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

v = []
w = []

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

DP = [0]*(w_max + 1)

w_tmp = 0
while w_tmp <= w_max:
    v_tmp = DP[w_tmp]
    for i in range(n):
        if w[i] <= w_tmp:
            v_tmp = max(DP[w_tmp - w[i]] + v[i], v_tmp)
        DP[w_tmp] = v_tmp
    w_tmp += 1

print(DP[w_max])

Submission status: Accepted

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

for a in A:
  for j in range(a[1], W + 1):
    dp[j] = max(dp[j], dp[j - a[1]] + a[0])
print(max(dp))

Submission status: Accepted

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

dp=[-1]*(W+1)
dp[0]=0
for i in range(n):
    for j in range(W+1):
        if dp[j]!=-1 and j+w[i]<W+1:
            dp[j+w[i]]=max(dp[j]+v[i],dp[j+w[i]])

print(max(dp))

Submission status: Accepted

Solution code:
# DPL 1 C

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

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
length, weight = map(int, input().split(" "))
dp = [0 for n in range(weight + 1)]

for i in range(length):
    v, w = map(int, input().split(" "))

    dp[w] = max(v, dp[w])
    for j in range(weight):
        if dp[j] and j + w <= weight:
            dp[j + w] = max(dp[j] + v, dp[j + w])

print(max(dp))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,W=MAP()
VW=[]
for i in range(N):
    v,w=MAP()
    VW.append((v, w))

dp=list2d(N+1, W+1, 0)
for i in range(1, N+1):
    v,w=VW[i-1]
    for j in range(W+1):
        dp[i][j]=max(dp[i][j], dp[i-1][j])
        if j-w>=0:
            # i-1ではなく同じiからも遷移することが、重複して選ぶことに相当する
            dp[i][j]=max(dp[i][j], dp[i-1][j-w]+v, dp[i][j-w]+v)
print(dp[N][W])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
goods = []
for i in range(N):
    goods.append(list(map(int, input().split())))
dp = [[0 for i in range(W+1)]]
for n in range(0, N):
    dp.append([0])
    g = goods[n]
    for w in range(1, W+1):
        if w>=g[1]:
            dp[-1].append(max(dp[-1][w-g[1]]+g[0],dp[-2][w]))
        else:
            dp[-1].append(dp[-2][w])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    N, W = readi(2)
    vs, ws = zip(*readi(N, 2))
    dp = arr(N + 1, W + 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 - ws[i]] + vs[i]
                )
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

    print(dp[N][W])


if __name__ == "__main__":
    main()

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 heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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

Submission status: Accepted

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


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

dp = [0]*(w + 1)
for i in range(n):
    for j in range(w + 1):
        if j - info[i][1] < 0:
            continue
        else:
            dp[j] = max(dp[j], dp[j - info[i][1]] + info[i][0])
print(dp[w])

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

items = []

def knapsack(n):
    for i in range(0, n + 1):
        res = 0
        for v, w in items:
            if i >= w:
                res = max(res, dp[i - w] + v)
        dp[i] = res
    return dp[n]

line = input()
E, W = list(map(int, line.split()))
for _ in range(0, E):
    line = input()
    v, w1 = list(map(int, line.split()))
    items += [[v, w1]]
dp = [0] * (W + 1)
used = [False] * E
knapsack(W)
print(dp[W])

Submission status: Accepted

Solution code:
N, W = [int(x)for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))
dp = [0]*(W+1)
# print(items)
for i in range(N):
    v, w = items[i]
#     print(W,w-1)
    for j in range(w,W+1):
        dp[j] = max(dp[j],dp[j-w]+v)
       

print(dp[-1])

Submission status: Accepted

Solution code:
def solve(N, W, data):
    """
    >>> solve(4, 8, [(4, 2), (5, 2), (2, 1), (8, 3)])
    21
    >>> solve(2, 20, [(5, 9), (4, 10)])
    10
    >>> solve(3, 9, [(2, 1), (3, 1), (5, 2)])
    27
    """
    dp = [0] * (W + 1)

    for v, w in data:
        for i in range(w, W + 1):
            dp[i] = max(dp[i - w] + v, dp[i])

    return dp[-1]


if __name__ == '__main__':
    N, W = map(int, input().split())
    data = [tuple(map(int, input().split())) for _ in range(N)]
    print(solve(N, W, data))
    # import doctest
    # doctest.testmod(verbose=True)

Submission status: Accepted

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

L=[]
for i in range(N):
    v,w=map(int,input().split())
    for j in range(len(dp)):
        if j+w>W:
            pass
        else:
            if dp[j+w]<dp[j]+v:
                dp[j+w]=dp[j]+v
print(dp[W])

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
VW  = [list(map(int, input().split())) for _ in range(N)]
VW  = sorted(VW, key=lambda x:x[1])
# print(VW)
# exit()

dp = [0] * (W+1) # $B2ACM$N:GBgCM(B

for i in range(W):
    for v,w in VW:
        # print(i,v,w)
        if i+w <= W:
            dp[i+w] = max(dp[i+w], dp[i]+v) 

# print( (dp) )
print( max(dp) )

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
nap=[]
for i in range(N):
    nap.append(list(map(int,input().split())))
list_dp=[0]*(W+1)
for i in range(W):
    for j,k in nap:
        if i+k>W:continue
        else:list_dp[i+k]=max(list_dp[i+k],list_dp[i]+j)
print(list_dp[W])

Submission status: Accepted

Solution code:
def dump(dp, max_w):
    for i in range(max_w + 1):
        print('%3d' % dp[i], end='')
    print()

inf = 1 << 60
max_n, max_w = map(int, input().split())
v = [0] * (max_n + 1)
w = [0] * (max_n + 1)
for i in range(1, max_n + 1):
    v[i], w[i] = map(int, input().split())

dp = [0] * (max_w + 1)

for n in range(1, max_n + 1):
    for i in range(max_w + 1 - w[n]):
        dp[i+w[n]] = max(dp[i+w[n]], dp[i] + v[n])
    #dump(dp, max_w)

print(dp[max_w])

Submission status: Accepted

Solution code:
class DP2D(object):

    def __init__(self, item_n: int, border: int, initializer: int = 0):
        self.item_n = item_n
        self.border = border
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

    def __str__(self):
        return "\n".join(list(map(lambda l:
                                  " ".join(list(map(str, l)))
                                  , self.table)))

    def __repr__(self):
        return "DynamicProgramming object:\n" + \
               "item_n: " + str(self.item_n) + ", border: " + str(self.border) + "\n" + \
               "table:\n" + self.__str__()

    def solve(self, expr: callable) -> list:
        raise NotImplementedError

    def fill_0_idx_with(self, value: int) -> "DP2D":
        self.table[0] = [value for _ in range(self.item_n + 1)]
        for i in range(1, self.border + 1):
            self.table[i][0] = value
        return self


class DP2DOptimizer(DP2D):

    def __init__(self, item_n: int, border: int, obj_coef: list, sbj_coef: list, initializer: int = 0):
        super(DP2DOptimizer, self).__init__(item_n, border, initializer=initializer)

        if len(obj_coef) == self.item_n:  # to 1-base
            obj_coef = [0] + obj_coef
        self.obj_coef = obj_coef

        if len(sbj_coef) == self.item_n:
            sbj_coef = [0] + sbj_coef
        self.sbj_coef = sbj_coef

    def solve(self, expr: callable) -> list:
        for weight_lim in range(1, self.border + 1):
            for item_idx in range(1, self.item_n + 1):
                self.table[weight_lim][item_idx] = expr(weight_lim, item_idx)

        return self.table

    def knapsack_expr(self, weight_lim: int, item_idx: int) -> int:
        res = self.table[weight_lim][item_idx - 1]
        if weight_lim - self.sbj_coef[item_idx] >= 0:
            res = max(res, self.table[weight_lim - self.sbj_coef[item_idx]][item_idx] + self.obj_coef[item_idx])
        return res


if __name__ == '__main__':
    N, W = map(int, input().split())
    v, w = [], []
    for _ in range(N):
        buff = [int(i) for i in input().split()]
        v.append(buff[0])
        w.append(buff[1])
    dp = DP2DOptimizer(N, W, v, w)
    print(dp.solve(dp.knapsack_expr)[W][N])

Submission status: Accepted

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

dp = [0] * (W + 1)

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

print(dp[W])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan  5 09:20:15 2019

@author: maezawa
"""

n, maxw = list(map(int, input().split()))
v = [0]*(n+1)
w = [0]*(n+1)
for i in range(1, n+1):
    vi, wi = list(map(int, input().split()))
    v[i] = vi
    w[i] = wi
    
dp = [0]*(maxw+1)
for i in range(1,maxw+1):
    candidates = [dp[i-w[j]]+v[j] 
                    for j in range(n+1) if i-w[j] >= 0]
    dp[i] = max(candidates)
    #print(i, *dp, sep = '\n')
print(dp[maxw])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DPL_1_C: Combinatorial - Knapsack Problem

from operator import itemgetter


def max_value(total_weight, items):
    values = [0] * (total_weight+1)

    for v, w in sorted(items, key=itemgetter(1)):
        for i in range(w, total_weight+1):
            values[i] = max(values[i], values[i-w] + v)

    return values[-1]


def run():
    n, t = [int(i) for i in input().split()]
    vs = []

    for _ in range(n):
        v, w = [int(i) for i in input().split()]
        vs.append((v, w))

    print(max_value(t, vs))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

# value[u] = 容量uのときの最大価値
value = {0: 0}

for u in range(1, W + 1):
    value[u] = max([value[u - w] + v for v, w in item if u >= w] \
                 + [value[u - 1]])
print(value[W])

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
wt=[0]*n
val=[0]*n
for x in range(n):
    va,wei=map(int,input().split())
    wt[x]=wei
    val[x]=va
    
def knapsack(n,W,wt,val):
    memo=[0]*(W+1)
    for w in range(1,W+1):
        for i in range(n):
            if wt[i]<=w:
                memo[w]=max(memo[w-wt[i]]+val[i],memo[w])                
    return memo[W]
print(knapsack(n,W,wt,val))

Submission status: Accepted

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

dp = {(0, j):0 for j in range(W + 1)}

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

print(dp[(N, W)])

Submission status: Accepted

Solution code:

def knapsack(n,W,v,w):
	dp=[[0 for x in range(W+1)] for x in range(n+1)]
	for i in range(n):
		vl = v[i]
		wt = w[i]
		for j in range(W+1):
			if j < w[i]:
				dp[i+1][j]=dp[i][j]
			else:
				dp[i+1][j]=max(dp[i][j],max(dp[i][j-wt]+vl,dp[i+1][j-wt]+vl))
	return dp[n][W]

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())
print(knapsack(n,W,v,w))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


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

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

for loop 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("%d"%(ans))

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
val_i = [0]*(W+1)
for i in range(1,N+1):
    v,w = map(int, input().split())
    copy = val_i[:] ##i-1번째줄의 val_i
    for j in range(1,W+1):
        if (w <= j):
            val_i[j] = max(copy[j], (val_i[j-w] + v)) ##0개선택시 copy[j], 
                                               ##1개 이상 선택시 val_i[j]와(val_i[j-w]+v)는 동일값
            #choice = [k*v + copy[j-k*w]for k in range(j//w+1)]
            #val_i[j] = max(choice)                            --> time limit exceeded
            
            ##val_i[j] = max((v + copy[j-w]), copy[j])   --> formal answer
print(val_i[-1])

Submission status: Accepted

Solution code:
n, w = [int(i) for i in input().split()]
V, W = zip(*[[int(i) for i in input().split()] for j in range(n)])

dp = [[0]*(w+1) for i 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][j-W[i]]+V[i], 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,wmax=map(int,input().split(" "))
v=[]
w=[]
ans=[0]*(wmax+1)
for i in range(n):
    vv,ww=map(int,input().split(" "))
    v.append(vv)
    w.append(ww)
for i in range(n):
    for j in range(w[i],wmax+1):
        ans[j]=max([ans[j],ans[j-w[i]]+v[i]])
print(ans[-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 for w in range(W+1)] for i in range(N+1)]
for w in range(W+1):
    dp[0][w] = 0
for i in range(N):
    for w in range(W+1):
        if items[i][1] <= w:
            dp[i+1][w] = max(dp[i+1][w-items[i][1]] + items[i][0], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Runtime Error

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(b,W+1,b):
		x = a + dp[j-b]
		if x >= dp[j]:
			dp = x

print(W+1)

Submission status: Runtime Error

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(b,W+1,b):
		x = a + dp[j-b]
		if x >= dp[j]:
			dp[j] = x

print(dp[W+1])

Submission status: Runtime Error

Solution code:
import bisect
import collections
import heapq
import itertools
import math
import string
import sys
from itertools import chain, takewhile

import numpy as np


def read(
    f, *shape, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        return f("".join(takewhile(lambda c: c not in whitespaces, it)).strip())

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def arr(*shape, fill_value=0):
    if isinstance(shape[0], int):
        return np.full(shape, fill_value).tolist()
    return np.full_like(shape[0], fill_value).tolist()


def debug(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )

def main():
    N, W = read(int, 2)
    values = arr(N)
    weights = arr(N)
    for i in range(N):
        values[i], weights[i] = read(int, 2)

    dp = arr(W + 1, fill_value=0)
    for i in range(N):
        for w in range(weights[i], W + 1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    print(dp[W])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


n, total_wait = map(int, readline().split())
value_wait = [list(map(int, readline().split())) for _ in range(n)]
value_wait.sort(key=operator.itemgetter(1), reverse=True)

dp = [0] * (total_wait + 1)

for ni, (v, w) in enumerate(value_wait):
    for tw in range(w, total_wait + 1):
        if dp[tw] < dp[tw - w] + v:
            dp[tw] = dp[tw - w] + v
print(dp[-1])

Submission status: Runtime Error

Solution code:
# coding: utf-8

from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from __future__ import absolute_import

def array2d(row, col, init = None):
    return [[init for _ in range(col)] for _ in range(row)]

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

dpt = array2d(N + 1, W + 1)

def dp(i, j):
    if dpt[i][j] is not None:
        return dpt[i][j]
    if i == 0:
        dpt[i][j] = 0
        return 0
    if j < w[i-1]:
        dpt[i][j] = dp(i-1, j)
        return dpt[i][j]
    dpt[i][j] = max(dp(i-1, j), dp(i, j-w[i-1]) + v[i-1])
    return dpt[i][j]

print(dp(N, W))

Submission status: Runtime Error

Solution code:
# coding: utf-8

from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from __future__ import absolute_import

def array2d(row, col, init = None):
    return [[init for _ in range(col)] for _ in range(row)]

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

dpt = array2d(N + 1, W + 1)

def dp(i, j):
    if dpt[i][j] is not None:
        return dpt[i][j]
    if i == 0:
        dpt[i][j] = 0
        return 0
    if j < w[i-1]:
        dpt[i][j] = dp(i-1, j)
        return dpt[i][j]
    dpt[i][j] = max(dp(i-1, j), dp(i, j-w[i-1]) + v[i-1])
    return dpt[i][j]

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

Submission status: Runtime Error

Solution code:
def dfs_dp(w,v,n,W,index,dp):
    if (dp[index][W] != -1):
        return dp[index][W]
    if index==n: return 0
    if W<w[index]: return dfs_dp(w,v,n,W,index+1,dp)

    ret=max(dfs_dp(w,v,n,W,index+1,dp),v[index]+dfs_dp(w,v,n,W-w[index],index+1,dp),v[index]+dfs_dp(w,v,n,W-w[index],index,dp))

    dp[index][W]=ret
    return ret


a,b=input().split()
N,W=int(a),int(b)

w=[]
v=[]
dp=[[-1 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    a,b=input().split()
    v.append(int(a))
    w.append(int(b))

print(dfs_dp(w,v,N,W,0,dp))

Submission status: Runtime Error

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

    print(max(dp))

Submission status: Runtime Error

Solution code:
n,w = map(int, input().split())
values = [0]
weights = [0]
counter=0
rest = 0

for i in range(n):
    v,weight = map(int, input().split())
    values.append(v)
    weights.append(weight)

dp=[[0 for i in range(w+1)]for j in range(v+1)]
for i in range(1, n+1):
    for j in range(1, w+1):
        rest = j
        counter = 0
        if(j >= weights[i]):
            while(rest-weights[i]>=0):
                counter = counter+1
                rest = rest - weights[i]
                dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i-1][j-weights[i]*counter]+values[i]*counter)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][-1])