Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]

wv.sort(key=lambda x: -x[1])
margin = [0] * (N + 1)
sum_tmp = 0
for i, (wi, vi) in list(enumerate(wv))[::-1]:
    sum_tmp += vi
    margin[i] = sum_tmp

ans = 0
task = [(0, 0, 0)] # index, weight, value
while len(task) > 0:
    i, w, v = task.pop()
    # print('#', i, w, v)
    if v + margin[i] < ans: continue # margin[N] = 0
    elif i == N: ans = v
    else:
        dw, dv = wv[i]
        task.append((i + 1, w, v))
        if w + dw <= W: task.append((i + 1, w + dw, v + dv))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, capacity = map(int, input().split())
    w = []
    v = []

    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    
    print(solve(w, v, n, capacity))

def memoize(func):
    memo = dict()

    def wrapper(i, w):
        key = (i, w)
        if key in memo:
            return memo[key]
        else:
            v = func(i, w)
            memo[key] = v
            return v
    
    return wrapper

def solve(weights, values, n, capacity):
    @memoize
    def sub(i, w):
        if i == 0:
            return 0
        if w == 0:
            return 0

        if weights[i - 1] <= w:
            return max(sub(i - 1, w - weights[i - 1]) + values[i - 1], sub(i - 1, w))
        else:
            return sub(i - 1, w)

    return sub(n, capacity)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, capacity = map(int, input().split())
    w = []
    v = []

    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    
    print(solve(w, v, n, capacity))

def solve(weights, values, n, capacity):
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

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

    return dp[i + 1][capacity]


main()

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import numpy as np
N,W = list(map(int, input().split()))
wlist = [tuple(map(int, input().split())) for _ in range(N)]
suml = [0 for _ in range(W+1)]

V = [[0 for _ in range(W+1)] for _ in range(N+1)]
for e,item in enumerate(wlist,1):
    w,v = item
    for wpoint in range(W+1):
        if w <= wpoint:
            V[e][wpoint] = max(V[e-1][wpoint -w] + v,
                     V[e][wpoint])
        else:
            V[e][wpoint] = V[e-1][wpoint]

# print(V)
print(np.array(V).max())



# # w, v
# for i in range(W+1):
#     for w,v in wlist:
#         if not (i+w) <= W:
#             continue
#         suml[i+w] = max(
#             suml[i+w],
#             suml[i] + v
#         )
#         print("\tsuml[{}+{}]: {}".format(i,w,suml[i+w]))
#         print("\tsuml[{}]:{} + v:{}".format(i, suml[i], v))
#     print(suml)
# print(max(suml))

Submission status: Time Limit Exceeded

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

f = [0 for i in range(w + 1)]
for i in range(n) : 
    cw, cv = map(int, input(). split())
    for j in range(w, cw - 1, -1) : 
        f[j] = max(f[j], f[j - cw] + cv)

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

Submission status: Time Limit Exceeded

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

a = []
b = []

for _ in range(n):
    x, y = map(int, input().split())

    a.append(y)
    b.append(x)

t = [[0 for x in range(w + 1)] for y in range(n + 1)]

for i in range(1, n+1):
    for j in range(1, w+1):
        if b[i-1] <= j:
            t[i][j] = max(a[i-1] + t[i-1][j - b[i-1]], t[i-1][j])
        else: t[i][j] = t[i-1][j]

print(t[n][w])

Submission status: Time Limit Exceeded

Solution code:
def ks(N, W, w, v):
    X = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
    for wi in range(1, W + 1):
        for n in range(N):
            if w[n] <= wi:
                X[n + 1][wi] = max(v[n] + X[n][wi - w[n]], X[n][wi])
            else:
                X[n + 1][wi] = X[n][wi]

    return X[-1][-1]

N, W = map(int, raw_input().split())
w, v = [], []
for _ in range(N):
    wi, vi = map(int, raw_input().split())
    w.append(wi)
    v.append(vi)
print(ks(N, W, w, v))

Submission status: Time Limit Exceeded

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

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

for i in range(1, N + 1):
    w[i], v[i] = [int(_) for _ in input().split()]

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

weight = [None] * N
value  = [None] * N

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

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

