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^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

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

1 1000000000
1000000000 10

Sample Output 2

10

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:
import numpy as np

N = W = 0
g = []
MAX_V = 100100


def get_input():
    global N, W, g
    N, W = map(int, input().split())
    g = []
    for _ in range(N):
        g.append([int(x) for x in input().split()])


def dpcalc():
    global N, W, g
    # 動的計画法のテーブルを初期化
    dp = np.full((N + 1, MAX_V + 1), 10 ** 11)
    # dp = [[10 ** 11] * (MAX_V + 1) for _ in range(N + 1)]

    # テーブルをiの小さい方から順に計算してゆく
    for i in range(1, N + 1):
        for j in range(MAX_V + 1):
            w, v = g[i - 1]
            if j - v > 0:
                dp[i][j] = min(dp[i - 1][j - v]  +  w, dp[i - 1][j])
            else:
                dp[i][j] = min(dp[i - 1][j], w)

    for i in range(MAX_V, -1, -1):
        if dp[N][i] <= W:
            return i
    return 0


get_input()
print(dpcalc())

Submission status: Time Limit Exceeded

Solution code:
N = W = 0
g = []
MAX_V = 100100


def get_input():
    global N, W, g
    N, W = map(int, input().split())
    g = []
    for _ in range(N):
        g.append([int(x) for x in input().split()])


def dpcalc():
    global N, W, g
    # 動的計画法のテーブルを初期化
    dp = [[10 ** 11] * (MAX_V + 1) for _ in range(N + 1)]

    # テーブルをiの小さい方から順に計算してゆく
    for i in range(1, N + 1):
        for j in range(MAX_V + 1):
            w, v = g[i - 1]
            if j - v > 0:
                dp[i][j] = min(dp[i - 1][j - v]  +  w, dp[i - 1][j])
            else:
                dp[i][j] = min(dp[i - 1][j], w)

    for i in range(MAX_V, -1, -1):
        if dp[N][i] <= W:
            return i
    return 0


get_input()
print(dpcalc())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
E - Knapsack 2
https://atcoder.jp/contests/dp/tasks/dp_e

"""
import sys


def solve(N, W, items):
    limit = 0
    for w, v in items:
        limit += v
    dp = [float('inf')] * (limit+1)
    dp[0] = 0
    for w, v in items:
        for i in range(limit, -1, -1):
            if dp[i] != float('inf') and dp[i]+w <= W:
                dp[i+v] = min(dp[i+v], dp[i]+w)

    ans = [i for i, d in enumerate(dp) if d != float('inf')]
    return max(ans)


def main(args):
    N, W = map(int, input().split())
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
E - Knapsack 2


"""
import sys


def solve(N, W, items):
    dp = {0: 0}
    for w, v in items:
        u = dict()
        for x, y in dp.items():
            if x+w <= W and dp.get(x+w, 0) < y+v:
                u[x+w]= y+v
        dp.update(u)
    return max([v for v in dp.values()])


def main(args):
    N, W = map(int, input().split())
    items = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, W, items)
    print(ans)


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

Submission status: Time Limit Exceeded

Solution code:
dp1=[None]*100001
dp2=[None]*100001
dp1[0]=0
dp2[0]=0
n,W=map(int,input().split())
for i in range(n):
    w,v=map(int,input().split())
    for i in range(v,100001):
        if(dp2[i-v]!=None):
            if(dp2[i]==None):
                dp1[i]=dp2[i-v]+w
            else:
                dp1[i]=min(dp2[i],dp2[i-v]+w)
    dp2=list(dp1)
for i in range(100000,-1,-1):
    if(dp2[i]!=None and dp2[i]<=W):
        print(i)
        break
# 3 8
# 3 3
# 4 5
# 5 6

Submission status: Time Limit Exceeded

Solution code:
def task(N, W, weight, value):
    V = sum(value)
    result = [[W + 1]*(V+1) for i in range(N+1)]
    result[0][0] = 0
    for i in range(1, N + 1):
        for v in range(V + 1):
            if value[i-1] > v:
                result[i][v] = result[i-1][v]
            else:
                result[i][v] = min(result[i-1][v], result[i-1][v - value[i-1]] + weight[i-1])
    for v in range(V, 0, -1):
        if result[N][v] <= W:
            return v
            
