Problem:


Knapsack Problem

You have N kinds of items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

The total value of the items is as large as possible.

The items have combined weight at most W, that is capacity of the knapsack.

You can select as many items as possible into a knapsack for each kind.

Find the maximum total value of items in the knapsack.

Input

N W
v1 w1
v2 w2
:
vN wN

The first line consists of the integers N and W. In the following lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Constraints

 1 ≤ N ≤ 100
	

 1 ≤ vi ≤ 1000
	

 1 ≤ wi ≤ 1000
	

 1 ≤ W ≤ 10000
	

Sample Input 1

4 8
4 2
5 2
2 1
8 3

Sample Output 1

21

Sample Input 2

2 20
5 9
4 10

Sample Output 2

10

Sample Input 3

3 9
2 1
3 1
5 2

Sample Output 3

27



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


Sample output:
21

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=jp
"""
import sys
input = sys.stdin.readline


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:
                dp[i+1][w] = max((item[0] + dp[i][w-item[1]]),  dp[i][w], (item[0] + dp[i+1][w-item[1]]))
            else:
                dp[i+1][w] = dp[i][w]
    return dp[-1][-1]


def main(args):
    N, W = map(int, input().split())
    items = [[]]
    for _ in range(N):
        items.append([int(x) for x in input().strip().split()])
    result = solve_knapsack(W, items)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=jp
AC
"""
import sys
input = sys.stdin.readline


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:
                # dp[i+1][w] = max((item[0] + dp[i][w-item[1]]),  dp[i][w], (item[0] + dp[i+1][w-item[1]]))
                dp[i+1][w] = max(dp[i][w], (item[0] + dp[i+1][w-item[1]]))
            else:
                dp[i+1][w] = dp[i][w]
    return dp[-1][-1]


def main(args):
    N, W = map(int, input().split())
    items = [[]]
    for _ in range(N):
        items.append([int(x) for x in input().strip().split()])
    result = solve_knapsack(W, items)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

Submission status: Accepted

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

print(max(dp))

Submission status: Accepted

Solution code:
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):
        if j >= w:
            dp[j] = max(dp[j], dp[j - w] + v)
print(dp[W])

Submission status: Accepted

Solution code:

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][j -item[i - 1][1]] > C[i - 1][j]:#???????????????
                C[i][j] = item[i-1][0] + C[i][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])

Submission status: Accepted

Solution code:
# Knapsack Problem
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


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

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

Submission status: Accepted

Solution code:
# Knapsack Problem
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


DP = [0] * (W+1)
for i in range(N):
    v, w = items[i]
    for j in range(w, W+1):
        DP[j] = max(DP[j], v + DP[j-w])

print(DP[-1])

Submission status: Accepted

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

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

dp = [-float('inf') for i in range(W+1)]
dp[0] = 0
max_w = 0
for w in range(W+1):
    for i in range(N):
        if w - ws[i] < 0 :
            continue
        dp[w] = max(dp[w], dp[w-ws[i]]+vs[i])
        max_w = max(max_w, dp[w])

#print(dp[W])
print(max_w)

Submission status: Accepted

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

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

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

for i in range(n):
    for j in range(weights[i], w+1):
        dp[j] = max(dp[j], dp[j-weights[i]]+values[i])

print(dp[w])

Submission status: Accepted

Solution code:
N, W = map(int,input().split(' '))
v=[]
w=[]

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

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

# dp[i][j]: i番目までの品物でjまでの重さを使ったときのvの最大値

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

print(dp[N][W])

Submission status: Accepted

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


for i in range(N):
    for j in range(W+1):
        if j - w_list[i] >= 0:
            dp[i+1][j] = max(dp[i+1][j-w_list[i]]+v_list[i],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())
v = []
w = []
for i in range(N):
    a, b = map(int, input().split())
    v.append(a)
    w.append(b)

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

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

print(dp[W])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, w = list(map(int, input().split(' ')))
items = [list(map(int, input().split(' '))) for i in range(n)]

table = [[0 for j in range(n+1)] for i in range(w+1)]

for i in range(1, w+1):
    for j in range(1, n+1):
        v, w = items[j-1]
        if i - w < 0:
            table[i][j] = table[i][j-1]
        else:
            new_val = table[i-w][j] + v
            table[i][j] = new_val if new_val > table[i][j-1] else table[i][j-1]

print(table[-1][-1])

Submission status: Accepted

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

value = []
weight = []

for _ in range(n):
  vi, wi = map(int, input().split())
  value.append(vi)
  weight.append(wi)

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

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

print(dp[w])

Submission status: Accepted

Solution code:
n,w = map(int, input().split())
item = [list(map(int,input().split())) for i in range(n)]
dp = [0 for i in range(w+2)]
for i in range(w+1):
    for v in item:
        if i+v[1] <= w:
            dp[i+v[1]] = max(dp[i+v[1]], dp[i]+v[0])
print(dp[w])

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
v = [0]*N; w = [0]*N
for i in range(N):
    v[i], w[i] = map(int, input().split())

