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:
n,w_max=map(int,input().split())
W,V=[],[]
for i in range(n):
  w,v=map(int,input().split())
  W.append(w)
  V.append(v)
w_tot=sum(W)
DP=[[-float("inf") for i in range(w_tot+1)] for j in range(n)]
for i in range(n):
  DP[i][0]=0
DP[0][W[0]]=V[0]
for i in range(1,n):
  for j in range(w_tot+1):
    if j>=W[i]:
      DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+V[i])
    else:
      DP[i][j]=DP[i-1][j]
print(max(DP[n-1][i] for i in range(w_max+1)))

Submission status: Time Limit Exceeded

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

ans = 0
dp = [[0] * (W + 1) for _ in range(2)]
for i, wv in enumerate(wvList):
    for j in range(1, W + 1):
        numi = 0
        if i % 2 == 0:
            numi = 1
        if j - wv[0] >= 0:
            dp[numi][j] = max(dp[numi-1][j-wv[0]] + wv[1], dp[numi-1][j])
        else:
            dp[numi][j] = dp[numi-1][j]
        ans = max(dp[numi][j], ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np


def dp_solve(dp, lim, n):
    for i in range(n):
        w, v = map(int, input().split())
        for j in range(lim+1):
            if w <= j:
                dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)
            else:
                dp[i+1][j] = dp[i][j]

    return dp[n][lim]


if __name__ == "__main__":
    n, lim = map(int, stdin.readline().split())
    items = []

    dp = np.zeros((n+1, lim+1), dtype='uint64')
    print(dp_solve(dp, lim, n))

Submission status: Time Limit Exceeded

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

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

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

print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

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

# 重さの総和の値を固定して、その値の最大値を求める組み合わせを
# dp[i][sum_wN]とする
dp = [[0 for _ in range(W+1)] for _ in range(N)]

# i番目についてのやつ
ans = 0
for i in range(N):
    for j in range(W+1):
        # あるWについて
        # i番目をknapsacに加える場合
        if j - ws[i] >= 0:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-ws[i]] + vs[i])
        else:
            dp[i][j] = max(dp[i][j],dp[i-1][j])

print(max(dp[-1]))

Submission status: Time Limit Exceeded

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


from collections import defaultdict
dp = defaultdict(int)
dp[0]=0

for wv in wvList:
    w,v = wv
    tp = defaultdict(int,{ i[0]+w : i[1]+v  for i in dp.items() if i[0]+w<=W})
    for i in set(list(dp.keys())+list(tp.keys())):
        dp[i] = max(dp[i],tp[i])

print(max(dp.values()))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

for i in range(N):
  a,b = list(map(int,input().split()))
  w.append(a)
  v.append(b)
  
# dp[i][w] = 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[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])  # max(iの品を使わない時, iの品を使う時)

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,W = IL()
w = [0]
v = [0]

for i in range(N):
  a,b = IL()
  w.append(a)
  v.append(b)
  
# dp[i][w] = 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[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])  # max(iの品を使わない時, iの品を使う時)

print(dp[N][W])

Submission status: Time Limit Exceeded

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

dp = [[0] * (W + 1) for _ in range(N)]
for i, wv in enumerate(wvList):
    for j in range(1, W + 1):
        if j - wv[0] >= 0:
            dp[i][j] = max(dp[i-1][j-wv[0]] + wv[1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

ans = 0
for numList in dp:
    num = max(numList)
    ans = max(ans, num)

print(ans)

Submission status: Time Limit Exceeded

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

dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):  #i番目の荷物チェック
    w,v=w_and_v[i]
    for j in range(1,W+1):  #残りjまで荷物を持てる
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
        
print(dp[N][W])

Submission status: Time Limit Exceeded

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

WV = [map(int,input().split()) for _ in range(N) ]


costs = [(0,0)]

for w, v in WV:
    new_costs = copy.deepcopy(costs)
    for cw, cv in costs:
        if cw + w > W:
            continue
        new_costs.append((cw + w, cv + v))
    costs = new_costs



print( max(costs,key=lambda item:item[1])[1])

Submission status: Time Limit Exceeded

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

weight = []
value = []

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

dp = []

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


# max value = dp[何個まで見たか][現在の重さ]
for i in range(N):
    for j in range(W+1):
        if (j+weight[i]) <= W:
            dp[i+1][j+weight[i]] = max(dp[i][j+weight[i]], dp[i][j] + value[i])

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

weight = []
value = []

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


# print('weight')
# print(weight)
# print('value')
# print(value)


def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)


# ans = dfs(0, 0, 0)

dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    
# print(dp)
# print(weight)
# print(value)
# max value = dp[何個まで見たか][現在の重さ]
for i in range(N):
    for j in range(W+1):
        # if j+weight[i] <= W:
        #     dp[i+1][j+weight[i]] = max(dp[i][j+weight[i]], dp[i][j]+value[i])
        # else:
        #     dp[i+1][j] = dp[i][j]
        # if 
        if j >= weight[i]:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()
    # W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

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

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()
    # W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

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

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()
    W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

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

    for sum_w in range(K + 1):
        for i in range(N):
            if sum_w - W[i] < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - W[i]] + V[i]
                )
    print(dp[-1][-1])