N, W = [int(x) for x in input().split()]
weight, value = [], []
for i in range(N):
    w, v = [int(x) for x in input().split()]
    weight.append(w)
    value.append(v)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
rr = lambda: sys.stdin.readline().strip()
ri = lambda: int(rr())
rs = lambda: [int(_) for _ in rr().split()]

N, W = rs()
d = [rs() for _ in range(N)]

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

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

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:

n, w = map(int, input().split())

#wvn = [ list( map(int,input().split()) ) for _ in range(n) ]

wvn = [ tuple( map(int,input().split())) for _ in range(n) ]

#print(wvn)

VMAX = 10**3 * (10**2)
# 1 <= vi <= 10**3
tab = [ [10**10] *(VMAX+1) for _ in range(n+1)]

#print(type(tab[0]))

for i in range(1, len(wvn)+1 ):
    
    wv = wvn[i-1]
    wi = wv[0]
    vi = wv[1]
    
    for j in range( VMAX + 1 ):

        t = tab[i-1][j]
        
        if j >= vi:
            t = min(t, tab[i-1][j-vi]+wi)

        else:
            t = min(t, wi)
        
        tab[i][j] = t

ans = 0
while tab[n][ans] <= w:
    #print( (tab[n][ans],ans) )
    ans += 1

#print("ANS")
print(ans)



def debug0():
    row1 = tab[1]
    
    print("DEBUG0--START")
    print([(i, row1[i]) for i in range(0,50,5)])
    print("DEBUG0--END")
#debug0()


def debug1():

    for i in range(n+1):
        t = tab[i][0]
        sss = set(tab[i])
        print(sss)
        for j in range( 1, len(tab[i]) ):
            v = tab[i][j]

            if not t == v:
                t = v
                print( (i,j,v) )
 #end


def debug3():
    t = -1

    for i in range( len(tab[n])-1 ):
        e = tab[n][i]

        if not t == e:
            t = e
            print( (i, e) )
            
#debug3()





def debug2():
    t = -1
    for vi in range(len(tab[0])):

        v = tab[n][vi]
        if not t == v:
            t = v
            print((t,vi))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def knapsack():
    n, max_w = map(int, input().split())
    dp = defaultdict(int)
    dp[0] = 0
    for _ in range(n):
        w, v = map(int, input().split())
        for item in list(dp.keys()):
            dp[item+w] = max(dp[item] + v, dp[item+w])
    max_v = 0
    for w, v in dp.items():
        if w <= max_w:
            max_v = max(v, max_v)
    print(max_v)
    

knapsack()

Submission status: Time Limit Exceeded

Solution code:
def task(N, W, weight, value, result_dict):
    if (N == 0) or (W == 0):
        result_dict[(N, W)] = 0
        return 0
    if (N, W) in result_dict:
        return result_dict[(N, W)]
    if weight[N - 1] <= W:
        a = task(N-1, W, weight, value, result_dict)
        b = task(N - 1, W - weight[N - 1], weight, value, result_dict) + value[N - 1]
        result_dict[(N, W)] = max(a, b)
    else:
        result_dict[(N, W)] = task(N-1, W, weight, value, result_dict)
    
    return result_dict[(N, W)]
  
N, W = [int(x) for x in input().split()]
weight, value = [], []
for i in range(N):
    w, v = [int(x) for x in input().split()]
    weight.append(w)
    value.append(v)

result_dict = {}
print(task(N, W, weight, value, result_dict))

Submission status: Time Limit Exceeded

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

dp = [[None for __ in range(N*max(V)+1)] for _ in range(N+1)]
dp[0] = [10**9 for _ in range(N*max(V)+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for v in range(N*max(V)+1):
        if V[i-1] >= v:
            dp[i][v] = min(dp[i-1][v], W[i-1])
        else:
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i-1]] + W[i-1])


print(max(i for i, w in enumerate(dp[-1]) if w <= M))

Submission status: Time Limit Exceeded

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

n, W = [int(i) for i in input().split()]
dp = [W + 1] * (1010 * (n + 1))