DP = [0]*(W+1)
for i in range(N):
    weight = w[i]
    value = v[i]
    for sum_w in range(1, W+1):
        if sum_w - weight >= 0:
            DP[sum_w] = max(DP[sum_w], DP[sum_w - weight] + value)
print(DP[-1])

Submission status: Accepted

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

value = [0] * N
weight = [0] * N

for i in range(N):
    value[i] = li[i][0]
    weight[i] = li[i][1]
    
dp = [[0] * (W+10) for _ in range(N+10)]

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], dp[i+1][w - weight[i]] + value[i])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Accepted

Solution code:
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+1][j-w[i]] + v[i]
                             )    
print(dp[N][W])

Submission status: Accepted

Solution code:
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 v, w in vw:
        for i in range(w, W + 1):
            dp[i] = max(dp[i], dp[i - w] + v)

    ans = max(dp)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

value, weight= [0]*N, [0]*N

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
"""
for i in range(N):
    for j in range(W+1):
        k = 0
        while k * weight[i] <= j:
            res1 = dp[i+1][j]
            res2 = dp[i][j - k*weight[i]] + k * value[i]
            dp[i+1][j] = max(res1, res2)
            k += 1
"""

for i in range(N):
    for j in range(W+1):
        if j < weight[i]:
            dp[i+1][j] = dp[i][j]
        else:
            res1 = dp[i][j]
            res2 = dp[i+1][j - weight[i]] + value[i]
            dp[i+1][j] = max(res1, res2)

print(dp[N][W])

Submission status: Accepted

Solution code:
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()
    d = [[0 for i in range(W+1)] for j in range(N+1)]
    mylist = [LI() for i in range(N)]
    for i in range(N):
        vt, wt = mylist[i]
        for j in range(W+1):
            if wt > j:
                d[i+1][j] = d[i][j]
            else:
                d[i+1][j] = max(d[i][j], d[i+1][j-wt]+vt)
    print(d[N][W])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
dp = [[-1]*(W+1) for _ in range(N+1)]
dp[0][0] = 0

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
# coding: utf-8

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

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

items = [0 for _ in range(10**7)]
weights = []
for _ in range(n):
    v, w = list(map(int, input().split(" ")))
    if w not in weights:
        weights.append(w)
    items[w] = max(items[w], v)


for i in range(1, max_weight+1):
    for w in weights:
        if i >= w:
            dp[i] = max(dp[i-w] + items[w], dp[i])

print(dp[max_weight])

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(n):
  v,w=[int(_) for _ in input().split()]
  
  for j in range(W-w+1):
    t[j+w]=max(t[j]+v,t[j+w])
print(max(t))
#print(t)

Submission status: Accepted

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

#容量jのとき商品i個目までで入れられる価値の最大値
#i-1個目まで分かっててi個目を詰めるとき
#容量j-wのときの価値+v  or  容量jのときの価値  or  i個目容量j-wのときの価値

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

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

Submission status: Accepted

Solution code:
n,www = map(int,input().split())
v,w=[],[]
for i in range(n):
    vv,ww = map(int,input().split())
    v.append(vv)
    w.append(ww)

dp=[0 for j in range(www+1)]
#dp[i][j] = i-1番目(0-index)までの品物の中から重さがjを超えないように選んだ時の価値の最大値

for i in range(n):
    dpp = dp[:]
    for j in range(www+1):
        if (w[i] > j): continue
        dpp[j] = max(dpp[j],dpp[j-w[i]] + v[i])
    dp = dpp[:]

print(dp[www])

Submission status: Accepted

Solution code:
def main():
    import sys

    readline = sys.stdin.readline

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

    dp = [[0] * (W + 1) for _ in [0] * (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 + 1][j - w[i]] + v[i])
    print(dp[N][W])


main()

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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],dp[i+1][w-weight[i]]+Value[i])
    else:
      dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

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

print(dp[-1])

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

Submission status: Accepted

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

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

dp = [0] * (W+1)

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

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],dp[i+1][j-W[i]]+V[i])
            
# pprint(dp)
print(dp[n][w])

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][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=map(int,input().split())
vlst=[0 for _ in range(n+1)]
wlst=[0 for _ in range(n+1)]

for i in range(1,n+1):
    x,y=map(int,input().split())
    vlst[i],wlst[i]=x,y

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

for i in range(1,n+1):
    for j in range(1,w+1):
        work=j-wlst[i]
        if work>=0:
            dp[i][j]=max(dp[i-1][j],dp[i][work]+vlst[i],dp[i-1][work]+vlst[i])
        else :
            dp[i][j]=dp[i-1][j]

print(dp[n][w])

Submission status: Accepted

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

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

print(max(dp))

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

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 個数制限なしナップサック問題
N,W = map(int,input().split())

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

for i in range(N):
    v,w = map(int,input().split())
    # dp[j] = 重さj以下でつくれる最大の価値
    for j in range(W+1):
        # jがwより小さいとき、wは選べない
        if j >= w:
            dp[j] = max(dp[j],dp[j-w] + v)

print(dp[W])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
vw=[list(map(int,input().split())) for _ in range(N)]
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][weight-vw[idx][1]]+vw[idx][0],DP[idx-1][weight])

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

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline



