Problem:
0-1 Knapsack Problem You have N items that you want to put them into a knapsack. Item i has value v i and weight w i . 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  v 1  w 1  v 2  w 2 : v N  w N  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 ≤ v i ≤ 1000  1 ≤ w i ≤ 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

Solution (Python):



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

Solution (Python):



"""
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[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)

Solution (Python):



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

output:
13
"""

import sys
from collections import namedtuple















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]

    
    ans = solve_2()
    print(ans)

Solution (Python):



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

output:
13
"""

import sys
from collections import namedtuple















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]

    
    ans = solve_2()
    print(ans)

Solution (Python):



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

output:
13
"""

import sys
from collections import namedtuple















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]

    
    print(solve_2())

Solution (Python):



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

output:
13
"""

import sys
from collections import namedtuple















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]

    
    print(solve_2())

Solution (Python):



"""
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] = 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())

Solution (Python):
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))

Solution (Python):
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])

Solution (Python):


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


def solve(N, W, v, w):
    
    
    
    
    dp = array2d(N, W + 1)
    for k in range(0, W + 1):
        dp[0][k] = 0 if k < w[0] else v[0]
    for i in range(1, N):
        for k in range(0, W + 1):
            dp[i][k] = dp[i-1][k]
            if k - w[i] >= 0:
                dp[i][k] = max(dp[i][k], dp[i-1][k-w[i]] + v[i])
    return max(dp[-1])



def main():
    N, W = map(int, input().split())
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = map(int, input().split())
    print(solve(N, W, v, w))

main()

Solution (Python):


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


def solve(N, W, v, w):
    
    
    
    
    dp = array2d(N, W + 1)
    for k in range(0, W + 1):
        dp[0][k] = v[0] if k == w[0] else 0
    for i in range(1, N):
        for k in range(0, W + 1):
            dp[i][k] = dp[i-1][k]
            if k - w[i] >= 0:
                dp[i][k] = max(dp[i][k], dp[i-1][k-w[i]] + v[i])
    return max(dp[-1])



def main():
    N, W = map(int, input().split())
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = map(int, input().split())
    print(solve(N, W, v, w))

main()

Solution (Python):


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


def solve(N, W, v, w):
    
    
    
    
    dp = array2d(N, W + 1)
    for k in range(0, W + 1):
        dp[0][k] = 0 if k < w[0] else v[0]
    for i in range(1, N):
        for k in range(0, W + 1):
            dp[i][k] = dp[i-1][k]
            if k - w[i] >= 0:
                dp[i][k] = max(dp[i][k], dp[i-1][k-w[i]] + v[i])
    return dp[N-1][W]



def main():
    N, W = map(int, input().split())
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = map(int, input().split())
    print(solve(N, W, v, w))

main()

Solution (Python):


import sys
import os



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

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






d = [[0 for i in range(C+1)] for j in range(N)]



for j in range(C+1):
    if j >= w[0]:
        d[0][j] = v[0]


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

print(d[N-1][C])

Solution (Python):
N, W = list(map(int, input().split()))
v_list = list()
w_list = list()

for _ in range(N):
    v, w = list(map(int, input().split()))
    v_list.append(v)
    w_list.append(w)

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

for i in range(1, N+1):
    item = v_list[i-1], w_list[i-1]
    for w in range(1, W+1):
        if item[1] > w:
            sum_v_table[i][w] = sum_v_table[i-1][w]
            continue
        sum_v_table[i][w] = max(sum_v_table[i-1][w], sum_v_table[i-1][w-item[1]] + item[0])

max_sum_v = sum_v_table[N][W]

print(max_sum_v)

Solution (Python):
N, W = map(int, input().split())
items = []
for _ in range(N):
    n, w = map(int, input().split())
    items.append([n, w])

