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:
N, W = 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 j in range(W + 1):
        v, w = vw[i]

        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

        if j >= w:
            dp[i + 1][j] = max(dp[i + 1][j - w] + v, dp[i][j])


print(dp[N][W])

Submission status: Accepted

Solution code:
"""何回でも同じ荷物を選べるナップザック問題"""
def main():
    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[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-1]>=0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+v[i-1])
                dp[i][j] = max(dp[i][j], dp[i][j-w[i-1]]+v[i-1])
            dp[i][j] = max(dp[i][j], dp[i-1][j])
    print(dp[N][W])

main()

Submission status: Accepted

Solution code:
def solve(N,W,knap):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(0,N):
        v,w=knap[i]
        for j in range(w,W+1):
            if dp[j-w]!=-1:
                dp[j]=max(dp[j],dp[j-w]+v)
    return max(dp)

N,W=map(int,input().split())
knap=[tuple(map(int,input().split())) for _ in range(N)]
print(solve(N,W,knap))

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    # (v, w)
    items = [tuple(map(int, input().split())) for _ in range(N)]
    """
    使い回さない
    dp = [[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        for w in range(W+1):
            if items[i][1] > w:
                dp[i+1][w] = dp[i][w]
            else:
                dp[i+1][w] = max(dp[i][w], dp[i+1][w-items[i][1]]+items[i][0])
    print(max(dp[N]))
    """
    """ 使い回す方 """
    dp = [0]*(W+1)
    for i in range(N):
        for w in range(W+1):
            if items[i][1] <= w:
                dp[w] = max(dp[w], dp[w-items[i][1]]+items[i][0])
    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
vw = [0] * N
for i in range(N):
  vw[i] = list(map(int, input().split()))
  
#vw = sorted(vw, key = lambda, x:x[1]) 
            
dp = [0] * (W + 1)
for i in range(W + 1):
  for j in range(N):
    if i >= vw[j][1]:
      dp[i] = max(dp[i], dp[i - vw[j][1]] + vw[j][0])
  
print(dp[-1])

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+1)]
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:
def solve(N, W, vals, weights):
    dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
    for i in range(N):
        for w in range(W + 1):
            if weights[i] <= w:
                dp[i + 1][w] = max(dp[i + 1][w - weights[i]] + vals[i], dp[i][w])
            else:
                dp[i + 1][w] = dp[i][w]
    print(dp[N][W])

if __name__ == "__main__":
    N, W = map(int, input().split())
    vals = []
    weights = []
    for _ in range(N):
        v, w = map(int, input().split())
        vals.append(v)
        weights.append(w)
    solve(N, W, vals, weights)

Submission status: Accepted

Solution code:
# DPL_1_B - 0,1ナップザック問題
# 貰う DP で回答

import sys
import math

N, W = map(int, sys.stdin.readline().strip().split())

item = []
for n in range(N):
    v, w = map(int, sys.stdin.readline().strip().split())
    item.append((v, w))


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

# dp 実行
for n in range(N):
    for w in range(W + 1):
        if w - item[n][1] >= 0:
            dp[n + 1][w] = max(dp[n][w], dp[n + 1][w - item[n][1]] + item[n][0])
        else:
            dp[n + 1][w] = dp[n][w]


# for i in range(len(dp)):
#     print(dp[i])

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

Submission status: Accepted

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

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

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

print(dp[N % 2][W])

Submission status: Accepted

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

#dp[i][u] := i個目までで重さu以下での最大の価値
#0個目までなら0なのは自明
dp = [[0] * (w+1) for _ in range(n+1)]

#dp[i][なんでも]がわかっているときにdp[i+1][u]を考える
for i in range(n):
    for u in range(w+1):
        #i+1個目の重さが残りの重さより重かったら，i+1個目は使えない
        if u < items[i][1]:
            dp[i+1][u] = dp[i][u]
        #i+1個目が使えるとき，考えうるのはi+1個目を使うか使わないか
        #使うとき，実は比べるのは１つ少なく使ったときに対して使った時が最大効率
        else:
            dp[i+1][u] = max(dp[i][u], dp[i+1][u-items[i][1]] + items[i][0])

print(dp[n][w])

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

Submission status: Accepted

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

# i個目までの品物から重さがwを超えないように選んだ時の価値の最大値
dp = [[0] * (W + 1) for _ in range(N + 1)]

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

print(dp[N][W])

Submission status: Accepted

Solution code:
nn,ww=map(int,input().split())
value=[0]*nn
weight=[0]*nn
for i in range(nn):
    value[i],weight[i]=map(int,input().split())    

dp=[[0]*(ww+1) for i in range(nn+1)]
for w in range(ww+1):
    dp[0][w]=0
    
