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:
import copy
length, capacity = map(int, input().split(" "))
nap = []
for _ in range(length):
    v, w = map(int, input().split(" "))
    nap.append([v, w])
dp = [0 for n in range(capacity + 1)]

for i, (v, w) in enumerate(nap):
    new_dp = dp[::]
    if w <= capacity:
        new_dp[w] = max(v, dp[w])
    for j, now_v in enumerate(dp):
        if now_v and j + w <= capacity:
            new_dp[j + w] = max(dp[j + w], now_v + v)
    dp = new_dp
answer = 0
for v in dp:
    answer = max(answer, v)
print(answer)

Submission status: Accepted

Solution code:
#Nはアイテム数、Wはナップサックサイズ
N,W = map(int,input().split())
#dpテーブルを作成（初期値は0）
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

#print(dp)

#N個のアイテムのvalueとweightを入れるリストを用意する
value = []
weight = []
for i in range(N):
    v,w = map(int,input().split())
    value.append(v)
    weight.append(w)

#print(values)
#print(weights)

#アイテムは１個目からN個まで、重さのレンジは0からWまで
for i in range(1,N+1):
    for j in range(W+1):
        if j >= weight[i-1]: #iは1から始めているので、weightやvalueのリストを参照するときは添字を1つ下げる
            dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i-1][j-weight[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[N][W])

Submission status: Accepted

Solution code:
INF = 10 ** 12

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

items =[] * N

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

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

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
N, W =map(int,input().split())
 
INF = 10**10
#dp = [[INF]*100000]*(N*100)#余分に
dp = [[0 for i in range(W+1)] for j in range(N+1)]

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

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


print(dp[N][W])

Submission status: Accepted

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

for _ in range(N):
    tmp_v, tmp_w = (int(x) for x in input().split())
    value.append(tmp_v)
    weight.append(tmp_w)

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

for n in range(N):
    for w in range(W+1):
        if w >= weight[n]:
            dp[n+1][w] = max(dp[n][w-weight[n]] + value[n], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]
print(dp[N][W])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def knappack(N, W, vs, ws):
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(W, ws[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - ws[i]] + vs[i])
            
    return dp[-1]
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    Nstr, Wstr = line.split()
    N, W = int(Nstr), int(Wstr)
    vs, ws = [], []
    for i in range(N):
        line = sys.stdin.readline()
        v, w = line.split()
        v, w = int(v), int(w)
        vs.append(v)
        ws.append(w)
    sys.stdout.write(str(knappack(N, W, vs, ws)))
    sys.stdout.write('\n')

Submission status: Accepted

Solution code:
from sys import stdin
import operator
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 _ in range(n + 1)]
for ni, (v, w) in enumerate(value_wait):
    for tw in range(w, total_wait + 1):
        dp[ni + 1][tw] = max(dp[ni][tw], dp[ni][tw - w] + v)
print(dp[-1][-1])

Submission status: Accepted

Solution code:
N, maxW = 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]*(maxW+1) for _ in range(N+1)]
for i in range(N):
    for j in range(maxW+1):
        if j < W[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-W[i]] + V[i])
print(dp[N][maxW])

Submission status: Accepted

Solution code:
N, maxW = 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]*(maxW+1) for _ in range(2)]
for i in range(N):
    for j in range(maxW+1):
        if j < W[i]:
            dp[(i+1)&1][j] = dp[i&1][j]
        else:
            dp[(i+1)&1][j] = max(dp[i&1][j], dp[i&1][j-W[i]] + V[i])
print(dp[N&1][maxW])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N,W = map(int,input().split())
v = [0] * (N+1)
w = [0] * (N+1)

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
n, w = map(int, raw_input().split())
goods = [map(int, raw_input().split()) for i in range(n)]
dp = [0]*(w+1)
for g in goods:
    ndp = [0]*(w+1)
    for i in range(w+1):
        if i - g[1] < 0:
            ndp[i] = dp[i]
        else:
            ndp[i] = max(dp[i-g[1]] + g[0], dp[i])
    dp = ndp
print dp[w]

Submission status: Accepted

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
"""

from __future__ import division
from sys import stdin, maxint

def knapsack(N, W, infos):
	dp = [0] * (W + 1)
	for i in range(N):
		for j in range(W, infos[i][1] - 1, -1):
			dp[j] = max(dp[j], dp[j - infos[i][1]] + infos[i][0])

	return dp[W]


if __name__ == '__main__':
    N, W = map(int, stdin.readline().strip().split())
    infos = []
    for _ in range(N):
    	v, w = map(int, stdin.readline().strip().split())
    	infos.append((v, w))
    print(knapsack(N, W, infos))

Submission status: Accepted

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
"""

from __future__ import division
from sys import stdin, maxint