C = [[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 items[i-1][1] <= w:
            if items[i-1][0] + C[i-1][w-items[i-1][1]] > C[i-1][w]:
                C[i][w] = items[i-1][0] + C[i-1][w-items[i-1][1]]
            else:
                C[i][w] = C[i-1][w]
        else:
            C[i][w] = C[i-1][w]
print(C[-1][-1])

Solution (Python):
def knapsack(items, num, weight):
    r = weight + 1
    C = [[0] * r for i in range(num + 1)]
    
    for i, item in enumerate(items, start=1):
        item_v, item_w = item
        for w in range(1, r):
            if item_w <= w:
                v1 = item_v + C[i - 1][w - item_w]
                v2 = C[i - 1][w]
                C[i][w] = max(v1, v2)
            else:
                C[i][w] = C[i - 1][w]
    return C[-1][-1]

import sys

file_input = sys.stdin

N, W = map(int, file_input.readline().split())

items = [map(int, line.split()) for line in file_input]

ans = knapsack(items, N, W)

print(ans)

Solution (Python):
N,W=[int(i) for i in input().split(" ")]
v=[]
w=[]
for i in range(N):
	vw=input().split(" ")
	v.append(int(vw[0]))
	w.append(int(vw[1]))



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

for i in range(N):
	array[i+1]=array[i].copy()
	for j in range(W):
		try:
			array[i+1][w[i]+j]=max(array[i+1][w[i]+j],array[i][j]+v[i],array[i][w[i]+j])
		except:
			pass


print (array[-1][-1])

Solution (Python):
def knapsack(items, num, weight):
    C = [0] * (weight + 1)
    for i in items:
        item_v, item_w = i
        for w in range(weight, 0, -1):
            if item_w <= w:
                v1 = item_v + C[w - item_w]
                v2 = C[w]
                C[w] = max(v1, v2)
    return C[weight]

import sys

file_input = sys.stdin

N, W = map(int, file_input.readline().split())

items = [map(int, line.split()) for line in file_input]

ans = knapsack(items, N, W)

print(ans)

Solution (Python):
def knapsack(items, num, weight):
    C = [0] * (weight + 1)
    for i in items:
        item_v, item_w = i
        for w in range(weight, item_w - 1, -1):
            v1 = item_v + C[w - item_w]
            v2 = C[w]
            C[w] = max(v1, v2)
    return C[weight]

import sys

file_input = sys.stdin

N, W = map(int, file_input.readline().split())

items = [map(int, line.split()) for line in file_input]

ans = knapsack(items, N, W)

print(ans)

Solution (Python):
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C[item_w:], C)):
            C[i] = max(vals[0] + item_v, vals[1])
    print(C[0])

solve()

Solution (Python):
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C[item_w:], C)):
            v1, v2 = vals
            C[i] = max(v1 + item_v, v2)
    print(C[0])

solve()

Solution (Python):
N,W = map(int, input().split())
item = [[None,None]]
for i in range(N):
    v,w = map(int, input().split())
    item.append([v,w])
C = [[0 for i in range(W+1)]] + [[0] + [None for i in range(W)] for i in range(N)]

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

Solution (Python):
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())

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


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

Solution (Python):
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())

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

print(value[W])

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

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

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

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

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

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

Solution (Python):
Nap = []

n,m = map(int,input().split())
for i in range(n):
    v,w = map(int,input().split())
    Nap.append([v,w])
DP = [[0 for j in range(m + 1)] for i in range(n + 1)]
for i in range(1,n+1):
        for j in range(m+1):
            if j - Nap[i-1][1] >= 0:
                DP[i][j] = max(DP[i-1][j],DP[i - 1][j - Nap[i - 1][1]] + Nap[i - 1][0])
            else:
                DP[i][j] = DP[i-1][j]
print(DP[n][m])

Solution (Python):
[N,W] = list(map(int,input().split()))
vl = [0]
wl = [0]
for i in range(N):
  [v,w] = list(map(int,input().split()))
  vl.append(v)
  wl.append(w)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N+1):
  for j in range(W+1):
    if i == 0 or j == 0:
      dp[i][j] = 0
    else:
      if wl[i] <= j:
        dp[i][j] = max(dp[i-1][j-wl[i]] + vl[i], dp[i-1][j])
      else:
        dp[i][j] = dp[i-1][j]

print(dp[N][W])

Solution (Python):
N, W = list(map(int,input().split()))
v = []
w = []
C = list([0 for i in range(W + 1)] for j in range(N + 1))
for i in range(N):
    n, m = list(map(int,input().split()))
    v.append(n)
    w.append(m)
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if j - w[i - 1] < 0:
            C[i][j] = C[i-1][j]
        else:
            C[i][j] = max(int(C[i-1][j]),int(C[i-1][j-w[i - 1]]+v[i - 1]))
print(int(C[N][W]))

Solution (Python):
import sys
readline = sys.stdin.readline

N, W = map(int, readline().split())
a = [(v, w) for _ in [None]*N for v, w in (map(int, readline().split()),)]

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

weight = {0}
for i in range(N):
    item_value, item_weight = a[i]
    for w in weight.copy():
        dp[i+1][w] = dp[i+1][w] if dp[i+1][w] > dp[i][w] else dp[i][w]
        nvalue = dp[i][w] + item_value
        if w+item_weight <= W:
            dp[i+1][w+item_weight] = nvalue if nvalue > dp[i+1][w+item_weight] else dp[i+1][w+item_weight]
            weight.add(w+item_weight)

print(max(dp[N]))

Solution (Python):
import sys
readline = sys.stdin.readline

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