Submission status: Time Limit Exceeded

Solution code:
def knapsack(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1): dp[0][i]=0

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

    return dp[N][W]

N, W = [int(i) for i in input().split()]
weight =[]
value =[]
for i in range(N):
    x, y = [int(i) for i in input().split()]
    weight.append(x)
    value.append(y)

print(knapsack(N,W,weight,value))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(int, input().split()))
wv = [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(1, N+1):  # 1-indexed
    for j in range(1, W+1):
        if j >= wv[i-1][0]:
            dp[i][j] = dp[i-1][j-wv[i-1][0]]+wv[i-1][1]
        dp[i][j] = max(dp[i][j], dp[i-1][j])

print(max(dp[N]))

Submission status: Time Limit Exceeded

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

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

for item in range(0, N):
    for weight in range(W+1):
        if WV[item][0] <= weight:
            temp1 = dp[item-1][weight]
            temp2 = dp[item-1][weight-WV[item][0]] + WV[item][1]
            dp[item][weight] = max(temp1, temp2)
        else:
            dp[item][weight] = dp[item-1][weight]

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

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(n)]
knap = {(0,0)}
for weight,value in lis:
    gone = set()
    for num,now in knap:
        if num + weight <= w:gone.add((num+weight,now+value))
    for nn,nu in gone:
        knap.add((nn,nu))
ans = 0

for num,value in knap:
    ans = max(ans,value)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

dp[0][w[0]] = v[0]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print(max(dp.values()))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [[0] * (W+1)]
for i in range(N)[::-1]:
  a = []
  for w in range(W+1):
    if A[i] > w:
      a.append(dp[-1][w])
    else:
      a.append(
        dp[-1][w]
        if dp[-1][w] > dp[-1][w-A[i]] + V[i]
        else dp[-1][w-A[i]] + V[i]
      )
  dp.append(a)

print(dp[-1][W])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500)
N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

memo = {}
def dp(i, w):
  if (i, w) in memo:
    return memo[(i, w)]
  ret = None
  if i == N:
    ret = 0
  else:
    ret = dp(i+1, w)
    if A[i] <= w:
      ret2 = dp(i+1, w - A[i]) + V[i]
      ret = ret if ret > ret2 else ret2
  memo[(i, w)] = ret
  return ret

print(dp(0, W))

Submission status: Time Limit Exceeded

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

DP_W=[0]*(W+1)

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

print(max(DP_W))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
 
N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))
 
dp = defaultdict(int)
 
dp[0] = 0
 
for w,v in WV:
    for nw, nv in list(dp.items()):
        if nw+w <= W:
            dp[nw+w] = max(dp[nw+w], nv+v)
            
print(max(dp.values()))

Submission status: Time Limit Exceeded

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

for i in range(n):
    items.append(list(map(int, input().split())))


def knapsack(n, w, items):
    c = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    g = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = 1

    for i in range(n + 1):
        c[i][0] = 0

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = 0
            item = items[i - 1]
            if item[0] > j:
                continue
            if item[1] + c[i - 1][j - item[0]] > c[i - 1][j]:
                c[i][j] = item[1] + c[i - 1][j - item[0]]
                g[i][j] = 1

    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == 1:
            routes.append(i)
            w -= items[i - 1][0]
    return max_value, routes


result, _ = knapsack(n, w, items)
print(result)

Submission status: Accepted

Solution code:
weights, values = [], []

n, w = list(map(int, input().split()))
for _ in range(n):
    w_c, v_c = list(map(int, input().split()))
    weights.append(w_c)
    values.append(v_c)