for i in range(nn):
    for w in range(ww+1):
        if w-weight[i]>=0:
            dp[i+1][w]=max(dp[i][w],dp[i][w-weight[i]]+value[i],dp[i+1][w-weight[i]]+value[i])
        else:
            dp[i+1][w]=dp[i][w]

print(dp[nn][ww])

Submission status: Accepted

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

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

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

print(dp[W])

Submission status: Accepted

Solution code:
n, w_max = map(int, input().split())
X = []
for _ in range(n):
    X.append(list(map(int, input().split())))

W = [0] * (w_max + 1)

for i in range(len(W)):
    for x in X:
        xv, xw = x[0], x[1]
        if i - xw >= 0:
            W[i] = max(W[i], W[i - xw] + xv)

print(max(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 w in range(W + 1):
    for value, weight in items:
        if weight <= w:
            dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[W])

Submission status: Accepted

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

for _ in range(N):
    vi, wi = map(int, input().split())
    ndp = [0] * (W+1)
    for j in range(W+1):
        if j < wi:
            ndp[j] = dp[j]
        else:
            ndp[j] = max(dp[j], ndp[j-wi] + vi)
    dp = ndp 
print(dp[W])

Submission status: Accepted

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

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

# dp[i+1][w]:i番目までの品物を入れたとき、wを超えない最大価値

dp = [[0]*(10**4+10) for _ in range(110)]
def rec(i,w):
    dp[i+1][w] = dp[i][w] #i番目は入れない

    if w-weight[i] >= 0:
        dp[i+1][w] = max(dp[i+1][w-weight[i]] + value[i], dp[i][w])

for i in range(N):
    for j in range(W+1):
        rec(i,j)
print(dp[N][W])

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n, w_size = map(int, input().split())
    v = []
    w = []
    for _ in range(n):
        vi, wi = map(int, input().split())
        v.append(vi)
        w.append(wi)
    
    dp = [[0] * (w_size + 1)] * n

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

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

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
listV, listW = [], []
for i in range(n):
    vi, wi = map(int, input().split())
    listV.append(vi)
    listW.append(wi)

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

for i in range(n):
    for j in range(w+1):
        if j >= listW[i]:
            dp[i+1][j] = max(dp[i+1][j-listW[i]] + listV[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())
item = [list(map(int,input().split())) for i in range(N)]

dp = [0] * (W + 1)

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

Submission status: Accepted

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

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

Submission status: Accepted

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

def main():
    N,W = map(int,input().split())
    item = [tuple(map(int,input().split())) for _ in range(N)]
    dp = [0]*(W + 1)
    for v,w in item:
        for j in range(w,W + 1):
            dp[j] = max(dp[j],dp[j - w] + v)
    print(dp[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=ja
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,W,*vw = map(int, read().split())

    VW = []
    for v, w in zip(*[iter(vw)]*2):
        VW.append((v, w))

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

    for i in range(N):
        v_i, w_i = VW[i]
        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+1][j - w_i] + v_i, dp[i][j])

    print(dp[N][W])    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    import sys

    N, W = list(map(int, sys.stdin.readline().split()))

    dp = [0 for i in range(W+1)]  # dp[w] := 重さの総和がw以下のときの価値の最大値

    for _ in range(N):
        v, w = list(map(int, sys.stdin.readline().split()))

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

    print(dp[W])


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

dp = [0] * (w + 1)
# (v, w)
weight = []
value = []
for _ in range(n):
    v, we = map(int, input().split())
    weight.append(we)
    value.append(v)

# dp[i+1][w] i番目までの品物の中から重さがWを超えないように選んだ時の価値の総和の最大値
#              weight[i]を引いた時の最大値
# dp[i+1][w] = dp[i][w-weight[i]]+value[i]
# 入れない時
# dp[i+1][w] = dp[i][w]

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

# print(dp)

print(dp[w])

Submission status: Accepted

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

dp = [0] * (w+1)

for i in range(w+1):
    for value, weight in items:
        x = i + weight
        if x > w:
            continue
        dp[x] = max(dp[i] + value, dp[x])

print(dp[w])

Submission status: Accepted

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

dp = [0]*(W+1)
L = []
for i in range(N):
    ta,tb = map(int,input().split())
    L.append([ta,tb])

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

Submission status: Accepted

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

value,weight = [],[]
for i in range(N):
    v,w = map(int,input().split())
    value.append(v)
    weight.append(w)
    
dp = [[0 for i in range(W+10)] for j in range(N+10)]    

# < DP初期配列 >
# i\w  0  1  2  3  ...  W
#  0   0  0  0  0  ...  0
#  1   0  0  0  0  ...  0
#           ...
#  N-1 0  0  0  0  ...  0
#  N   0  0  0  0  ...  0
# dp[i+1][j] = (荷物iまで選んだ場合、および重さがj-1までで荷物i+1を選んだ場合)から算出される
#               荷物0,1,...,iを重複含んで選んで重さjとなる場合の価値の最大値
#
# < DP遷移式 >
# if(w>=weght[i]):   # 荷物iを採用できるなら
#      dp[i+1][w] =  min(dp[i][w-weight[i]],    # 荷物iを採用 
#                        dp[i][w],              # 荷物iを採用しない
#                        dp[i+1][w-weight[i]],) # 荷物iを重複を許して採用 
#                                             → 1つ前のループだけでなく、同じル-プ(直前の更新情報)まで使用することで「複数回荷物を選ぶ」という操作を実現している
# elif(w<weight[i]): # 荷物iを採用できないなら
#      dp[i+1][]w = dp[i][w]  # 荷物iを採用しない


for i in range(N):
  for w in range(W+1):
    if(w>=weight[i]): # 荷物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 = [0] * N
w = [0] * N
for i in range(N):
    v[i], w[i] = map(int, input().split())

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

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

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

Submission status: Accepted

Solution code:
N,W = list(map(int,input().split()))
vals = []
weis = []
for i in range( N):
    v,w =list(map(int,input().split()))
    vals.append(v)
    weis.append(w)
dp=[0] * (W+1)
for i,v in enumerate(vals):
    for w in range(weis[i], W+1):
        dp[w] = max(dp[w], dp[w-weis[i]] +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[i]: 重さがiとなるように選んだ時の合計価値の最大値
dp = [0]*(W+1)

dp[0] = 0

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

Submission status: Accepted

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

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

for i in range(1,1+N):
    for j in range(10100):
        if j-W[i-1] >= 0:
            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(dp[N][WI])

Submission status: Accepted

Solution code:
import sys

N, W = map(int, sys.stdin.readline().strip().split())
weights = []

for _ in range(N):
    v, w = map(int, sys.stdin.readline().strip().split())
    weights.append((v, w))

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

print(max(dp))

Submission status: Accepted

Solution code:

def main():
    N, W = map(int, input().split())
    DP = [-1]*(W+1)
    DP[0] = 0
    for i in range(N):
        v, w = map(int, input().split())
        for j in range(w, W+1):
            if DP[j-w] == -1:
                continue
            else:
                DP[j] = max(DP[j], DP[j-w] + v)
    
    ans = 0
    for k in range(W+1):
        ans = max(ans, DP[k])
    #print(DP)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    
    N, W = map(int, input().split())
    item = [tuple(map(int, readline().split())) for _ in range(N)]
    INF = float('inf')
    dp = [-INF] * (W + 1)
    dp[0] = 0
    for i in range(N):
        v, w = item[i]
        for j in range(W + 1 - w):
            dp[j + w] = max(dp[j] + v, dp[j + w])
    
    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def knapsack_duplicate(N, W, weight, value):
    # initialize
    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

    # DP
    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]
    return dp[N][W]


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

Submission status: Accepted

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

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

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

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] = max(DP[i + 1][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:
n, w = map(int, input().split())
vw = [[int(i) for i in input().split()] for _ in range(n)]
dp = [[-1 for _ in range(w + 1)] for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][i] = 0
for i in range(n):
    for j in range(w + 1):
        if vw[i][1] > j:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - vw[i][1]] + vw[i][0])
print(dp[n][w])

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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): # watasu=
    v, w = vw[i-1]
    for j in range(W+1):
        if j-w>=0:
            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(max(dp[N]))

