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):
n, w = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+10) for _ in range(n+10)]
weight = [0] * (n+10)
value = [0] * (n+10)

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

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

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

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


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

Solution (Python):
import sys

input = sys.stdin.readline


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

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

    ans = max(dp[-1])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
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 n_i in range(1, n+1):
  for w_i in range(w+1):
    if w_i-VW[n_i-1][1]>=0:
      DP[n_i][w_i] = max(DP[n_i-1][w_i], DP[n_i-1][w_i-VW[n_i-1][1]]+VW[n_i-1][0])
    else:
      DP[n_i][w_i] = DP[n_i-1][w_i]
      
print(max(DP[-1]))

Solution (Python):
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N, W = MI()
    mylist = [LI() for i in range(N)]
    d = [[0 for i in range(W+1)] for j in range(1+N)]
    for i in range(N):
        v, w = mylist[i]
        for j in range(W+1):
            if w > j:
                d[i+1][j] = max(d[i][j], d[i+1][j])
            else:
                d[i+1][j] = max(d[i][j], d[i+1][j], d[i][j-w]+v)
    print(d[N][W])
    
    
if __name__ == "__main__":
    main()

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

Solution (Python):
class item:
    def __init__(self,v,w):
        self.v = v
        self.w = w

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

for i in range(1,n+1):
    for w in range(W+1):
        max_value = dp[i-1][w]
        if w-items[i-1].w>=0:
            max_value = max(max_value,dp[i-1][w-items[i-1].w]+items[i-1].v)
        dp[i][w] = max_value
        
print(dp[n][W])

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

w=[]
v=[]


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


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

for i in range(N):
    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],dp[i][j-w[i]]+v[i])
    
print(dp[N][W])

Solution (Python):


n, max_weight = list(map(int, input().split(" ")))

value = []
weight = []

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

dp = []
for _ in range(n+1):
    dp.append([0 for _ in range(max_weight+1)])

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

print(dp[n][max_weight])

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

weight = []
value = []

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

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

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

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

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

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

from itertools import product
for i, w in product(range(N), range(W + 1)):
    dp[i + 1][w] = dp[i][w]
    value, weight = items[i]
    if w - weight >= 0:
        dp[i + 1][w] = max(dp[i][w], dp[i][w - weight] + value)

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

Solution (Python):
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  v, w = map(int, input().split())
  value.append(v)
  weight.append(w)
record = [[-1] * (W+1) for _ in range(N+1)]
record[0][0] = 0

for i in range(1, N+1): 
  for j in range(W+1): 
    if record[i-1][j] != -1:
      if record[i][j] < record[i-1][j]:
        record[i][j] = record[i-1][j]
      if j + weight[i] < W + 1:
        record[i][j + weight[i]] = record[i-1][j] + value[i]
print(max(record[N]))

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

mem=[[0]*(W+2) for _ in range(N+2)]

for i in range(N,0,-1):
    for w in range(0,W+1):
        value, weight=P[i-1]
        if w < weight:
            mem[i][w] =mem[i+1][w]
        else:
            mem[i][w]=max(mem[i+1][w], mem[i+1][w-weight]+value)
print(mem[1][W])

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,w = readInts()
arr = [readInts() for i in range(n)]

dp = [[0]*10001 for i in range(n+1)]

for i in range(n):
	for j in range(10001):
		if j-arr[i][1]>=0:
			dp[i+1][j] = max(dp[i][j-arr[i][1]]+arr[i][0],dp[i][j])
		else:
			dp[i+1][j] = dp[i][j]

print(dp[n][w])

Solution (Python):
N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    vv, ww = items[i]
    for w in range(W+1):
        if w >= ww:
            dp[i+1][w] = max(dp[i][w], dp[i][w-ww]+vv)
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, W = map(int, readline().split())
    dp = [0]*(W+1)
    for _ in range(N):
        v, w = map(int, readline().split())
        if W-w>=0:
            for i in range(W,w-1,-1):
                dp[i] = max(dp[i], dp[i-w]+v)
    print(dp[W])

if __name__ == '__main__':
    main()

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

value = [0]*1001
wight = [0]*1001
for i in range(n):
    V, W = map(int, input().split())
    value[i] = V
    wight[i] = W

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

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

print(dp[n][w])

Solution (Python):
n, mw = map(int, input().split())
v, w = [], []
for _ in range(n):
    vi, wi = map(int, input().split())
    v.append(vi)
    w.append(wi)

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

for i in range(n-1, -1, -1):
    for j in range(mw+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][mw])

Solution (Python):
n, w = [int(_) for _ in input().split()]

ans = [[-1 for i in range(w+1)]for i in range(2)]