dp = [[0 for i in range(w + 1)] for i in range(n + 1)]
for i in range(len(values) + 1):
    for j in range(w + 1):
        if i == 0 or j == 0: 
            dp[i][j] = 0
        elif weights[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
        else:
            dp[i][j] = dp[i - 1][j]
    
print(dp[-1][-1])

Submission status: Accepted

Solution code:
# メイン関数
def main():
    # 入力データ
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N):
        wi, vi = map(int, input().split())
        w.append(wi)
        v.append(vi)

    # dpテーブルの作成
    dp = [[0] * (W+1) for i in range(N)]
    for i in range(N):
        for j in range(W + 1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    # 解答の出力
    print(dp[-1][-1])
    return

# 実行
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w,v = [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N):
    w[i],v[i] = map(int,input().split())
# dp[i][w] = [合計重さ,重さw で得られる最大の価値v]
dp = [[0 for _ in range(W+1)] for i in range(N+1)]

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

# for i in dp:
#     print(i)
print(dp[N][W])

Submission status: Accepted

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

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


def wi(i):
    return wv[i - 1][0]


def vi(i):
    return wv[i - 1][1]


def value(i, w):
    if w - wi(i) >= 0:
        return max(dp[i - 1][w], dp[i - 1][w - wi(i)] + vi(i))
    else:
        return dp[i - 1][w]


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

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

Submission status: Accepted

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

DP = [[0] * (W + 2) for i in range(N + 2)]
"""
DP[0][W]
DP[i][j]
i:荷物の個数
j:残り容量
"""
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(max(DP[N]))

Submission status: Accepted

Solution code:
def main():
    N, Wei = map(int, input().split())
    W = [0] * N
    V = [0] * N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[0] * (Wei + 5) for _ in range(N + 5)]
    dp[0][Wei] = 0
    for i in range(N):
        for w in range(Wei+1):
            if w >= W[i]:
                dp[i+1][w] = max(dp[i][w-W[i]] + V[i], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]

    print(dp[N][Wei])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

    dp = [0] * (w + 1)
    for wi, vi in wv:
        for sum_w in range(w, wi - 1, -1):
            v = dp[sum_w - wi] + vi
            if dp[sum_w] < v:
                dp[sum_w] = v

    print(dp[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):
    w, v = map(int, input().split())

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

Submission status: Accepted

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

#import
#import math
#import numpy as np
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (W + 1)

for w, v in wv:
    for i in range(W, 0, -1):
        if i - w < 0:
            break

        dp[i] = max(dp[i], dp[i - w] + v)
            
print(dp[W])

Submission status: Accepted

Solution code:
'''
in
-----
6 15
6 5
5 6
6 4
6 6
3 5
7 2
'''
'''
out
-----
17
'''
N, M = map(int, input().split())
dp = [[0]*(M+1) for _ in range(N+1)]

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

'''
for i in range(0,N+1):
    for j in range(1, M+1):
        print(dp[i][j])
    print('')
'''

print(max(dp[-1]))

Submission status: Accepted

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

for i in range(1, N+1):
    W,V = map(int,input().split())
    for j in range(W):
        dp[i][j] = dp[i-1][j]
    for j in range(M-W+1):
        dp[i][j+W] = max(dp[i-1][j+W],dp[i-1][j]+V)

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def getval():
    n,w = map(int,input().split())
    p = [list(map(int,input().split())) for i in range(n)]
    return n,w,p 

def main(n,w,p):
    #DP[n][w] 
    dp = [[0 for i in range(w+1)]]
    for i in range(n):
        item = p[i]
        temp = []
        for j in range(w+1):
            cur = dp[i][j]
            if j>=item[0]:
                cur = max(cur,dp[i][j-item[0]]+item[1])
            temp.append(cur)
        dp.append(temp)
    print(dp[n][w])
                
if __name__=="__main__":
    n,w,p = getval()
    main(n,w,p)

Submission status: Accepted

Solution code:
def main():
    n, w = map(int, input().split())
    wv = [[0, 0] for _ in range(n + 1)]
    for i in range(1, n + 1):
        wv[i] = list(map(int, input().split()))
    # 1からi番目までの品物から総重量がj以下になるように選んだ時の価値の総和の最大値
    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

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

for i in range(n):
    temp_w,temp_v=map(int,input().split())
    w.append(temp_w)
    v.append(temp_v)
    

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

Submission status: Accepted

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

def main():
    n, w = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(n)]

    dp = [0] * (w + 1)
    for weight, value in wv:
        for i in range(w - weight + 1)[::-1]:
            if dp[i + weight] < dp[i] + value:
                dp[i + weight] = dp[i] + value

    print(dp[w])

main()

Submission status: Accepted

Solution code:
from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