Submission status: Accepted

Solution code:
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 for _ in range(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[-1][-1])

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

Submission status: Accepted

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

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

Submission status: Accepted

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


"""
  dp[i + 1][j] i番目までの品物から，総和がj以下になるように選んだときの最大値
  - dp[0][j] = 0
  - dp[i+1][j] = max{ dp[i][j - k w[i]] + k v[i] | 0 <= k}
"""

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

for i in range(n):
    for j in range(w + 1):
        # k = 0
        # while k * item[i][1] <= j:
        #     dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k * item[i][1]] + k * item[i][0])
        #     k += 1
        if j < item[i][1]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - item[i][1]] + item[i][0])
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]*(w+1)
for i in range(w+1):
    for volume,weight in VW:
        if 0<=i+weight<=w:
            DP[i+weight]=max(DP[i+weight],DP[i]+volume)
print(max(DP))

Submission status: Accepted

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

import sys
from collections import namedtuple

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

Item = namedtuple("Item", ("value", "weight"))

def main():
    n, max_w = read_list(int)
    items = []

    for _ in range(n):
        v, w = read_list(int)
        items.append(Item(v, w))
    
    dp = [0] * (max_w + 1)
    for w_i in range(max_w + 1):
        for i in range(len(items)):
            if w_i >= items[i].weight:
                dp[w_i] = max(dp[w_i], dp[w_i - items[i].weight] + items[i].value)
    print(dp[max_w])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=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]*(m+1)