main()

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()
    W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

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

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

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


main()

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():

    N, K = read_ints()
    W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

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

    for sum_w in range(K + 1):
        for i, (w, v) in enumerate(zip(W, V)):
            if sum_w - W[i] > -1:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v
                )
            else:
                dp[i + 1][sum_w] = dp[i][sum_w]

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


main()

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
W, V = read_col(N, 2)


dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

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

for sum_w in range(K + 1):
    for i, (w, v) in enumerate(zip(W, V)):
        if sum_w - W[i] > -1:
            dp[i + 1][sum_w] = max(
                dp[i][sum_w],
                dp[i][sum_w - w] + v
            )
        else:
            dp[i + 1][sum_w] = dp[i][sum_w]

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

Submission status: Time Limit Exceeded

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

weight = []
value = []

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


# print('weight')
# print(weight)
# print('value')
# print(value)


def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)




ans = dfs(0, 0, 0)

print(ans)

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
W, V = read_col(N, 2)


dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
WV = (map(int, input().split()) for _ in range(N))

DP = [0] * (W+1)

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

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
WV = (map(int, input().split()) for _ in range(N))

DP = [0] * (W+1)

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

Submission status: Time Limit Exceeded

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

DP = [0] * (W+1)

for i, (w, v) in enumerate(WV):
  for j in range(W, w-1, -1):
    # toru
    dp1 = DP[j-w] + v 
    # toranai
    dp2 = DP[j]
    dp = max(dp1, dp2)
    DP[j] = dp
print(DP[W])

Submission status: Time Limit Exceeded

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

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

for i, (w, v) in enumerate(WV):
  for j in range(W+1):
    if j-w >= 0:
      # toru
      dp1 = DP[i-1][j-w] + v 
      # toranai
      dp2 = DP[i-1][j]
      dp = max(dp1, dp2)
    else:
      # toranai
      dp = DP[i-1][j]
    DP[i][j] = dp
print(max(DP[N-1]))

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 23 21:51:02 2019