dp[0] = 0
v_max = 0
for i in range(n):
    w, v = [int(i) for i in input().split()]
    v_max += v
    for j in range(v_max, v - 1, -1):
        dp[j] = min(dp[j - v] + w, dp[j])

ans = 0
for i in range(v_max, -1, -1):
    if dp[i] <= W:
        ans = max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

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

n, W = [int(i) for i in input().split()]
dp = [W + 1] * (1010 * (n + 1))

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

ans = 0
for i in range(v_max, -1, -1):
    if dp[i] <= W:
        ans = max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(v_max, -1, -1):
    if dp[i] <= W:
        ans = max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

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

n, W = map(int, input().split())
dp = [[float("inf")] * (1010 * (n + 1)) for _ in range(n + 1)]

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

ans = 0
for i in range(n + 1):
    for j in range(v_max + 1):
        if dp[i][j] <= W:
            ans = max(ans, j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, W = map(int, input().split())
dp = [[float("inf")] * (1010 * (n + 1)) for _ in range(n + 1)]

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

ans = 0
for i in range(n + 1):
    for j in range(v_max + 1):
        if dp[i][j] <= W:
            ans = max(ans, j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def main():
    num, weigh = map(int, input().split())
    dp = [defaultdict(int) for i in range(num + 1)]
    dp[0][0] = 0

    for i in range(1, num + 1):
        data = list(map(int, input().split()))
        for pre_value in dp[i - 1].keys():
            dp[i][pre_value] = max(dp[i - 1][pre_value], dp[i][pre_value])
            if pre_value + data[0] <= weigh:
                dp[i][pre_value + data[0]] = max(dp[i - 1][pre_value] + data[1], dp[i][pre_value + data[0]])

    print(max(list(dp[-1].values())))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
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)
DP=[[float("inf") for i in range(10**5+1)] for j in range(n+1)]
DP[0][0]=1
for i in range(1,n+1):
  for j in range(i*(10**3)+1):
    if j>V[i-1]:
      DP[i][j]=min(DP[i-1][j],DP[i-1][j-V[i-1]]+W[i-1])
    else:
      DP[i][j]=min(DP[i-1][j],W[i-1])
ans=bisect.bisect_right(DP[n],w_max)-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
import functools
import sys
input=sys.stdin.readline
@functools.lru_cache(maxsize=None)
def Knapsack(N,W):
    for i in range(N):
        w,v=map(int,input().split())
        for k,b in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],b+v)
    return max(d.values())
N,W=map(int,input().split())   #pypyで実行！
d=defaultdict(int)
d[0]=0
print(Knapsack(N,W))

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
from collections import*
d=defaultdict(int)
d[0]=0
for i in range(N):
    w,v=map(int,input().split())
    for k,b in d.copy().items():
        if k+w<=W:
            d[k+w]=max(d[k+w],b+v)
print(max(d.values()))

Submission status: Time Limit Exceeded

Solution code:
inf = 2000000000

n, w = map(int, input().split())
ws, vs = [], []
for _ in range(n):
    ww, vv = map(int, input().split())
    ws.append(ww)
    vs.append(vv)

sum_v = sum(vs)
dp = [[inf for _ in range(sum_v+1)] for _ in range(n)]
# dp[i][j]: i番目までで価値jを達成する最小の重さ

dp[0][0] = 0
dp[0][vs[0]] = ws[0]

for i in range(1, n):
    for j in range(0, sum_v+1):
        if j - vs[i] >= 0:
            dp[i][j] = min(dp[i-1][j], ws[i] + dp[i-1][j-vs[i]])
        else:
            dp[i][j] = dp[i-1][j]

max_v = 0
for j in range(0, sum_v+1):
    if dp[n-1][j] <= w:
        max_v = j

print(max_v)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
input = stdin.readline
N, W = list(map(int, input().split()))
wvList = [list(map(int, input().split())) for _ in range(N)]
v_dict = defaultdict(int)
v_dict[0]=0
for wv in wvList:
    w,v = wv
    copy_dict = v_dict.copy()
    for v_key in copy_dict:
        add_val_a = copy_dict[v_key]+w if copy_dict[v_key] + w <=W else float("inf") 
        #print((v_key+v) in copy_dict.keys())
        add_val_b = copy_dict[v_key+v] if (v_key+v) in copy_dict.keys() else float("inf")
        if add_val_a != float("inf") or add_val_b != float("inf") :
            #print(add_val_a,add_val_b)
            v_dict[v_key+v] = min(add_val_a,add_val_b)
    #print(v_dict)