dp = [0] * (W+1)

weights = {0}
add = weights.add
for i in range(N):
    item_v, item_w = map(int, readline().split())
    for w in sorted(weights, reverse=True):
        if w+item_w <= W and dp[w+item_w] < dp[w] + item_v:
            dp[w+item_w] = dp[w] + item_v
            add(w+item_w)

print(max(dp))

Solution (Python):
n, W = input().split()
n = int(n)
W = int(W)

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

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

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

print(dp[W][n])

Solution (Python):
from collections import defaultdict

memo = {}
def dfs(i, w, item_list, W):
    if i >= len(item_list):
        return 0

    if (i, w) in memo:
        return memo[(i, w)]

    ans = 0
    
    new_w = w + item_list[i][1]
    if new_w <= W:
        ans = max(ans, dfs(i + 1, new_w, item_list, W) + item_list[i][0])

    
    ans = max(ans, dfs(i + 1, w, item_list, W))

    memo[(i, w)] = ans
    return ans


def main():
    N, W = map(int, input().split())
    item_list = []
    for _ in range(N):
        v, w = map(int, input().split())
        item_list.append((v, w))

    print(dfs(0, 0, item_list, W))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict


def solve(N, W, vs, ws):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        v, w = vs[i], ws[i]
        for j in range(len(dp[0])):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            if j + w < len(dp[0]):
                dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)
    ans = 0
    for line in dp:
        ans = max(line)
    return ans


def main():
    N, W = map(int, input().split())
    vs, ws = [], []
    for _ in range(N):
        v, w = map(int, input().split())
        vs.append(v)
        ws.append(w)

    print(solve(N, W, vs, ws))

if __name__ == '__main__':
    main()

Solution (Python):
def solve_knapsack(weight, items):
    dp = [[0]*(weight+1) for _ in range(len(items))]
    for i, item in enumerate(items[1:]):
        for w in range(1, weight+1):
            if item[1] <= w:
                if item[0] + dp[i][w-item[1]] > dp[i][w]:
                    dp[i+1][w] = item[0] + dp[i][w-item[1]]
                else:
                    dp[i+1][w] = dp[i][w]
            else:
                dp[i+1][w] = dp[i][w]
    return dp[-1][-1]



if __name__ == '__main__':
    
    
    num_of_sack, total_capacity = [int(x) for x in input().strip().split(' ')]
    items = [[]]
    for _ in range(num_of_sack):
        items.append([int(x) for x in input().strip().split(' ')])
    

    
    result = solve_knapsack(total_capacity, items)
    print(result)

Solution (Python):
def solve_knapsack(weight, items):
    """
    ???????¨?????????§???????????¶????????????????§£???
    :param weight: ?¨±???????????????????????????
    :param items: ???????????¨???????????¨????????¨????????????????????????????????¨????????????????????£????????????[0]???????????§[1]????????????items[0]?????????????????????
    :return: ??????????¶??????????????????§??¢??????????????°??????????????´????????????????????§???
    """
    dp = [[0]*(weight+1) for _ in range(len(items))] 
    for i, item in enumerate(items[1:], start=1):
        for w in range(1, weight+1):
            
            if item[1] <= w:
                if item[0] + dp[i-1][w-item[1]] > dp[i-1][w]: 
                    dp[i][w] = item[0] + dp[i-1][w-item[1]] 
                else:           
                    dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = dp[i-1][w]
    return dp[-1][-1]



if __name__ == '__main__':
    
    
    num_of_sack, total_capacity = [int(x) for x in input().strip().split(' ')]
    items = [[]]                
    for _ in range(num_of_sack):
        items.append([int(x) for x in input().strip().split(' ')])
    

    
    result = solve_knapsack(total_capacity, items)
    print(result)

Solution (Python):

from copy import deepcopy
N, W = tuple(map(int, input().split()))
items = []
for n in range(N):
    items.append(list(map(int, input().split()))) 

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

for item in items:
    for w in range(item[1], W+1):
        post_costs[w] = max(pre_costs[w], pre_costs[w-item[1]] + item[0])
    pre_costs = deepcopy(post_costs)

print(post_costs[-1])

Solution (Python):

from copy import deepcopy
N, W = tuple(map(int, input().split()))
items = []
for n in range(N):
    items.append(list(map(int, input().split()))) 

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

for item in items:
    for w in range(item[1], W+1):
        post_costs[w] = max(pre_costs[w], pre_costs[w-item[1]] + item[0])
    pre_costs = deepcopy(post_costs)

print(post_costs[-1])

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

for i in range(N)[::-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])

Solution (Python):
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 i in range(N):
    v[i], w[i] = 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])

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

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

