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:
N, totalWt = list(map(int, input().split()))
itemsVal = [0]
itemsWt = [0]
for i in range(0, N):
    val, weight = list(map(int, input().split()))
    itemsVal.append(val)
    itemsWt.append(weight)

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


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

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

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 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]:
            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())
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]:
            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())
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:
      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())
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 j in range(W+10)] for i in range(N+10)]
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 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:
            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())
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)]

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

print(dp[N][W])

Submission status: Accepted

Solution code:
# 35

# 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):
    for j in range(w+1):
        _v, _w = vw_l[i]
        if j < _w:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][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] = 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-1][j-w[i]])
print(dp[i][j])

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, -1):
        if j - weight[i] >= 0:
            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())
value, weight = [], []
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)]
for i in range(W+1):
    dp[0][i] = 0
for i in range(N):
    for w in range(W+1):
        if weight[i] <= w:
            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:
N, W = map(int, input().split())
vw = [list(map(int, input().split())) for _ in range(N)]

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 vw[i][1] <= w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
            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:
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, -1):
            d_new = dp[i]+v
            if dp[i+w] < d_new:
                dp[i+w] = d_new
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dp = [[0]*(W+1) for i in range(N+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:
N,W=map(int,input().split())
G=[]
for i in range(N):
    G.append(list(map(int,input().split())))

#dp[i][j]=iまで考え、重さがj以下
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(N):
    v=G[i][0]
    w=G[i][1]
    for j in range(W+1):
        if j>=w:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
        else:
            dp[i+1][j]=dp[i][j]

print(dp[N][W])

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

    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

inf = float("inf")
dp = [[ -inf 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 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)
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:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-product[i][0]] + product[i][1])
print(max(dp[N]))

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
dp = [[0]*(w+1) for j in range(n+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+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(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 _ in range(W + 1)] for _ in range(N + 1)]

for i in range(N):
    for j in range(W + 1):
        v, w = vw[i]

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

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

print(dp[N][W])

Submission status: Accepted

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

vaw = [0 for i in range(W+1)]
for i in range(len(v)):
    for k in range(len(vaw)):
        j = len(vaw) - k - 1
        if vaw[j] != 0 and j+w[i]<=W:
            vaw[j+w[i]] = max(vaw[j+w[i]], vaw[j]+v[i])

    vaw[w[i]] = max(vaw[w[i]], v[i])

print(max(vaw))

Submission status: Accepted

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

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

for i in range(N):
    for j in range(1,W+1000):
        if j - items[i][1] >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i][j-items[i][1]]+items[i][0])
        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]*(W+1) for _ in range(N+1)]

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

Submission status: Accepted

Solution code:
def solve(N,W,knap):
    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 dp[i-1][j]>-1:
                dp[i][j]=dp[i-1][j]
            if j-knap[i][1]>=0:
                if dp[i-1][j-knap[i][1]]>-1:
                    dp[i][j]=max(dp[i][j],dp[i-1][j-knap[i][1]]+knap[i][0])
    return max(dp[N])