print(max(v_dict.keys()))

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

import numpy as np
# 流れ
# dpテーブルのサイズを決める
#     (N,max(V)*N)
# dpテーブルの初期化
# dpテーブルの更新
#     いままでと同じ
#     sum_v以上を達成すhるように選んだときのsum_wの最小値を保持する
# 答えの抽出
# dpでW以下かつ最大価値が最大(sum_v)なものが答え


dp = np.full((N+1, np.max(V) * N+1), float('inf'))
# dp[:, 0] = 0
dp[0][0] = 0

from itertools import product

for i, sum_v in product(range(N), range(np.max(V) * N+1)):
    if sum_v - V[i] < 0:
        dp[i + 1, sum_v] = dp[i, sum_v]
    else:
        # print(i, sum_v)
        dp[i + 1, sum_v] = min(
            dp[i, sum_v],
            dp[i, sum_v-V[i]]+W[i]
        )

# print(dp)
print(np.where((dp <= K).sum(axis=0) != 0)[0].max())
# print(max(np.where((dp < K).sum(axis=0) != 0)))
# print(max(np.where((dp < K).sum(axis=0) != 0)))

Submission status: Time Limit Exceeded

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

for i in range(1, num + 1):
    weight, value = list(map(int, input().split()))
    for w in range(capacity + 1):
        if w - weight >= 0:
            dp[i][w] = max( dp[i-1][w - weight] + value,  dp[i-1][w] )
        else:
            dp[i][w] = dp[i-1][w]
print(dp[num][capacity])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())

dp = np.ones([2, N * 10 ** 3 + 1], dtype=int) * float("inf")
dp[0][0], dp[1][0] = 0, 0
for i in range(N):
    index = i % 2
    w, v = map(int, input().split())
    for j in range(1, len(dp[0])):
        if j <= v:
            dp[index][j] = min(w, dp[index-1][j])
        else:
            dp[index][j] = min(w + dp[index-1][j-v], dp[index-1][j])

dp = np.minimum(dp[0], dp[1])
ans = 0
for i, w in enumerate(dp):
    if w <= W:
        ans = max(ans, i)
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**10
vsum = 1000*N
dp = [INF for i in range(vsum+1)]
dp[0] = 0


for _ in range(N):
    w,v = map(int,input().split())
    dp1 = [d for d in dp]
    for i,d in enumerate(dp):
        if d == INF:
            continue
        else:
            if i + v <= vsum:
                dp[i+v] = min(dp1[i+v], dp1[i]+w)
    
ans = 0
for i,d in enumerate(dp):
    if d <= W:
        ans = i

print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**10
vsum = 10**5
dp = [INF for i in range(vsum+1)]
dp[0] = 0

for _ in range(N):
    w,v = map(int,input().split())
    dp1 = [d for d in dp]
    for i,d in enumerate(dp):
        if d == INF:
            continue
        else:
            if i + v <= vsum:
                dp1[i+v] = min(dp[i+v], dp[i]+w)
    dp = [d1 for d1 in dp1]

ans = 0
for i,d in enumerate(dp):
    if d <= W:
        ans = i

print(ans)

Submission status: Time Limit Exceeded

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

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


#dp[w] = max cost
costs = [-1 for _ in range(W + 1)]
costs[0] = 0

for w, v in WV:
    for index in reversed(range(W + 1)):
        if costs[index] == -1:
            continue
        if index + w > W:
            continue
        costs[index + w] = max(costs[index] + v, costs[index + w])


print(max(costs))

Submission status: Time Limit Exceeded

Solution code:
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      if i + w <= W:
        if i+w in DP:
          DP[i+w] = max(DP[i] + v, DP[i+w])
        else:
          DP[i+w] = DP[i] + v
  return max(DP.values())
  
print(dp_fn())