M, W = map(int, input().split())                                # M: 品物の種類 W: 重量制限
single = False                                                   # 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[item <= M ][weight <= W]
dp = [[dp_min] * (W + 1) for _ in range(M + 1)]                 # 左端と上端の境界条件で W, M を一個ずつ多めに取る

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]:
                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())
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][j-w]+v)
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][W])

Submission status: Accepted

Solution code:
# 36

# dp[i][j] : i-1 までの品物を使って重さw以下で押さえたときの価値の最大値
n, w = map(int, input().split())
vw_l = [[int(x) for x in input().split()] for y in range(n)]

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

for i in range(n):
    _v, _w = vw_l[i]
    for j in range(w+1):
        if j < _w:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i+1][j-_w] + _v, dp[i][j])

print(dp[n][w])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
v = [0] * N
w = [0] * N

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

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

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

print(dp[W])

Submission status: Accepted

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

dp = [0] * (W+1)

value = []
weight = []

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

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

print(dp[W])

Submission status: Accepted

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

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] = max(dp[i][j], dp[i][j-w[i]]+v[i], dp[i+1][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]

print(max(dp[n]))

Submission status: Accepted

Solution code:
def solve():
    N, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    dp = [0]*(W+1)
    for w in range(1,W+1):
        for i in range(N):
            if A[i][1]<=w:
                dp[w] = max(dp[w],dp[w-A[i][1]]+A[i][0])
    ans = dp[-1]
    return ans
print(solve())

Submission status: Accepted

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


dp=[[-float('inf')]*(W+1) for i in range(N+1)]
for i in range(W+1):
    dp[0][i]=0
for i in range(1,N+1):
    dp[i][0]=0

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

print(dp[N][W])

Submission status: Accepted

Solution code:
def main():
    _, W, *C = map(int, open(0).read().split())
    dp = [0]*(W+1)
    for v, w in zip(*[iter(C)]*2):
        for i in range(w, W+1):
            d_new = dp[i-w]+v
            if dp[i] < d_new:
                dp[i] = d_new
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    N, W = map(int, readline().rstrip().split())
    dp = [0] * (W + 1)

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

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
v, w = [0] * N, [0] * N
for i in range(N):
    v[i], w[i] = map(int, input().split())
# dp[i][j]:i番目までの種類を使って、総和がj の時の最大価値
dp = [[0] * (W + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(W + 1):
        if j >= w[i - 1]:
            dp[i][j] = max(
                dp[i - 1][j],
                dp[i][j - w[i - 1]] + v[i - 1],
            )
        else:
            dp[i][j] = dp[i - 1][j]
print(max(dp[N]))
#print(dp)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, WM = map(int, input().split())
V = [0] * N
W = [0] * N

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

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

Submission status: Accepted

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

# 品物の数ループ
for _ in range(N):
    value, weight = map(int, input().split())
    for i in range(weight, W+1):
        if dp[i-weight] != -1:
            dp[i] = max(dp[i], dp[i-weight]+value)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')


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

# dp[w] := 重さがwを超えないように品物をいくつか選んだときの価値の和の最大値
# dp[w] = max(dp[w], dp[w-w_list[i]] + v_list[i])

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

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

# pprint(dp)
print(dp[W])

Submission status: Accepted

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

inf = float("inf")
dp = [[-inf for _ in range(W+1)] for _ in range(N+1)]
for w in range(W+1):
    dp[0][w] = 0

value = []
weight = []

for _ 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], dp[i+1][w-weight[i]]+value[i])
            #3項目が重複を許すもの。wが1ずつ増えていき、今回のwの最小は1なので、左のvalueも使える
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Accepted

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

product = [(0,0)]
for _ in range(N):
    v,w = map(int,input().split())
    product.append((w, v))

#縦が商品i，横が仮想カバンの耐久値
#i番目までの商品だけを使って，耐久wのカバンの価値を最大化していく
dp = [[-float('inf')]*(W+1) for _ in range(N+1)]

for i in range(N+1):
    for w in range(W+1):
        if i == 0:
            dp[i][w] = 0
            continue
        if w == 0:
            dp[i][w] = 0
            continue
        if product[i][0] > w:
            dp[i][w] = dp[i-1][w]
        else:
            not_choice = dp[i-1][w]
            choice = dp[i-1][w-product[i][0]] + product[i][1]
            same_choice = dp[i][w-product[i][0]] + product[i][1]#重複を許して選ぶことに相当
            dp[i][w] = max(not_choice, choice, same_choice)
print(max(dp[N]))

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
dp = [0]*(w+1) # DPテーブルの作成
v = []
W = []
for i in range(n):
    v_,w_ = map(int,input().split())
    v.append(v_)
    W.append(w_)
for i in range(n):
    for j in range(W[i],w+1):
        if j >= W[i]:
            a = j // W[i]
            dp[j] = max(dp[j],dp[j-W[i]]+v[i])
        else:
            dp[j] = dp[j]
print(dp[w])