N,W=map(int,input().split())
knap=[(0,0)]+[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)
    item = [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 w >= item[i][1]:
                dp[i+1][w] = max(dp[i][w], dp[i][w-item[i][1]]+item[i][0])
            else:
                dp[i+1][w] = dp[i][w]
    print(max(dp[N]))
    """
    """ 使い回す方 """
    dp = [0]*(W+1)
    for i in range(N):
        for w in range(W, -1, -1):
            if item[i][1] <= w:
                dp[w] = max(dp[w], dp[w-item[i][1]]+item[i][0])
    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
v = []
ww = []
for _ in range(n):
    a, b = map(int, input().split())
    v.append(a)
    ww.append(b)

dp = [[-1e9 for _ in range(w+1)] for _ in range(n+1)]
#dp[i][j] = i番目まで見た時、重さjまででできる最大の価値, 0<=i<=n, 0<=j<=w

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

for i in range(n):
    for j in range(w+1):
        if (j >= ww[i]):#w以下ならww[i]を入れた時とそうでない時で比較
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]] + v[i])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[n][w])

Submission status: Accepted

Solution code:
n, targetw = map(int,input().split())
dp = [[0 for i in range(targetw+1)] for j in range(n+1)]

for i in range(n):
	tmpv, tmpw = map(int, input().split())
	for j in range(1, targetw+1):
		if j >= tmpw:
			dp[i+1][j] = max(dp[i][j-tmpw]+tmpv, dp[i][j])
		else:
			dp[i+1][j] = dp[i][j]

print(dp[n][targetw])

Submission status: Accepted

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

# dpi[j] := i番目以降のものでjのコストで実現できる最大の価値
dp = [0] * (W + 1)

for i in range(n):
    for j in range(W, w[i]-1, -1):
        #w[i]よりjが小さい時はそのコストを払えないので考えない
        #jを上から考えれば小さなjについてはまだ前のテーブルが残ってる
        dp[j] = max(dp[j], dp[j-w[i]] + v[i])

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

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

for i in range(n):
    for j in range(w+1):
        if memo[i][j] > -1 and j+items[i][1] <= w:
            memo[i+1][j+items[i][1]] = max(memo[i+1][j+items[i][1]], memo[i][j]+items[i][0])
        memo[i+1][j] = max(memo[i+1][j], memo[i][j])

print(max(memo[-1]))

Submission status: Accepted

Solution code:
# DPL_1_B - 0,1ナップザック問題　
# 配るDPで解いてみる

import sys

N, C = map(int, sys.stdin.readline().strip().split())  # C: content 容量

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

# dp 配列の初期化
dp = [[0] * (C + 1) for _ in range(N + 1)]


for n in range(N):
    for c in range(C + 1):
        dp[n + 1][c] = max(dp[n + 1][c], dp[n][c])

        if c + w[n] <= C:
            dp[n + 1][c + w[n]] = max(dp[n][c] + v[n], dp[n + 1][c + w[n]])

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    import sys
    N, W = map(int, sys.stdin.readline().split())
    L = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
    #print(L)
    dp = [[0 for i in range(W+1)] for j in range(N)]
    #初期設定
    dp[0][L[0][1]] = L[0][0]
    for i in range(1, N):
        dp[i] = dp[i-1].copy() #1.前回データの更新
        v, w = L[i][0], L[i][1]
        dp[i][w] = max(dp[i][w], v) #2.今回データの挿入
        for j in range(W+1): #3.足し算データ更新
            if dp[i-1][j] !=0 and j+w<=W:
                dp[i][j+w] = max(dp[i-1][j]+v, dp[i-1][j+w]) 
    print(max(dp[-1]))


if __name__=='__main__':
    main()

Submission status: Accepted

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

# https://qiita.com/e869120/items/eb50fdaece12be418faa
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja


def main():
    n, w_limit = map(int, input().split())
    v, w = [0], [0]
    for _ in range(n):
        vi, wi = map(int, input().split())
        v.append(vi)
        w.append(wi)

    print(napzac(v, w, w_limit))


def napzac(v, w, w_limit):
    n = len(v)
    dp = [[0] * (w_limit + 1) for _ in range(n + 1)]  # dp の i だけ 1 origin..

    for i in range(n):
        for j in range(w_limit + 1):

            if j < w[i]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(
                    dp[i][j],
                    dp[i][j - w[i]] + v[i]
                )
    return dp[n][w_limit]


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

for i in range(n):
    for j in range(w + 1):
        if j >= we[i]:
            dp[i + 1][j] = max(dp[i][j - we[i]] + v[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())
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):
        if w <= j:
            dp[i+1][j] = max(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:
import sys

N, W = [int(i) for i in sys.stdin.readline().rstrip("\n").split()]
goods_v = []
goods_w = []
for _ in range(N):
    elem = [int(i) for i in sys.stdin.readline().rstrip("\n").split()]
    goods_v.append(elem[0])
    goods_w.append(elem[1])
    
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if w >= goods_w[i]:
            dp[i+1][w] = max(dp[i][w], dp[i][w-goods_w[i]] + goods_v[i])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N,W = [int(x) for x in input().split()]
    vl,wl = [],[]
    for _ in range(N):
        v,w = [int(x) for x in input().split()]
        vl.append(v)
        wl.append(w)

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

    for i in range(N):
        for j in range(W+1):
            # print(i,j)
            if j < wl[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j],dp[i][j-wl[i]]+vl[i])
            # print(dp)
    print(int(dp[N][W]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, MAX_W = map(int, input().split())  # N: 品物数, MAX_W: ナップサックの容量
items = [list(map(int, input().split())) for _ in range(N)]  # items[i]: i番目の品物の（価値, 重さ）


# dp[i][j] := i番目の品物までみた時に、重さの総和がj以下であるように品物を入れた場合の価値の総和の最大値
# 0番目、重さ0も考慮しているのが少しポイント！
dp = [[0] * (MAX_W + 1) for _ in range(N + 1)]

# ここからdpテーブルを順に埋めていく
for i, (v, w) in enumerate(items):
    for j in range(MAX_W + 1):  # Pythonは + 1 しないと MAX_W番目まで計算しないため
        # 次の品物を入れない場合
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

        # 次の品物を入れてもナップサックの容量を超えないか判定
        if j + w <= MAX_W:
            # 次の品物を入れる場合
            dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)


# N番目の品物までみた時に、重さの総和がナップサックの容量以下であるように品物を入れた場合の価値の総和の最大値 が答え！
print(dp[N][MAX_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 weight[i]<=w:
            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[nn][ww])

Submission status: Accepted

Solution code:
#  価値が vi 重さが wi であるような N 個の品物と、容量が W のナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます：
#     選んだ品物の価値の合計をできるだけ高くする。
#     選んだ品物の重さの総和は W を超えない。
# 価値の合計の最大値を求めてください。 

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

# print(w)


# dpテーブル（縦は個数N, 横は価値Wの最大値（多めに取ればよろし）
# このように、横軸に価値Wを全部とってもとめちゃえとするのがコツと思われる

# dp[i+1][w] = i 番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値
# i番目の品物（value[i], weight[i]）が選ばれるということは、w - weight[i] > 0であるときは選べば良くて、
# dp[i][w - weight[i]] + value[i]
# そうでないときは更新できない。

dp = [[0] * 10010 for _ in range(110)] # 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])
        else:
            dp[i+1][w] = dp[i][w]

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, W = il()
    VW = [il() 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 w >= VW[i][1]:
                dp[i+1][w] = max(VW[i][0] + dp[i][w-VW[i][1]], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
    print(dp[N][W])


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 = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
	for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
#print(dp)
print(dp[N][W])

Submission status: Accepted

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

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

for i in range(n):
    cv, cw = IN[i]
    for j in range(w + 1):
        if j - cw >= 0:
            DP[i + 1][j] = max(DP[i][j - cw] + cv, DP[i][j])            
        else:
            DP[i + 1][j] = DP[i][j]
print(max(sum(DP, [])))

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
v=[]
w=[]
for i in range(N):
  x,y=map(int,input().split())
  v.append(x)
  w.append(y)
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(W+1):
      if(j-w[i-1]>=0):
          dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
      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] * (W+1)
for i 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-wi] + vi, dp[j])
    dp = ndp
print(dp[W])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, W = MAP()

v, w = [0]*N, [0]*N
dp = [0]*(W+1)

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

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

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][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:
n, w = map(int, input().split())
weight = [0] * n
values = [0] * n
for i in range(n):
    a, b = map(int, input().split())
    weight[i] = b
    values[i] = a

def chmax(a, b):
    if a > b:
        return a
    else:
        return b

dp = [[0] * (w + 10) for _ in range(n + 10)]
for i in range(n):
    for sum_w in range(w + 1):
        if sum_w >= weight[i]:
            dp[i + 1][sum_w] = chmax(dp[i][sum_w - weight[i]] + values[i], dp[i][sum_w])
        else:
            dp[i + 1][sum_w] = dp[i][sum_w]

print(dp[n][w])

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n, w = map(int, input().split())
    v = []
    ws = []
    for _ in range(n):
        vi, wi = map(int, input().split())
        v.append(vi)
        ws.append(wi)
    
    dp = []
    for _ in range(n + 1):
        dp.append([0] * (w + 1))
    # dp[1][w[0]] = v[0]
    
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            dp[i][j] = dp[i - 1][j]
            if j - ws[i - 1] >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - ws[i - 1]] + v[i - 1])
    ans = (-1) * float('inf')
    print(max(dp[n]))