Submission status: Time Limit Exceeded

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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(list(DP.keys()), reverse=True)
    for i in keys:
      if i + w <= W:
        if i+w in DP:
          DP[i+w] = max(DP[i] + v, DP[i+w])
        else:
          DP[i+w] = DP[i] + v
  return max(DP.values())
  
print(dp_fn())

Submission status: Time Limit Exceeded

Solution code:
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(list(DP.keys()), reverse=True)
    for i in keys:
      if i + w <= W:
        if i+w in DP:
          DP[i+w] = max(DP[i] + v, DP[i+w])
        else:
          DP[i+w] = DP[i] + v
  return max(DP.values())
  
print(dp_fn())

Submission status: Time Limit Exceeded

Solution code:
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  from collections import defaultdict
  
  DP = defaultdict(int)
  DP[0] = 0
  
  for w, v in WV:
    for i in reversed(tuple(DP.keys())):
      if i + w <= W:
        DP[i+w] = max(DP[i] + v, DP[i+w])
  return max(DP.values())
  
print(dp_fn())

Submission status: Time Limit Exceeded

Solution code:
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    CP = {}
    for i in DP.keys():
      if i + w <= W:
        CP[i+w] = max(DP[i] + v, DP[i])
    for i in CP.keys():
      DP[i] = CP[i]
  return max(DP.values())
  
print(dp_fn())

Submission status: Time Limit Exceeded

Solution code:
def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    for i in reversed(list(DP.keys())):
      if i + w <= W:
        DP[i+w] = max(DP[i] + v, DP[i])
  return max(DP.values())
  
print(dp_fn())

Submission status: Time Limit Exceeded

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

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 = [[float('inf') for _ in range(sum(v) + 1)] for _ in range(N + 1)]
dp[0][0] = 0
# dp[何番目までの品物で][この価値以下を達成する]:=最小の重量

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

for j in sorted(range(sum(v) + 1), reverse=True):
    t = dp[N][j]
    if t <= W:
        print(j)
        break

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:
from collections import defaultdict as d
s=d(int)
s[0]=0
n,w=map(int,input().split())
for i in range(n):
    q,v=map(int,input().split())
    c=s.copy()
    for p,r in c.items():
        if p+q<=w:
            s[p+q]=max(s[p+q],r+v)
print(max(s.values()))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
d = []
S = 0
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))
    S += v
INF = float('inf')
dp = [[INF] * (S + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(S + 1):
        w, v = d[i - 1]
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if j + v <= S:
            dp[i][j + v] = min(dp[i][j + v], dp[i - 1][j] + w)

for i in range(S, -1, -1):
    if dp[N][i] <= W:
        print(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:

n, ww = map(int, input().split())

wv = [list(map(int, input().split())) for i in range(n)]

dp = {0:0}
for w, v in wv:
    dp_next = dp.copy()
    for key in dp:
        dp_next[key+v] = min(dp[key]+ w, dp.get(key+v, float("inf")))
    dp = dp_next
for key in sorted(dp.keys(), reverse=True):
    if dp[key] <= ww:
        print(key)
        exit()

Submission status: Time Limit Exceeded

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

def main():
    #raw = ["3 8",
    #       "3 30",
    #       "4 50",
    #       "5 60"]
    #raw = ["5 5",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000",
    #       "1 1000000000"]
    #raw = ["1 1000000000",
    #       "1000000000 10"]
    #raw = ["6 15",
    #       "6 5",
    #       "5 6",
    #       "6 4",
    #       "6 6",
    #       "3 5",
    #       "7 2"]
    #N, W = map(int, raw[0].split())
    #data = [list(map(int, x.split())) for x in raw[1:]]
    import sys
    N, W = map(int, sys.stdin.readline().split())
    data = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    #dp = [0] * (W + 1)
    dp = {}
    def getdp(i):
        if i in dp:
            return dp[i]
        return 0
    mymax = max
    for i in range(N):
        weight, value = data[i]
        for j in range(W, weight-1, -1):
            dp[j] = mymax(getdp(j), getdp(j - weight) + value)
    print(getdp(W))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# sum_vの取りうる上限値
MAX_V = (10**3+1) * N

# 最小値を求めるので無限大の値
f_inf = float('inf')

def chmin(a, b):
    if a <= b:
        return a
    else:
        return b

def knapsack(n, w):
    # dpの初期化　dp[i][sum_v]は重さの総和の最小値
    dp = [[f_inf for i in range(MAX_V)] for j in range(N+1)]
    # 初期条件
    dp[0][0] = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        w, v = map(int, input().split())
        for sum_v in range(MAX_V):
            # i番目の品物を選ぶ場合
            if (sum_v -v >= 0):
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v - v] + w)
            # i番目の品物を選ばない場合
            dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v])
    #dp[N][sum_v]の値が、W以下であるsum_vの値の最大値
    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)