# Based on the solution you choose,
def knapsack(N, W, infos):
	dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(W + 1):
			if j >= infos[i - 1][1]:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - infos[i - 1][1]] + infos[i - 1][0])
			else:
				dp[i][j] = dp[i - 1][j]


	return dp[N][W]


if __name__ == '__main__':
    N, W = map(int, stdin.readline().strip().split())
    infos = []
    for _ in range(N):
    	v, w = map(int, stdin.readline().strip().split())
    	infos.append((v, w))
    print(knapsack(N, W, infos))

Submission status: Accepted

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

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

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


def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]

    if i == N:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])

    dp[i][j] = res
    return res

print(rec(0, W))

Submission status: Accepted

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

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

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

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

print(dp[0][W])

Submission status: Accepted

Solution code:
a = map(int, raw_input().split())
N = a[0]
W = a[1]

class Item(object):
    def __init__(self,v,w):
        self.v = v
        self.w = w

Items = [Item(0,0)]
for i in xrange(N):
    a = map(int,raw_input().split())
    Items.append(Item(a[0],a[1]))

C = [ [0] * (W+1) for _ in xrange(N+1)]
G = [ [''] * (W+1) for _ in xrange(N+1)] 

def knapsack():
    for i in xrange(1,N+1):
        for w in xrange(1,W+1):
            if Items[i].w <= w:
                if Items[i].v + C[i-1][w-Items[i].w] > C[i-1][w]:
                    C[i][w] = Items[i].v + C[i-1][w-Items[i].w]
                    G[i][w] = 'DIAGONAL'
                else:
                    C[i][w] = C[i-1][w]
                    G[i][w] = 'TOP'
            else:
                C[i][w] = C[i-1][w]
                G[i][w] = 'TOP'

    print C[N][W]
    return 0

knapsack()

Submission status: Accepted

Solution code:
# coding: utf-8

from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from __future__ import absolute_import
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect

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

print(dp(N, W))

Submission status: Accepted

Solution code:
N,W=map(int,raw_input().split())
vw=[map(int,raw_input().split()) for i in xrange(N)]
dp=[[0]*(W+1) for _ in xrange(N+1)]
for i in xrange(N):
    for j in xrange(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][j-vw[i][1]]+vw[i][0])
print(dp[N][W])

Submission status: Accepted

Solution code:
l = input().split()
N = int(l[0])
W = int(l[1])
products = [] # [[value, weigth]]
for i in range(N):
    l = input().split()
    products.append([int(l[0]),int(l[1])])

DP = [0 for _ in range(W+1)]
p_flag = [[False for _ in range(N)] for _ in range(W+1)]
for i in range(N):
    new_DP = [DP[j] if j < products[i][1] else 0 for j in range(W+1)]
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            new_DP[j] = product_in
        else:
            new_DP[j] = DP[j]
    DP = [v for v in new_DP]
print(DP[W])

Submission status: Accepted

Solution code:
N, W = map(int, raw_input().split())
v = [0]*N
w = [0]*N
for i in xrange(N):
    v[i], w[i] = map(int, raw_input().split())
dp = [0] * (W+1)
for i in xrange(N):
    for j in xrange(W, w[i]-1, -1):
        dp[j] = max(dp[j-w[i]] + v[i], dp[j])
print dp[W]

Submission status: Accepted

Solution code:
l = input().split()
N = int(l[0])
W = int(l[1])
products = [] # [[value, weight]]
for i in range(N):
    l = input().split()
    products.append([int(l[0]),int(l[1])])

DP = [0 for _ in range(W + 1)]
p_flag = [[False for _ in range(N)] for _ in range(W + 1)]
for i in range(N):
    new_DP = [DP[j] if j < products[i][1] else 0 for j in range(W + 1)]
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            new_DP[j] = product_in
        else:
            new_DP[j] = DP[j]
    DP = [v for v in new_DP]
print(DP[W])

Submission status: Accepted

Solution code:
l = input().split()
N = int(l[0])
W = int(l[1])

v = []
w = []
for i in range(N):
    l = input().split()
    v.append(int(l[0]))
    w.append(int(l[1]))


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

for j in range(1, N + 1):
    for k in range(1, W + 1):
        if w[j-1] <= k:
            if v[j-1] + c[j-1][k-w[j-1]] > c[j - 1][k]:
                c[j][k] = v[j-1] + c[j-1][k-w[j-1]]
            else:
                c[j][k] = c[j-1][k]
        else:
            c[j][k] = c[j-1][k]
print(c[N][W])

Submission status: Accepted