ans[0][0] = 0
ans[1][0] = 0
c = 0
for i in range(n):
    s, t = [int(_) for _ in input().split()]
    for j in range(w-t+1):
        if ans[c][j] > -1:
            ans[not(c)][t+j] = max(ans[c][t+j], ans[c][j]+s)
    for j in range(w):
        ans[c][j] = ans[not(c)][j]
    c = not(c)
print(max(ans[c]))

Solution (Python):
N,W = map(int,input().split())
Value = []
weight = []
inf=float("inf")
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):
    v,w = map(int,input().split())
    Value.append(v)
    weight.append(w)


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

print(dp[N][W])

Solution (Python):
def main():
    import sys

    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]

    
    
    dp = [[0] * (W + 1) for _ in [0] * (N + 1)]
    
    for n in range(N):
        v, w = lst[n]
        for sum_w in range(W + 1):
            res = sum_w - w
            if res >= 0:
                dp[n + 1][sum_w] = max(dp[n + 1][sum_w], dp[n][res] + v)
            dp[n + 1][sum_w] = max(dp[n + 1][sum_w], dp[n][sum_w])
    print(dp[N][W])


main()

Solution (Python):
n, w = map(int, input().split())
s = [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 < s[i][1]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - s[i][1]] + s[i][0])
print(dp[n][w])

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

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

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

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

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

Solution (Python):
n,l = map(int,input().split())
V = []
W = []
INF = float("inf")
for _ in range(n):
    v,w = map(int,input().split())
    V.append(v)
    W.append(w)
dp = [[0]*(l+1) for _ in range(n+1)]
for i in range(n):
    for j in range(l+1):
        if j>=W[i]:
            dp[i+1][j] = max(dp[i][j],dp[i][j-W[i]]+V[i])
        else:
            dp[i+1][j] = dp[i][j]
print(max(dp[n]))

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

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

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

def knapsack_problem(n,cap,value,weight):
    ans = 0
    dp = [[0]*(cap+1) for i in range(n+1)]
    
    for i in range(n):
        for w in range(cap+1):
            if w >= weight[i]:
                dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i],dp[i][w])
            else:
                dp[i + 1][w] = dp[i][w]

    can = 0
    for s in dp:
        can = max(can,max(s))

    return can
        
if __name__ == "__main__":
    n,w = map(int,input().split())
    vl = [0] * n
    wl = [0] * n
    for i in range(n):
        vl[i], wl[i]= map(int,input().split())

    print(knapsack_problem(n,w,vl,wl))

Solution (Python):
from collections import defaultdict
from copy import deepcopy

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

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

ans = 0
w2v = defaultdict(int)
w2v[0] = 0

for v, w in VW:
    new_w2v = deepcopy(w2v)
    for w_, v_ in w2v.items():
        new_w = w_ + w
        new_v = v_ + v
        if new_w <= W:
            ans = max(ans, new_v)
            new_w2v[new_w] = max(new_w2v[new_w], new_v)
    w2v = new_w2v
print(ans)

Solution (Python):
from pprint import pprint
n,w=map(int,input().split())
V=[]
W=[]
for _ in range(n):
    x,y=map(int,input().split())
    V.append(x)
    W.append(y)

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

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

print(dp[n][w])

Solution (Python):

while True:
    try:
        N, W = map(int,input().split())
        v=[]
        w=[]

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

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

        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])
        
    except:
        break

Solution (Python):
import sys


def main():
    input = sys.stdin.buffer.readline
    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())
        v[i], w[i] = v_i, w_i
    
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
            else:
                dp[i][j] = dp[i - 1][j]
    print(dp[n][W])


if __name__ == "__main__":
    main()

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


value = []
weight = []

for i in range(n):
    x, y = map(int, input().split())
    value.append(x)
    weight.append(y)


memo = [[-1 for ii in range(w+1)] for jj in range(n+1)]
maximum = 0

def zero_oneKnapsack(ww,nn):
    global maximum

    if memo[nn][ww] == -1:
        if nn == 0 or ww == 0:
            memo[nn][ww] = 0
        else:
            a = zero_oneKnapsack(ww, nn-1)
            b = -1
            if ww >= weight[nn-1]:
                b = value[nn-1] + zero_oneKnapsack(ww-weight[nn-1], nn-1)
            elif ww < weight[nn-1]:
                memo[nn][ww] = zero_oneKnapsack(ww, nn-1)
            maximum = max(a, b)
            memo[nn][ww] = maximum
    return memo[nn][ww]

print(zero_oneKnapsack(w, n))

Solution (Python):
str = input().split(" ")
N = int(str[0])
W = int(str[1])
value = [0 for i in range(N)]
weight = [0 for i in range(N)]
dp = [[0 for i in range(W+1)] for l in range(N+1)]

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

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