mod=1000000007
INF=float('inf')

def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1]  + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
    

x=[]
y=[]
n,w=mp()
for i in range(n):
    a,b=mp()
    x.append(a)
    y.append(b)

print(knapSack(w,x,y,n))

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

INF = 10**18
dp = [[-INF]*(W+1) for _ in range(n+1)]
dp[0][0] = 0

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

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




n, w = li()
l = []
for i in range(n):l.append(li())

l.sort()

knapsack = [0] * (w + 1)
for i in l:
    for j in range(w - i[0], -1, -1):
        if not j or knapsack[j]:
            knapsack[j + i[0]] = max(knapsack[j + i[0]], knapsack[j] + i[1])

print(max(knapsack))

Submission status: Accepted

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

dp = [[0]*(W+1) for i in range(n+1)]
#i品目までの中から重さwを超えないように選んだときの価値の総和の最大値
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-1][j])
print(max(dp[n]))

Submission status: Accepted

Solution code:
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
        ans = 1
        for i in range(1, x+1): ans = (ans * i) % mod
        return ans
def arr2D(n, m, default=0):
        lst = []
        for i in range(n): temp = [default] * m; lst.append(temp)
        return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(n, W, weight, value):
    dp = arr2D(n+1, W+1)

    for i in range(1, n+1):
        for j in range(1, W+1):
            # print(i, j)
            val = max(dp[i][j-1], dp[i-1][j])
            if j >= weight[i-1]:
                dp[i][j] = max(val, dp[i-1][j-weight[i-1]] + value[i-1])
            else: dp[i][j] = val
    return dp[n][W]

n, W = list(map(int, input().split()))
weight = []
value = []
for i in range(n):
        a, b = list(map(int, input().split()))
        weight.append(a)
        value.append(b)
print(solve(n, W, weight, value))

Submission status: Accepted

Solution code:
def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]

# 全探索？：全探索は2**NでN=100では間に合わない
# 貪欲法？：貪欲法で常に最もコスパの高い物を入れても、次の一手でめっちゃコスパ悪くなる可能性あるのでダメ
# DP！：同じ重さで複数種類の価値のパターンが出てきた場合、最大価値のパターン以外は切り捨てて良い。

# dp[i][w]: i番目の選択で重さwだった時の最大価値

dp = [[0] * (W+1) for _ in range(N)]
sw, sv = L[0][0], L[0][1]
dp[0][0] = 0
dp[0][sw] = sv
for i in range(1, N):
    cw, cv = L[i][0], L[i][1]
    for w in range(W):
        # 取らない場合
        dp[i][w] = max(dp[i][w], dp[i-1][w])
        # 取る場合
        if w + cw > W:
            continue
        dp[i][w + cw] = max(dp[i][w + cw], dp[i-1][w] + cv)

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

Submission status: Accepted

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

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

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

print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n, W = map(int, input().split())

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

dp = np.zeros((n+1, W+1))

for i in range(n):
    dp[i+1, :w[i]] = dp[i, :w[i]]
    dp[i+1, w[i]:] = np.maximum(dp[i, w[i]:], dp[i, :W-w[i]+1]+v[i])

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

Submission status: Accepted

Solution code:
import numpy as np
[N,W],*h = [list(map(int,i.split())) for i in open(0)]

dp = np.zeros(W+1, dtype=int)

for i in range(N):
    w = h[i][0]
    v = h[i][1]
    dp[w:] = np.maximum(dp[:-w]+v,dp[w:])
print(dp[-1])

Submission status: Accepted

Solution code:
def getval():
    n,w = map(int,input().split())
    p = [list(map(int,input().split())) for i in range(n)]
    return n,w,p 

def main(n,w,p):
    #DP[n][w] 
    dp = [[0 for i in range(w+1)]]
    for i in range(n):
        item = p[i]
        temp = []
        for j in range(w+1):
            cur = dp[i][j]
            if j>=item[0]:
                cur = max(cur,dp[i][j-item[0]]+item[1])
            temp.append(cur)
        dp.append(temp)
    print(dp[n][w])
                
if __name__=="__main__":
    n,w,p = getval()
    main(n,w,p)