Solution code:
n,maxw = map(int, input().split())
arr = [[-1 for i in range(maxw+1)] for j in range(n+1)]
arr[0][0] = 0
ans = 0
for i in range(n):
    v,w = map(int, input().split())
    for j in range(maxw):
        arr[i+1][j] = max(arr[i+1][j], arr[i][j])
        if j + w <= maxw and arr[i][j] >= 0:
            arr[i+1][j+w] = max(arr[i][j+w], arr[i][j] + v)
            ans = max(arr[i+1][j+w], ans)
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':

    """prepairing"""

    amount = input()
    factor = amount.split(' ')
    N = int(factor[0])
    W = int(factor[1])

    v = []
    w = []
    v.append(0)
    w.append(0)
    inputs = []

    d = []

    for i in range(W + 1):
        temp = [0] * (N + 1)
        d.append(temp)

    """getting inputs and initializing arrays"""

    for x in range(N):
        inputs[:] = []
        inputs = input().split(' ')
        v.append(int(inputs[0]))
        w.append(int(inputs[1]))



    """make array"""

    for row in range(W + 1):
        for column in range(N + 1):
            if row != 0 and column != 0:
                if w[column] > row:
                    d[row][column] = d[row][column - 1]
                else:
                    d[row][column] = max(d[row - w[column]][column - 1] + v[column], d[row][column - 1])

    print(d[W][N])

Submission status: Accepted

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

Submission status: Accepted

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

for _ in range(n):
    v, w = map(int, input().split())
    for k in range(cap - w, -1, -1):
        tmp_before_v = dp[k]
        if tmp_before_v == None:
            continue
        tmp_after_v, new_v = dp[k + w], tmp_before_v + v
        if tmp_after_v == None or tmp_after_v < new_v:
            dp[k + w] = new_v

print(max(filter(None, dp)))

Submission status: Accepted

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

for _ in range(n):
    v, w = map(int, input().split())
    for k in range(cap - w, -1, -1):
        new_v = dp[k] + v
        if dp[k + w] < new_v:
            dp[k + w] = new_v

print(max(dp))

Submission status: Accepted

Solution code:
n,w=map(int,raw_input().split())
vw=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[[0]*(w+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(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][j-vw[i][1]]+vw[i][0])
print(dp[n][w])

Submission status: Accepted

Solution code:
num,weight = (int(n) for n in input().split(" "))
query = []
for n in range(num):
    query.append([int(n) for n in input().split(" ")])
nap = [[0 for n in range(weight + 1)] for m in range(num + 1)]
for n in range(num):
    for w in range(weight + 1):

        if query[n][1] <= w:
            nap[n + 1][w] = max(nap[n][w-query[n][1]] + query[n][0],nap[n][w])
        else:
            nap[n + 1][w] = nap[n][w]
print(nap[num][weight])

Submission status: Accepted

Solution code:
n,w=map(int,raw_input().split())
vw=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[[0]*(w+1) for _ in xrange(2)]
for i in xrange(n):
    for j in xrange(w+1):
        if j<vw[i][1]:
            dp[(i+1)&1][j]=dp[i&1][j]
        else:
            dp[(i+1)&1][j]=max(dp[i&1][j],dp[i&1][j-vw[i][1]]+vw[i][0])
print(dp[n&1][w])

Submission status: Accepted

Solution code:
n,w=map(int,raw_input().split())
vw=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[0]*(w+1)
for i in xrange(n):
    for j in xrange(w,vw[i][1]-1,-1):
        dp[j]=max(dp[j],dp[j-vw[i][1]]+vw[i][0])
print(dp[w])

Submission status: Accepted

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

def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i == N:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j),rec(i + 1, j - w[i]) + v[i])
    dp[i][j] = res
    return res

print(str(rec(0, W)))

Submission status: Accepted

Solution code:
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

dp=[[False for j in range(W+1)] for i in range(n+1)]

def solve(i,w):
	if dp[i][w]==False:
		if i==n:
			res=(0)
		elif w-l[i][0]<0:
			res=(solve(i+1,w))
		else:
			a=solve(i+1,w)
			b=l[i][1]+solve(i+1,w-l[i][0])
			if b>a:
				res=(b)
			else:
				res=(a)
		dp[i][w]=res
		return(res)
	else:
		return(dp[i][w])

print(solve(0,W))

Submission status: Accepted