print(dp[N][W])

Solution (Python):
import sys 
sys.setrecursionlimit(10000)



n ,m = map(int,input().split())
v = [0]*(n)
w = [0]*(n)

memo = [[None]*(m+1) for d in range(n+1)]


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


def knapsack(i , c):
    if memo[i][c] != None :
      return memo[i][c]
    elif i==n or c == 0:
        return 0
    else :
        t1 = knapsack(i + 1 , c)
        t2 = -1
        if c >= w[i] :
            t2 = v[i] + knapsack(i + 1 , c - w[i])
        result = max(t1,t2)
        memo[i][c] = result
        return result
print(knapsack(0 , m))

Solution (Python):
import time

import sys
sys.setrecursionlimit(10000) 

n ,c = list(map(int,input().split())) 
v = [0]*(n)
w = [0]*(n)

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

mm = [[None for i in range(c + 1)] for j in range(n + 1)]

def comb(i, c):
    if i == n:
        return 0
    else:
        if mm[i][c] != None:
            return mm[i][c]

        a = comb(i+1, c)

        b = -1
        if c >= w[i]:
            b = v[i] + comb(i+1, c - w[i])

        mm[i][c] = max(a, b)
        return mm[i][c]

print(comb(0, c))

Solution (Python):
import sys
sys.setrecursionlimit(10001)

n, m = list(map(int, input().split()))
v = []
w = []

for i in range(n):
    a,b = list(map(int, input().split()))
    v.append(a)
    w.append(b)

x = [[-1]* (m+1) for i in range(n+1) ]

def knapsack(i, c):
    if x[i][c] == -1:
        if c == 0 or i == n:
            x[i][c] = 0

        else:
            a = knapsack(i+1, c)
            b = 0

            if c >= w[i]:
                b = v[i] + knapsack(i+1, c - w[i])
            x[i][c] = max(a, b)

    return x[i][c]

print(knapsack(0, m))

Solution (Python):
N, W = tuple(map(int,(input().split())))
items = []

memo = [[-2]*(W+1) for i in range(N+1)]

weight = 1
value = 0

for i in range(N):
   item = tuple(map(int,(input().split())))
   items.append(item)

def comb(i, c):
    if memo[i][c] != -2:
        return memo[i][c]
    if i == N:
        return 0
    
    v = 0
    u = comb(i+1, c)
    if c-items[i][weight] >= 0:
        v = comb(i+1, c-items[i][weight]) + items[i][value]
    best = max(u,v)
    memo[i][c] = best
    return best

print(comb(0,W))

Solution (Python):
x = list(map(int,input().split()))
n = x[0]
cap = x[1]
weights = []
vals = []
for i in range(n):
    y = list(map(int,input().split()))
    vals.append(y[0])
    weights.append(y[1])


dp = [[-1]*(cap+1) for i in range(len(weights)+1)]
cnt = 0













    







def knapsack(s,av):
    global cnt
    cnt += 1

    if dp[s][av] != -1:
        return dp[s][av]

    if s == len(weights):
        dp[s][av] = 0
        return 0
    
    a = knapsack(s+1,av)

    if av >= weights[s]:
        b = vals[s] + knapsack(s+1,av-weights[s])
    else:
        b = -1
    
    dp[s][av] = max(a,b)

    return max(a,b)


print(knapsack(0,cap))

Solution (Python):
(N,W),*vw = [list(map(int, s.split())) for s in open(0)]
vw.sort(key=lambda x:x[1],reverse=True)
from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0

for v,w in vw:
    items = list(dp.items())
    for key, val in items:
        new_key = key+w
        if new_key <= W:
            new_val = val+v
            if (new_key in dp and dp[new_key] < new_val) or new_key not in dp:
                dp[new_key] = max(dp[new_key], new_val)

print(max(dp.values()))

Solution (Python):
import pprint
n,w=map(int,input().split())
V=[]
W=[]
for _ in range(n):
    x,y=map(int,input().split())
    V.append(x)
    W.append(y)
dp=[[0]*(w+1) for _ in range(n+1)]

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


print(dp[n][w])

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

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

print(max(sum(dp, [])))

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

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

if __name__ == '__main__':
    main()

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

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

for i in range(N):
    for j in range(W+1):
        if W-j+L[i][1]<=W:
            DP[W-j+L[i][1]]=max(DP[W-j+L[i][1]],DP[W-j]+L[i][0])
print(DP[-1])

