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:
# coding: utf-8

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]))
# print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    # dp[n][sum_w]はn個目までの品物でsum_w以下の重量での価値の最大値
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
#0で初期化されたj*iの二次元配列を作る
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split()) 
#0で初期化されたj*iの二次元配列を作る 
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])
# pprint(dp)
print(dp[n][w])

Submission status: Accepted

Solution code:
#2-5 Knoapsack problem
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

Submission status: Accepted

Solution code:
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[i][j]:=i個目までの品物から重さの総和がj以下になるように選ぶときの，価値の合計の最大理
    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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(10000)

#input

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

#func
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))

Submission status: Accepted

Solution code:
import time

import sys
sys.setrecursionlimit(10000) # set recursion-stack depth

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

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

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])
# status = [0] * len(weights)
# dp = [0] * (cap + 1)
dp = [[-1]*(cap+1) for i in range(len(weights)+1)]
cnt = 0

# def knapsack(s):
#     w = 0
#     v = 0
#     if s == len(weights):
#         for i in range(len(status)):
#             if status[i] == 1:
#                 w += weights[i]
#                 v += vals[i]
#         if w <= cap:
#             return v
#         elif w > cap:
#             return -1
    
#     status[s] = 0
#     a = knapsack(s+1)
#     status[s] = 1
#     b = knapsack(s+1)

#     return max(a,b)

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))
# print(f'Count: {cnt}')




# def knapsack(w):
#     global status
#     global cnt
#     cnt += 1
#     isFin = True
#     for i in range(len(weights)):
#         if status[i] == 0 and weights[i] <= w:
#             isFin = False
#             break
    
#     if isFin == True:
#         return 0
#     max_v = -float('inf')
#     for i in range(len(weights)):
#         if status[i] == 1 or weights[i] > w:
#             continue
#         status[i] = 1
#         r = knapsack(w-weights[i]) + vals[i]
#         status[i] = 0
#         max_v = max(max_v,r)
#     return max_v



# def knapsack2(w):
#     global status
#     global cnt
#     cnt += 1
#     isFin = True
#     for i in range(len(weights)):
#         if status[i] == 0 and weights[i] <= w:
#             isFin = False
#             break
    
#     if isFin == True:
#         return 0
#     max_v = -float('inf')
#     for i in range(len(weights)):
#         if status[i] == 1 or weights[i] > w:
#             continue
#         status[i] = 1
#         r = 0
#         if dp[w-weights[i]] == 0:
#             r = knapsack2(w-weights[i]) + vals[i]
#         else:
#             r = dp[w-weights[i]] + vals[i]
#         status[i] = 0
#         max_v = max(max_v,r)
#         dp[w] = max_v
#         print(dp)
#     return max_v

Submission status: Accepted

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

Submission status: Accepted

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

# pprint.pprint(dp)
print(dp[n][w])

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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)]#容量W横軸、品物の数N縦軸
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 #cは袋の容量、iは品物の番号
        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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#ナップザック問題
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:
            # i番目までの品物の中から重さが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])

Submission status: Accepted

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


# dpテーブルの作成
# 今回は最大化が目的なのですべてのマスを-1で埋めることにする
dp = [[-1] * (W + 1) for _ in range(N + 1)]

# dpテーブルの初期化
# dp[:][0]が0 ∵大きさ0のナップサックには何も入れられない
# dp[0][:]が0 ∵なにもitemを考慮しないときはナップサックに何も入らない。
for i in range(N + 1):
    dp[i][0] = 0
for w in range(W + 1):
    dp[0][w] = 0

# dpテーブルの更新
# i番目のitemが入らない場合→dp[i+1][w]=dp[i][w] ∵iを考慮しないときと価値は変わらない
# i番目のitemが入る場合→dp[i+1][w]=max(dp[i][w], dp[i][w-item[i]の重さ]+item[i]の価値)
# ∵iを入れる前の最善はdp[i][w-item[i]の重さ]にあり、それにitem[i]の価値を足すことで最善になる可能性がある。
# ただしちゃんと、iを入れないときのほうが良いかもしれないことに注意しなければいけない。
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])

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

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

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


# ===CODE===


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 初期値
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())
    # dp[i][j] = i番目までの品物から重さj以下でつくれる最大の価値
    for j in range(W+1):
        # jがwより小さいとき、wは選べない
        if j < w:
            dp[i+1][j] = dp[i][j]
        # jがw以上のときは、入れる->dp[i][j-w]+v、入れない->dp[i][j]が価値
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w] + v)

print(dp[N][W])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp




import sys
input = sys.stdin.readline



M, W = map(int, input().split())                                # M: 品物の種類 W: 重量制限
single = True                                                   # 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)]                 # 左端と上端の境界条件で W, M を一個ずつ多めに取る
""" dp[item <= M ][weight <= W] = 重さ上限を固定した時の"最大"価値 """

for item in range(M+1):                                         # 左端の境界条件
    dp[item][0] = 0                                             # 重さ 0 を実現するのに必要な品物の個数は 0 個

# for weight in range(W+1):                                     # 上端の境界条件
#     dp[0][weight] = dp_max                                    # 0 種類の品物で実現できる重量は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for weight in range(1, W + 1):
        if weight < weight_list[item]:                          # weight (重量価値) < weight_list[item] (品物の重量) の時は無視してよい
            dp[item][weight] = dp[item - 1][weight]
        else:
            temp = dp[item - single][weight - weight_list[item]] + price_list[item]  # single = True: 重複なし
            if temp > dp[item-1][weight]:                       # max(dp[item-1][weight], temp)
                dp[item][weight] = temp
            else:
                dp[item][weight] = dp[item-1][weight]

print(dp[M][W])

Submission status: Accepted

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

Submission status: Accepted

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