Solution code:
value=[0]
weight=[0]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n][W])

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)]
goods=[]
for i in range(N):
    v,w=map(int,input().split())
    goods.append([v,w])

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

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

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            if item.w <= cp:
                # if item.v + values[i - 1][cp - item.w] > values[i - 1][cp]:
                #     values[i][cp] = item.v + values[i - 1][cp - item.w]
                #     # chosen[i][cp] = True
                # else:
                values[i][cp] = max(values[i - 1][cp], item.v + values[i - 1][cp - item.w])
                # chosen[i][cp] = False
            else:
                values[i][cp] = values[i - 1][cp]
                # chosen[i][cp] = False
    return values[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', 'v w')
    # item_list = [Item(v=-1, w=-1)] + [Item(v=int(v), w=int(w)) for v, w in items]
    item_list = [Item(v=int(v), w=int(w)) for v, w in items]

    # chosen = [[False] * (real_cp + 1) for _ in range(c_items + 1)]
    values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve()
    print(ans)

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            if item.w <= cp:
                values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
            else:
                values[i][cp] = values[i - 1][cp]
    return values[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', 'v w')
    item_list = [Item(v=int(v), w=int(w)) for v, w in items]

    values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve()
    print(ans)

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            if item.w <= cp:
                values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
            else:
                values[i][cp] = values[i - 1][cp]
    return values[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', 'v w')
    item_list = (Item(v=int(v), w=int(w)) for v, w in items)

    values = tuple([0] * (real_cp + 1) for _ in range(c_items + 1))
    ans = solve()
    print(ans)

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            if item.w <= cp:
                values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
            else:
                values[i][cp] = values[i - 1][cp]
    return values[-1][-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', 'v w')
    item_list = (Item(v=int(v), w=int(w)) for v, w in items)

    values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve()
    print(ans)

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


def solve():
    for i, item in enumerate(item_list, 1):
        for cp in range(1, real_cp + 1):
            # capacity allows putting in, calculate value
            if item.w <= cp:
                values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
            # can't put in, skip current item
            else:
                values[i][cp] = values[i - 1][cp]

    return values[c_items][real_cp]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('v', 'w'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve()
    print(ans)

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


# def solve():
#     for i, item in enumerate(item_list, 1):
#         for cp in range(1, real_cp + 1):
#             # capacity allows putting in, calculate value
#             if item.w <= cp:
#                 values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
#             # can't put in, skip current item
#             else:
#                 values[i][cp] = values[i - 1][cp]
#
#     return values[c_items][real_cp]


def solve_2():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.v, item.w
        for cp in range(real_cp - w, -1, -1):
            dp[cp + w] = max(dp[cp + w], dp[cp] + v)

    return dp[-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('v', 'w'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    # values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve_2()
    print(ans)

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


# def solve():
#     for i, item in enumerate(item_list, 1):
#         for cp in range(1, real_cp + 1):
#             # capacity allows putting in, calculate value
#             if item.w <= cp:
#                 values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
#             # can't put in, skip current item
#             else:
#                 values[i][cp] = values[i - 1][cp]
#
#     return values[c_items][real_cp]


def solve_2():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.v, item.w
        for cp in range(real_cp - w, -1, -1):
            dp[cp + w] = max(dp[cp + w], dp[cp] + v)

    return dp.pop()


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('v', 'w'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    # values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    ans = solve_2()
    print(ans)

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


# def solve():
#     for i, item in enumerate(item_list, 1):
#         for cp in range(1, real_cp + 1):
#             # capacity allows putting in, calculate value
#             if item.w <= cp:
#                 values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
#             # can't put in, skip current item
#             else:
#                 values[i][cp] = values[i - 1][cp]
#
#     return values[c_items][real_cp]


def solve_2():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.v, item.w
        for cp in range(real_cp - w, -1, -1):
            dp[cp + w] = max(dp[cp + w], dp[cp] + v)

    return dp.pop()


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('v', 'w'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    # values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    print(solve_2())

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


# def solve():
#     for i, item in enumerate(item_list, 1):
#         for cp in range(1, real_cp + 1):
#             # capacity allows putting in, calculate value
#             if item.w <= cp:
#                 values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
#             # can't put in, skip current item
#             else:
#                 values[i][cp] = values[i - 1][cp]
#
#     return values[c_items][real_cp]


def solve_2():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.v, item.w
        for cp in range(real_cp - w, -1, -1):
            dp[cp + w] = max(dp[cp + w], dp[cp] + v)

    return dp[-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('v', 'w'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    # values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    print(solve_2())

Submission status: Accepted

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

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

output:
13
"""

import sys
from collections import namedtuple


def solve():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.v, item.w
        # for cp in range(real_cp - w, -1, -1):
        #     dp[cp + w] = max(dp[cp + w], dp[cp] + v)
        for cp in range(real_cp, w - 1, -1):
            dp[cp] = max(dp[cp], dp[cp - w] + v)

    return dp[-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('v', 'w'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Submission status: Accepted

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

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

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

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

def rec(i,j):
    if dp[i][j] != -1:
        return dp[i][j]
        
    if i == N:
        res = 0
    elif j < w[i]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-w[i])+v[i])
    
    dp[i][j] = res
    
    return dp[i][j]
    
print(rec(0,W))

Submission status: Accepted

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

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

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

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

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

print(dp[0][W])