Solution (Python):
n,w=map(int,input().split())
vlst=[0 for i in range(n)]
wlst=[0 for i in range(n)]
for i in range(n):
    vlst[i],wlst[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 j-wlst[i-1]>=0:
            dp[i][j]=max(dp[i-1][j-wlst[i-1]]+vlst[i-1],dp[i-1][j])
        else : dp[i][j]=dp[i-1][j]

print(dp[n][w])

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

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

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

print(DP[N][W])

Solution (Python):
import sys
sys.setrecursionlimit(10000)

temp = [int(x) for x in input().split()]
N = temp[0]
if N < 1 or N > 100:
    sys.exit()
W = temp[1]
if W < 1 or W > 10000:
    sys.exit()
weight = [0]*N
value = [0]*N
temp1 = [0, 0]
for i in range(N):
    temp1 = [int(x) for x in input().split()]
    value[i] = temp1[0]
    if value[i] < 1 or value[i] > 1000:
        sys.exit()
    weight[i] = temp1[1]
    if weight[i] < 1 or weight[i] > 10000:
        sys.exit()

calls = [[-1 for x in range(W + 1)] for y in range(N + 1)] 

def comb(n, cap):
    if (n == N):
        return 0
    else:
        if calls[n][cap] == -1:
            a = comb(n + 1, cap)
            b = 0
            if (weight[n] <= cap):
                b = value[n] + comb(n + 1, cap - weight[n])
            calls[n][cap] = max(a, b)
        return calls[n][cap]

print(comb(0, W))

Solution (Python):

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

print(dp[N][W])

Solution (Python):

N, W = list(map(int, input().split()))
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))




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




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






from itertools import product
for i, w in product(range(N), range(W + 1)):
    dp[i + 1][w] = dp[i][w]
    value, weight = items[i]
    if w - weight >= 0:
        dp[i + 1][w] = max(dp[i][w], dp[i][w - weight] + value)

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

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n, w = ns()
    d = []
    for _ in range(n):
        tmp = na()
        d.append(tmp)

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

    for vi, wi in d:
        for i in range(w, -1, -1):
            if dp[i] > -1 and i + wi < w + 1:
                dp[i + wi] = max(dp[i + wi], dp[i] + vi)

    print(max(dp))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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(1, N + 1):
        v, w = VW[i - 1]
        for j in range(1, W + 1):
            if j - w >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j])
    print(dp[-1][-1])


if __name__ == '__main__':
    resolve()

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

dp = [ [0]*(W+1) for _ in range(N+1)]
for i in range(1, N+1):
  wei, val = weights[i-1], vals[i-1]
  for w in range(W+1):
    if w >= wei:
      dp[i][w] = max(dp[i-1][w], dp[i-1][w-wei] + val)
    else:
      dp[i][w] = max(dp[i][w-1], dp[i-1][w])

print(dp[N][W])

Solution (Python):

INF = 10**18


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

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

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

print(dp[N][W])

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

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

Solution (Python):
N,W=map(int,input().split())
vw=[list(map(int,input().split())) for _ in range(N)]
DP=[[0 for i in range(10001)] for j in range(100)]
for idx in range(N):
    for weight in range(10001):
        if weight<vw[idx][1]:
            DP[idx][weight]=DP[idx-1][weight]
        else:
            DP[idx][weight]=max(DP[idx-1][weight-vw[idx][1]]+vw[idx][0],DP[idx-1][weight])

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

Solution (Python):





import sys
input = sys.stdin.readline



M, W = map(int, input().split())                                
single = True                                                   

price_list = [0]
weight_list = [0]
for _ in range(M):
    price, weight = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)




dp_min = 0                                                      


dp = [[dp_min] * (W + 1) for _ in range(M + 1)]                 
""" dp[item <= M ][weight <= W] = 重さ上限を固定した時の"最大"価値 """

for item in range(M+1):                                         
    dp[item][0] = 0                                             





for item in range(1,M+1):                                       
    for weight in range(1, W + 1):
        if weight < weight_list[item]:                          
            dp[item][weight] = dp[item - 1][weight]
        else:
            temp = dp[item - single][weight - weight_list[item]] + price_list[item]  
            if temp > dp[item-1][weight]:                       
                dp[item][weight] = temp
            else:
                dp[item][weight] = dp[item-1][weight]

print(dp[M][W])

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

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

Solution (Python):
N, totalWt = list(map(int, input().split()))
itemsVal = [0]
itemsWt = [0]
for i in range(0, N):
    val, weight = list(map(int, input().split()))
    itemsVal.append(val)
    itemsWt.append(weight)

mylist = [[0 for _ in range(totalWt+1)] for _ in range(N + 1)]


for i in range(1, N + 1):
    for j in range(1, totalWt+1):
        if j >= itemsWt[i]:
            mylist[i][j] = max(mylist[i-1][j], mylist[i-1][j-itemsWt[i]] + itemsVal[i])
        else:
            mylist[i][j] = mylist[i-1][j]

print(mylist[len(itemsWt)-1][totalWt])