@author: Yamazaki Kenichi
"""

N,W = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

ans = [[-1 for i in range(N+1)]]
ans[0][N] = 0
for i in range(1,W+1):
    tmp = -1
    maxv = ans[-1][N]
#    print('aa',maxv)
    for j in range(N):
#        print(i,j,A[j][0],maxv,ans[i -A[j][0]][j])
#        print(i,j,A[j],i -A[j][0],ans[-1])
        if i-A[j][0] >= 0 and ans[i-A[j][0]][j] == -1 and ans[i-A[j][0]][N] + A[j][1] > maxv:
            maxv = ans[i-A[j][0]][N] + A[j][1]
            tmp = j
#            print('maxv',maxv,'tmp',tmp)
    if tmp != -1:
        ans.append(ans[-A[tmp][0]][:])
        ans[i][tmp] = 1
    else:
        ans.append(ans[-1][:])
    ans[i][N] = maxv
#    print(ans[i][N])
#    print(ans[i])
print(ans[W][N])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
c,p=map(int,input().split())
dp[c]=p
 
def ans(n,w):
  for _ in range(1,n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      if dp[j]<dp[j-c]+p:
        dp[j]=dp[j-c]+p
  return max(dp)
print(ans(n,w))

Submission status: Time Limit Exceeded

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

n,w=map(int,input().split())
dp=[0]*(w+1)
c,p=map(int,input().split())
dp[c]=p

def ans(n,w):
  for _ in range(1,n):
    c,p=map(int,input().split())
    for j in range(w,c,-1):
      if dp[j-c] != 0 and dp[j]<dp[j-c]+p:
        dp[j]=dp[j-c]+p
    if dp[c] < p:
      dp[c]=p
  return max(dp)
print(ans(n,w))

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
dp=[0 for j in range(w+1)]
c,p=map(int,input().split())
dp[c]=p
for i in range(1,n):
  c,p=map(int,input().split())
  for j in range(w,c,-1):
    if dp[j-c] != 0 and dp[j]<dp[j-c]+p:
      dp[j]=dp[j-c]+p
  if dp[c] < p:
    dp[c]=p
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
dp=[{} for j in range(n+1)]
c,p=map(int,input().split())
dp[1][c]=p
for i in range(2,n+1):
  c,p=map(int,input().split())
  for j in dp[i-1].keys():
    if j+c<=w and dp[i-1][j] != 0:
      if j+c in dp[i-1]:
        dp[i][j+c]=max(dp[i-1][j+c],dp[i-1][j]+p)
      else:
        dp[i][j+c]=dp[i-1][j]+p
    if dp[i-1][j] != 0:
      dp[i][j]=dp[i-1][j]
  if c in dp[i-1]:
    dp[i][c]=max(dp[i-1][c],p)
  else:
    dp[i][c]=p
print(max([dp[n][i] for i in dp[n].keys()]))

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)]
c,p=map(int,input().split())
dp[1][c]=p
for i in range(2,n+1):
  c,p=map(int,input().split())
  for j in range(w-1,0,-1):
    if j+c<=w and dp[i-1][j] != 0:
      dp[i][j+c]=max(dp[i-1][j+c],dp[i-1][j]+p)
    if dp[i-1][j] != 0:
      dp[i][j]=dp[i-1][j]
  dp[i][c]=max(dp[i-1][c],p)
print(max([dp[n][i] for i in range(w+1)]))

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)]
c,p=map(int,input().split())
dp[1][c]=p
for i in range(2,n+1):
  c,p=map(int,input().split())
  for j in range(w):
    if dp[i-1][j] != 0:
      dp[i][j]=dp[i-1][j]
  for j in range(w):
    if j+c<=w and dp[i-1][j] != 0:
      dp[i][j+c]=max(dp[i-1][j+c],dp[i-1][j]+p)
  dp[i][c]=max(dp[i-1][c],p)
print(max([dp[n][i] for i in range(w+1)]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import reduce
import fractions
import pprint
import math
import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  # LIST INT
def LF(): return [float(x) for x in sys.stdin.readline().split()]  # LIST FLOAT
def LS(): return sys.stdin.readline().split()  # LIST STRING
def MI(): return map(int, sys.stdin.readline().split())  # MAP INT
def II(): return int(sys.stdin.readline())  # INPUT INT
def IS(): return input()  # INPUT STRING
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  # greatest common divisor
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  # least common multiple
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


N, W = MI()
dp = [[0 for i in range(100001)] for i in range(N+1)]

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

P(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros((N+1, W+1), dtype='uint64')
  
for i in range(1, N+1):
  for sum_w in range(W+1):
    if sum_w - ws[i-1] >= 0:
    	dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-ws[i-1]]+vs[i-1])
    dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(max(dp[N, :]))

Submission status: Time Limit Exceeded

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

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

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

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]
print(dp[N][W])

Submission status: Time Limit Exceeded

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

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: Time Limit Exceeded

Solution code:
import bisect
import itertools
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
flag1=1 if N<=30 else 0
flag2=1
flag3=1
for i in range(N):
    w[i],v[i]=map(int,input().split())
    if v[i]>100000:
        flag2=0
    if w[i]>100000:
        flag3=0
if flag1==1:
    A=[];B=[]
    for i in range(N):
        if i%2==0:
            A.append((v[i],w[i]))
        else:
            B.append((v[i],w[i]))
    Al=len(A);Bl=len(B)
    Xtmp=[]
    for seq in itertools.product(range(2),repeat=Al):
        tmp0=0
        tmp1=0
        for i in range(Al):
            if seq[i]==1:
                tmp0+=A[i][0]
                tmp1+=A[i][1]
        Xtmp.append((tmp0,tmp1))
    Xtmp.sort(key=lambda x:x[1])
    X=[]
    Xltmp=len(Xtmp)
    maxtmp=0
    for i,seq in enumerate(Xtmp):
        if maxtmp<=seq[0]:
            X.append(seq)
        maxtmp=max(maxtmp,seq[0])
    #print(X)
    wt=[i[1] for i in X]
    #print(wt)
    ans=0
    for seq in itertools.product(range(2),repeat=Bl):
        tmp0=0
        tmp1=0
        for i in range(Bl):
            if seq[i]==1:
                tmp0+=B[i][0]
                tmp1+=B[i][1]
        if W-tmp1<=0:
            continue
        index=bisect.bisect_right(wt,W-tmp1)-1
        tmp=X[index][0]+tmp0
        ans=max(ans,tmp)
    print(ans)
elif flag2==1:
    V=sum(v)
    INF=10**15
    dp=[[INF for j in range(V+1)] for i in range(N+1)]
    #dp[i][j]:iまで試して価値の合計がjのときの重さの最小値
    dp[0][0]=0
    for i in range(N):
        for j in range(V+1):
            if j-v[i]>=0:
                dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i],INF)
            else:
                dp[i+1][j]=min(dp[i][j],INF)
    b=[]
    for i in range(V+1):
        if dp[N][i]!=INF:
            b.append((dp[N][i],i))
    ans=0
    for (x,y) in b:
        if x<=W:
            ans=max(ans,y)
    print(ans)
elif flag3==1:
    dp=[[0 for i in range(W+1)] for i in range(N+1)]
    for j in range(W+1):
        dp[0][j]=0
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=dp[i][j]
            if j-w[i]>=0:
                if dp[i][j]<dp[i][j-w[i]]+v[i]:
                    dp[i+1][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()))
arr = []
for i in range(n):
    lista = list(map(int,input().split()))
    arr.append(lista)

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

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

print(ans)'''


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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n, w = nm()
lis = [nl() for _ in range(n)]
lis.insert(0, [0, 0])
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 - lis[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - lis[i][0]] + lis[i][1])
        else:
            dp[i][j] = dp[i - 1][j]

for i in range(w, -1, -1):
    if dp[n][i] != 0:
        print(dp[n][i])
        exit()

Submission status: Time Limit Exceeded

Solution code:


n,w = list(map(int,input().split()))
arr = []
for i in range(n):
    lista = list(map(int,input().split()))
    arr.append(lista)

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

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

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

print(ans)

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

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

print(ans)