knapsack(N, W)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, W = map(int, input().split())
    weight = [0 for i in range(N)]
    value = [0 for i in range(N)]
    for i in range(N):
        weight[i], value[i] = map(int, input().split())
    MAX_VALUE = sum(value)
    dp = [float('inf') for i in range(MAX_VALUE + 1)]
    dp[0] = 0

    for i in range(N):
        wi = weight[i]
        vi = value[i]
        for v in range(MAX_VALUE, -1, -1):
            _v = v + vi
            _w = dp[v] + wi
            if _v > MAX_VALUE: continue
            if _w > W: continue
            if dp[_v] <= _w: continue
            dp[_v] = _w
    for i in range(MAX_VALUE, -1, -1):
      if dp[i] <= W: return i
    return 0

print(solve())

Submission status: Time Limit Exceeded

Solution code:
n, w_limit = map(int, input().split())
dp = [[float('inf') for _ in range(1000*n+1)] for __ in range(n+1)]
dp[0][0] = 0

for i in range(n):
  w, v = map(int, input().split())
  for v_sum in range(1000*n+1):
    if v_sum >= v:
      dp[i+1][v_sum] = dp[i][v_sum - v] + w
    dp[i+1][v_sum] = min(dp[i+1][v_sum], dp[i][v_sum])

for i in range(1000*n+1)[::-1]:
  if dp[n][i] <= w_limit:
    ans = i
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,s=map(int,input().split())
k=defaultdict(int)
k[0]=0
d=0
for i in range(n):
    w,v=map(int,input().split())
    c=list(k)
    for i in range(len(c)-1,-1,-1):
        if c[i]+w<=s:
            if k[c[i]+w]!=0:
                k[c[i]+w]=max(k[c[i]+w],k[c[i]]+v)
            else:
                k[c[i]+w]=k[c[i]]+v
            d=max(d,k[c[i]+w])
print(d)

Submission status: Time Limit Exceeded

Solution code:
n,w=list(map(int,input().split()))
k=[]
for i in range(n):
    k.append(list(map(int,input().split())))
vn=100100
dp=[[0]+[float("inf") for i in range(vn)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,k[i-1][1]+1):
        dp[i][j]=min(dp[i-1][j],k[i-1][0])
    for j in range(k[i-1][1]+1,vn):
        dp[i][j]=min(dp[i-1][j],k[i-1][0]+dp[i-1][j-k[i-1][1]])
for i in range(vn,-1,-1):
    if dp[n][i]<=w:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
n,w=list(map(int,input().split()))
k=[]
for i in range(n):
    k.append(list(map(int,input().split())))
vn=100100
dp=[[0]+[float("inf") for i in range(vn)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,vn):
        if j<=k[i-1][1]:
            dp[i][j]=min(dp[i-1][j],k[i-1][0])
        else:
            dp[i][j]=min(dp[i-1][j],k[i-1][0]+dp[i-1][j-k[i-1][1]])
for i in range(vn,-1,-1):
    if dp[n][i]<=w:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
n,w=list(map(int,input().split()))
k=[]
for i in range(n):
    k.append(list(map(int,input().split())))
vn=111100
dp=[[0]+[float("inf") for i in range(vn)] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,vn+1):
        if j<=k[i-1][1]:
            dp[i][j]=min(dp[i-1][j],k[i-1][0])
        else:
            dp[i][j]=min(dp[i-1][j],k[i-1][0]+dp[i-1][j-k[i-1][1]])
for i in range(vn,-1,-1):
    if dp[n][i]<=w:
        print(i)
        break