for i in range(n):
    for j in range(1,m+1):
        if j>=w[i]:
            dp[j]=max(dp[j],dp[j-w[i]]+v[i])
print(dp[m])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, W = map(int, input().split())
    vw = [list(map(int, input().split())) for _ in range(N)]

    # 重さiの場合の最大価値
    dp = [0]*(W+1)

    for i in range(1, W+1):
        for j in range(N):
            v_j = vw[j][0]
            w_j = vw[j][1]
            if i-w_j>=0:
                dp[i] = max(dp[i-w_j]+v_j, dp[i])

    print(dp[W])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

dp = [0] * (W+1)

for k in range(1,W+1):
  dpk = 0
  for m in range(N):
    if(k-weight[m] >= 0):
      tmp = dp[k-weight[m]] + value[m]
      if(tmp > dpk):
        dpk = tmp
  dp[k] = dpk

print(dp[W])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
V = []
for i in range(N):
    V.append(list(map(int, input().split())))
    
DP = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

Submission status: Accepted

Solution code:
N,M = map(int, raw_input().split())
V,W = [],[]
for i in range(N):
    v,w = map(int, raw_input().split())
    V.append(v)
    W.append(w)

DP = [0]*(M+1)

for w in range(1, M+1):
    for i in range(N):
        if W[i] <= w:
            DP[w] = max(DP[w], DP[w-W[i]] + V[i])

print DP[M]

Submission status: Accepted

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

# dp[この重さを超えないレベルで] = 価値の最大値となるような一次元配列
dp = [0] * (W+1)

for i in range(N):
    v, w = items[i]
    # 個数制限ありでは同じものを使わないように後ろから更新したが、今回は逆に同じものを使うように前から更新する
    for j in range(w, W+1):
        # jを超えない重さであれば、前の要素番号まででこの重さを引いた数値の価値と今回の価値を足したものが上回れば今回の価値とする
        dp[j] = max(dp[j], dp[j-w] + v)
print(dp[W])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
VW = [tuple(map(int, input().split())) for i in range(n)]
V = [v for v, w in VW]
W = [w for v, w in VW]
# n, m = 4, 8
# V = [4, 5, 2, 8]
# W = [2, 2, 1, 3]
# DP[i][j]=i個の品物で重さj以内で最大価値
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(m+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][m])

Submission status: Accepted

Solution code:
import sys,bisect
sys.setrecursionlimit(15000)

n,w = map(int,sys.stdin.readline().split())
a = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
dp = [0]*(w+1)

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

Submission status: Accepted

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

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

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

dps = [[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):
        if i == 1:
            if j >= weights[i]:
                dps[i][j] = values[i] * (j // weights[i])
        else:
            if j >= weights[i]:
                dps[i][j] = max(dps[i][j - (weights[i])] +
                                values[i], dps[i - 1][j])
                # for k in range(j // weights[i] + 1):
                # dps[i][j] = max(dps[i][j - (weights[i] * k)] + (values[i] * k),
                #                 dps[i][j])
                dps[i][j] = max(dps[i][j], dps[i][j - 1])
            else:
                dps[i][j] = max(dps[i][j - 1], dps[i - 1][j])
print(dps[N][W])

Submission status: Accepted

Solution code:
n,w0=map(int,input().split())
v=[]
w=[]
for _ in range(n):
	V,W=map(int,input().split())
	v.append(V)
	w.append(W)

#knapsack with no restriction
dp=[[0]*(w0+1) for _ in range(n+1)]
#print(dp)
for i in range(n):
	for j in range(w0+1): #iが小さいほうから埋まっていくので昇順
		if j-w[i]<0:
			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][w0])
#dp[0][j]は0番目まで選んだとする。何も選んでないと言うこと。
#通常のナップサックの場合、何も選んでいないのはdp[n][j]。n番目以降から選ぶが、番号は[0:n-1]でふられている。

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def make4(initial, L, M, N, O):
    return [[[[initial for i in range(O)]
                for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def make3(initial, L, M, N):
    return [[[initial for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N, W = MI()
    v = [0] * N
    w = [0] * N
    dp = [[0] * (W+1) for i in range(N+1)]

    for i in range(N):
        v[i], w[i] = MI()

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

if __name__ == '__main__':
    main()

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

print(dp[-1])

Submission status: Accepted

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

	dp = [0] * (W + 1)
	
	for item in items:
		v, w = item
		for i in range(W - w + 1):
			if dp[i + w] < dp[i] + v:
				dp[i + w] = dp[i] + v
	print(max(dp))