Solution (Python):
n, maxw = list(map(int, input().split()))
v_lis, w_lis = [], []   


for _ in range(n):
    v, c = list(map(int, input().split()))
    v_lis.append(v)
    w_lis.append(c)



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

for i in range(1, n+1):
    for j in range(1, maxw+1):
        if j>=w_lis[i-1]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_lis[i-1]]+v_lis[i-1])
        else:
            dp[i][j] = dp[i-1][j]

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

Solution (Python):
n, maxw = list(map(int, input().split()))

dp = [0 for _ in range(maxw+1)]
for i in range(n):
    v, c = list(map(int, input().split()))
    for j in range(maxw, -1, -1):
        if j>=c:
            dp[j] = max(dp[j], dp[j-c]+v)
        else:
            break
print(dp[-1])

Solution (Python):
n, maxw = map(int, input().split())

dp = [0 for _ in range(maxw+1)]
for i in range(n):
    v, c = map(int, input().split())
    for j in range(maxw, -1, -1):
        if j>=c:
            dp[j] = max(dp[j], dp[j-c]+v)
        else:
            break
print(dp[-1])

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

Solution (Python):
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 res 
print(rec(0, W))

Solution (Python):

NW=input().split()

N=int(NW[0])
W=int(NW[1])

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

C=[[0 for i2 in range(W+1)]for i1 in range(N+1)]

for i in range(1,N+1):
    for j in range(1,W+1):
        if j>=item[i-1][1]:
            if item[i-1][0]+C[i-1][j-item[i-1][1]]>C[i-1][j]:
                C[i][j]=item[i-1][0]+C[i-1][j-item[i-1][1]]
            else:
                C[i][j]=C[i-1][j]
        else:
            C[i][j]=C[i-1][j]


print(C[N][W])

Solution (Python):
if __name__ == "__main__":
	N,W = map(int,input().split(" "))
	dp = [[0] * (W+1) for _ in range(N+1)]

	w_lis = [0] * N
	v_lis = [0] * N

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



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

			else:
				dp[i][w] = dp[i-1][w]


	print(dp[N][W])

Solution (Python):




input1 = input().split()
N = int(input1[0]) 
W = int(input1[1]) 

item = [[0]*2 for i in range(N)]
for i in range(N):
	input2 = input().split()
	item[i][0] = int(input2[0])
	item[i][1] = int(input2[1])

v = [[0]*(W+1) for i in range(N)]
for i in range(N):
	for c in range(W+1):
		if (i < 0 or c <= 0):
			v[i][c] = 0
		elif (c-item[i][1] < 0):
			v[i][c] = v[i-1][c]
		else:
			v[i][c] = max(item[i][0] + v[i-1][c-item[i][1]], v[i-1][c])
			
print(v[N-1][W])

Solution (Python):
N,W = map(int, input().split())
v = [0] * (N+1)
w = [0] * (N+1)
dp = [[0 for x in range(W+1)] for y in range(N+1)]

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

for i in range(1,N+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[N][W])

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

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

print(dp[N][W])

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

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

print(dp[N][W])

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

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

print(dp[N][W])

Solution (Python):
from fractions import gcd
from functools import reduce

N,W = map(int, input().split())
v = [0]*(N+1)
wtemp = [0]*(N+1)

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

gcdw = reduce(gcd,wtemp+[W])
w = list(map(lambda x:x//gcdw, wtemp))

W2 = W//gcdw
dp = [[0]*(W2+1) for y in range(N+1)]

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

print(dp[N][W2])

Solution (Python):
N,W = map(int, input().split())
dp = [0]*(W+1)
temp = [0]*(W+1)

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

print(dp[W])

Solution (Python):
N,W = map(int, input().split())
dp = [0]*(W+1)
temp = [0]*(W+1)

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

print(dp[W])

Solution (Python):
N,W = map(int, input().split())
dp = [0]*(W+1)
temp = [0]*(W+1)

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

print(dp[W])

Solution (Python):
N,W = map(int, input().split())
dp = [0]*(W+1)
temp = [0]*(W+1)

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

print(dp[W])

Solution (Python):
N,W = map(int, input().split())
dp = [0]*(W+1)
temp = [0]*(W+1)

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

print(dp[W])

Solution (Python):
N,W = map(int, input().split())
dp = [0]*(W+1)
temp = [0]*(W+1)

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

print(dp[W])

Solution (Python):
N,W = map(int, input().split())
dp = [0]*(W+1)
temp = [0]*(W+1)

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

    temp[0:W+1] = dp[0:W+1]

print(dp[W])

Solution (Python):
N,W = map(int, input().split())
dp = [0]*(W+1)

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

print(dp[W])