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:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, W = map(int, input().split())
    V = N * 10**3
    INF = 10**12
    dp = [INF] * (V+1)# dp[i]: 価値の総和をiにするための重さの最小値
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(V,-1,-1):
            if j-v >= 0:
                dp[j] = min(dp[j],dp[j-v]+w)
    # print(dp)
    ans = -1
    for i in range(V+1):
        if dp[i] <= W:
            ans = i
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if Current_Weight <= W:
        Last_Search_List = list(dp.keys())
        Current_Search_List = list(set(map(lambda x:x+Current_Weight if 
                                           x+Current_Weight <= W else 0, Last_Search_List)))
        Same_Search_List = list(set(Last_Search_List) & set(Current_Search_List))
        Diff_Search_List = list(set(Current_Search_List) - set(Last_Search_List))
        for j in Diff_Search_List:
            Last_Search_Weight = j - Current_Weight
            dp[j] = dp[Last_Search_Weight] + Current_Value
        for j in Same_Search_List:
            if j ==0:
                continue
            Last_Search_Weight = j - Current_Weight
            dp[j] = max(dp[j],dp[Last_Search_Weight] + Current_Value)

print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if Current_Weight <= W:
        Current_Search_List = list(set(map(lambda x:x+Current_Weight if 
                                           x+Current_Weight <= W else 0, dp.keys())))
        for j in Current_Search_List:
            if j == 0:
                continue
            Last_Search_Weight = j - Current_Weight
            if j in dp:
                dp[j] = max(dp[j],dp[Last_Search_Weight] + Current_Value)
            else: 
                dp[j] = dp[Last_Search_Weight] + Current_Value

print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split(" "))
INF =  1e11
v = [INF]*100010
v[0] = 0
for i in range(N):
  weight,value = map(int,input().split(" "))
  for j in range(100001,0,-1):
    if j < value:
      break
    v[j] = min(v[j],v[j-value]+weight)

for i in range(100001,0,-1):
  if v[i] <= W:
    print(i)
    break

Submission status: Time Limit Exceeded

Solution code:
### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if (i == 0) & (Current_Weight <= W) :
        dp[Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = list(dp.keys())
        for j in Last_Search_List:
            Current_Search_Weight = j + Current_Weight
            if Current_Search_Weight in dp:
                dp[Current_Search_Weight] = max(dp[Current_Search_Weight],
                                                dp[j] + Current_Value)
            elif Current_Search_Weight <= W :
                dp[Current_Search_Weight] = dp[j] + Current_Value

print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]

dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if (i == 0) & (Current_Weight <= W) :
        dp[Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = list(dp.keys())
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        for j in range(len(Current_Search_List)):
            Last_Search_Weight = Last_Search_List[j]
            Current_Search_Weight = Current_Search_List[j]
            if Current_Search_Weight in dp:
                dp[Current_Search_Weight] = max(dp[Current_Search_Weight],
                                                dp[Last_Search_Weight] + Current_Value)
            elif Current_Search_Weight <= W :
                dp[Current_Search_Weight] = dp[Last_Search_Weight] + Current_Value

print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))

dp={0:0}
for i in range(N):
    Current_Weight = Goods_List[i][0]
    Current_Value  = Goods_List[i][1]
    if (i == 0) & (Current_Weight <= W) :
        dp[Current_Weight] = Current_Value
    elif i > 0:
        Last_Search_List = list(dp.keys())
        Current_Search_List = list(map(lambda x:x+Current_Weight,Last_Search_List))
        for j in range(len(Current_Search_List)):
            Last_Search_Weight = Last_Search_List[j]
            Current_Search_Weight = Current_Search_List[j]
            if Current_Search_Weight in dp:
                dp[Current_Search_Weight] = max(dp[Current_Search_Weight],
                                                dp[Last_Search_Weight] + Current_Value)
            elif Current_Search_Weight <= W :
                dp[Current_Search_Weight] = dp[Last_Search_Weight] + Current_Value

print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
N, W = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(N)]  # [重さ、価値]
# sum_vの取りうる上限値
# MAX_V = (10**3 + 1) * N
MAX_V = 0
for line in array:
    MAX_V += line[1]
MAX_V += 1
# 最小値を求めるので無限大の値
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] * 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 - array[i][1] >= 0:
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v],
                                         dp[i][sum_v - array[i][1]] + array[i][0])
            # 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:
import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
N, W = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(N)]  # [重さ、価値]
# 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] * 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 - array[i][1] >= 0:
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v],
                                         dp[i][sum_v - array[i][1]] + array[i][0])
            # 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:

N, W = [int(x) for x in input().split()]
items = [tuple(map(int, input().split())) for _ in range(N)]

#bottomup
memo = [10**10]*(10**5+1)
memo[0] = 0

for weight, value in items:
    for i in reversed(range(len(memo)-value)):
            memo[i+value] = min(memo[i+value],memo[i] + weight)

ans = 0
for i in range(len(memo)):
    if memo[i] != 10**10 and memo[i] <= W:
        ans = i

print(ans)

Submission status: Time Limit Exceeded

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

def main():
    n, w = map(int,input().split())
    wei = []
    val = []
    for i in range(n):
        a, b = map(int,input().split())
        wei.append(a)
        val.append(b)

    max_v = 10**5 + 10
    dp = [[float('inf') for i in range(max_v)] for j in range(100+10)]

    dp[0][0] = 0

    for i in range(n):
        for sum_v in range(max_v):

            # i 番目の品物を選ぶ場合
            if sum_v - val[i] >= 0:
                dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v - val[i]] + wei[i])
            else:
                # i 番目の品物を選ばない場合
                dp[i+1][sum_v] = dp[i][sum_v]

    res = 0
    for i in range(100+10):
        for sum_v in range(max_v):
            if dp[i][sum_v] <= w and res < sum_v:
                res = sum_v

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

INF = float("inf")
dp = [0] + [INF] * 10**5

for _ in range(N):
  w, v = map(int, input().split())
  for j in range(10**5, v-1, -1):
    dp[j] = min(dp[j], dp[j-v] + w)

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

print(ans)

Submission status: Time Limit Exceeded

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

INF = float("inf")
dp = [0] + [INF] * 10**5

for _ in range(N):
  w, v = map(int, input().split())
  for j in range(10**5, v-1, -1):
    dp[j] = min(dp[j], dp[j-v] + w)

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

print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**11 + 1
dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][max(0, j-v)] + w)

ans = 0
    
for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)

Submission status: Time Limit Exceeded

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

w, v = [0] * N, [0] * N

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

dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for n in range(N + 1):
    for weight in range(W + 1):
        if weight == 0 or n == 0:
            dp[n][weight] = 0
        elif w[n-1] > weight:
            dp[n][weight] = dp[n-1][weight]
        else:
            dp[n][weight] = max(dp[n-1][weight], v[n-1] + dp[n-1][weight-w[n-1]])

print(dp[N][W])

Submission status: Time Limit Exceeded

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

w, v = [0] * N, [0] * N

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


def helper(weight, n, wt, val, memo):
    if n == 0 or w == 0:
        return 0
    if wt[n-1] > weight:
        return helper(weight, n-1, wt, val, memo)
    if (weight, n) in memo:
        return memo[(weight, n)]
    res = max(
        helper(weight, n-1, wt, v, memo),
        val[n-1] + helper(weight-wt[n-1], n-1, wt, val, memo)
    )
    memo[(weight, n)] = res
    return res


print(helper(W, N, w, v, {}))

Submission status: Time Limit Exceeded

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

w, v = [0] * N, [0] * N

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


def helper(weight, n, wt, val, memo):
    if n == 0 or w == 0:
        return 0
    if (weight, n) in memo:
        return memo[(weight, n)]
    if wt[n-1] > weight:
        return helper(weight, n-1, wt, val, memo)
    res = max(
        helper(weight, n-1, wt, v, memo),
        val[n-1] + helper(weight-wt[n-1], n-1, wt, val, memo)
    )
    memo[(weight, n)] = res
    return res


print(helper(W, N, w, v, {}))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

num = list(map(int, input().split()))
n, tw = num[0], num[1]

w = deque([0])
v = deque([0])

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

if sum(w) < tw:
    tw = sum(w)

dp1 = [0 for i in range(tw+1)]
dp2 = [0 for i in range(tw+1)]

w.popleft()
v.popleft()

while w:
    curr_weight = w.popleft()
    curr_val = v.popleft()
    for i in range(1, tw+1):
        if i < curr_weight:
            dp2[i] = dp1[i]
        else:
            dp2[i] = max(dp1[i], curr_val + dp1[i - curr_weight])
    dp1 = dp2[:]
    dp2 = [0 for i in range(tw+1)]
print(dp1[-1])

Submission status: Time Limit Exceeded

Solution code:
num = list(map(int, input().split()))
n, tw = num[0], num[1]

w = [0]
v = [0]

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

if sum(w) < tw:
    tw = sum(w)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# from sys import stdin, stdout
def helper(weights,values,n,capacity,memo):
    if(capacity==0 or n==0):
        return 0
    if((n,capacity) in memo):
        return memo[(n,capacity)]
    if(weights[n-1]<=capacity):
        memo[(n,capacity)]=max(values[n-1]+helper(weights,values,n-1,capacity- weights[n-1],memo),helper(weights,values,n-1,capacity,memo))
        return memo[(n,capacity)]
    memo[(n,capacity)]=helper(weights,values,n-1,capacity,memo)
    return memo[(n,capacity)]
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())

memo={}
print(helper(weights,values,n,capacity,memo))

Submission status: Time Limit Exceeded

Solution code:
def solve(w,v,tv,W):
    dp=[float('inf')]*(tv+1)
    dp[0]=0
    for i in range(len(w)):
        for j in range(tv-v[i],-1,-1):
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])
    maxx=0
    for i in range(tv+1):
        if dp[i]<=W:
            maxx=max(maxx,i)
    return maxx
if __name__=='__main__':
    n,W=map(int,input().split())
    w=[]
    v=[]
    for i in range(n):
        p,q=map(int,input().split())
        w.append(p)
        v.append(q)
    print(solve(w,v,sum(v),W))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def solve(a,w,dp):
    if not a or w==0: return 0
    if (str(a),w) in dp: return dp[(str(a),w)]
    maxx=0
    for i in range(len(a)):
        if a[i][0]<=w:
            maxx=max(maxx,a[i][1]+solve(a[:i]+a[i+1:],w-a[i][0],dp))
    dp[(str(a),w)]=maxx
    return maxx
if __name__=='__main__':
    n,w=map(int,input().split())
    a=[]
    sw=0
    for i in range(n):
        p,q=map(int,input().split())
        if p>w: continue
        a.append((p,q))
        sw+=a[-1][0]
    a.sort(key=lambda x: x[0])
    print(solve(a,w,{}))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def solve(a,w,dp):
    if not a or w==0: return 0
    if (str(a),w) in dp: return dp[(str(a),w)]
    maxx=0
    for i in range(len(a)):
        if a[i][0]<=w:
            maxx=max(maxx,a[i][1]+solve(a[:i]+a[i+1:],w-a[i][0],dp))
    dp[(str(a),w)]=maxx
    return maxx
if __name__=='__main__':
    n,w=map(int,input().split())
    a=[]
    sw=0
    for i in range(n):
        p,q=map(int,input().split())
        a.append((p,q))
        sw+=a[-1][0]
    a.sort(key=lambda x: x[0])
    print(solve(a,w,{}))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

min_w_per_v = [10**11] * (10**6)
min_w_per_v[0] = 0

for i in range(N):
    w, v = wv[i]
    tmp = copy.deepcopy(min_w_per_v)
    for j in range(v, len(min_w_per_v)):
        min_w_per_v[j] = min(tmp[j], tmp[j-v]+w)
        
for n, i in enumerate(min_w_per_v[::-1]):
    if i <= W:
        print(10**6-n-1)
        break

Submission status: Time Limit Exceeded

Solution code:
#D
N,W=map(int,input().split())
w_list=[]
v_list=[]

for i in range(N):
    w1,v1=map(int,input().split())
    w_list.append(w1)
    v_list.append(v1)
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 w_list[i]<=w:
            dp[i+1][w]=max(dp[i][w-w_list[i]]+v_list[i],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,gcd,floor
from collections import deque,defaultdict 
from functools import lru_cache
from bisect import bisect_left,bisect_left,insort
from heapq import heappush as hpush , heappop as hpop
import sys
# sys.setrecursionlimit(10**5)
from itertools import permutations 
# input = sys.stdin.buffer.readline

inf=float("inf")

def inpi(): return(int(input()))
def inpa(): return(list(map(int,input().split())))
def inps(): return(list(input()))
def inpv(): return(map(int,input().split()))


N, W = inpv()
nums = []
for _ in range(N):
    nums.append(inpa())

dp = defaultdict(int)
s = set([0])
for weight,val in nums:
    t = set()
    for w in s:
        if weight + w <= W:
            dp[weight + w] = max(dp[weight + w] , dp[w]+val)
            t |= {weight + w}
    s |= t

print (max(dp.values()))

Submission status: Time Limit Exceeded

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

INF = float('inf')
V = max(v)
dp = [[INF for i in range(V * n + 1)] for j in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(V * n + 1):
        if v[i] <= j:
            dp[i + 1][j] = min(dp[i][j - v[i]] + w[i], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0
for i in range(V * n + 1):
    if dp[n][i] <= W:
        ans = i

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(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] = list(map(int, input().split()))

v_sum = sum(v)
w_max = 1000000000
n = 100

dp = []
visited = []
for i in range(v_sum+1):
    temp = []
    for j in range(n):
        temp.append(0)
    dp.append(temp)
    visited.append(temp)



def solve(val, index, w, v, w_len):
    if val <= 0:
        return 0
    if index == w_len:
        return w_max
    if visited[val][index]:
        return dp[val][index]

    visited[val][index] = 1

    dp[val][index] = min(solve(val, index+1, w, v, w_len), w[index] + solve(val-v[index], index+1, w, v, w_len))

    return dp[val][index]


flag = False
for i in range(v_sum, -1, -1):
    if solve(i, 0, w, v, len(w)) <= k:
        print(i)
        flag = True
        break


if not flag:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(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] = list(map(int, input().split()))


max_w = k
min_w = min(w)

dp = []

for i in range(n+1):
    temp = []
    for j in range(0, max_w-min_w+1):
        temp.append(0)
    dp.append(temp)


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

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

Submission status: Time Limit Exceeded

Solution code:
n, k = list(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] = list(map(int, input().split()))


dp = []

for i in range(n+1):
    temp = []
    for j in range(k+1):
        temp.append(0)
    dp.append(temp)


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

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

Submission status: Time Limit Exceeded

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

sum_v = sum([wv[i][1] for i in range(n)])

# dp[i][j]: i番目の品物までで価値がj以上であるときの重さの最小値
dp = [[float('inf')]*(sum_v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum_v+1):
        # 品物を選ぶ場合
        if (j - wv[i][1] >= 0):
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        # 品物を選ばない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = 0
for i in range(sum_v+1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, gettrace
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()
def main():
    n,w=map(int,input().split())
    li=[]
    for i in range(n):
        temp=[int(x) for x in input().split()]
        li.append(temp)
    dp=[[-1 for j in range(w+1)] for i in range(n+1)]
    for i in range(n,-1,-1):
        for j in range(0,w+1,1):
            if i==n or j==0:
                dp[i][j]=0        
            elif li[i][0]>j:
                dp[i][j]=dp[i+1][j]
            else:
                dp[i][j]=max(dp[i+1][j-li[i][0]]+li[i][1],dp[i+1][j])
    print(dp[i][w])
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys;
import math;
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

N,W = get_ints();
arr = [];
for i in range(N):
    tarr = get_array();
    arr.append(tarr);


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

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

print(dp[N][W]);

Submission status: Time Limit Exceeded

Solution code:
def knapsackBottomUp(wt,price,c,n,m):
    dp=[[float('inf') for x in range(m+1)] for y in range(n+1)]
    for l in range(n+1):
        dp[l][0]=0


    for i in range(1,n+1):
        wi=wt[i];vi=price[i]
        for V in range(1,m+1):
            if vi <= V:
                dp[i][V]=min(wi+dp[i-1][V-vi],dp[i-1][V])
            else:
                dp[i][V]=dp[i-1][V]

    res=0
    for i in range(m+1):
        if dp[n][i]<=c:
            res=i
    return res 
n,c=map(int,input().split())
wt=[]
price=[]
wt.append(0)
price.append(0)
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
max_val=sum(price)

print(knapsackBottomUp(wt,price,c,n,max_val))

Submission status: Time Limit Exceeded

Solution code:
def knapsackBottomUp(wt,price,c,n):
    dp=[[0 for x in range(c+1)] for y in range(n+1)]
    for i in range(n+1):
        for w in range(c+1):
            if i==0 or w==0:
                dp[i][w]=0
            else:
                inc=exc=0
                if wt[i-1]<=w:
                    inc=price[i-1]+dp[i-1][w-wt[i-1]]
                exc=dp[i-1][w]
                dp[i][w]=max(inc,exc)

    
    return dp[n][c]

n,c=map(int,input().split())
wt=[]
price=[]
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
print(knapsackBottomUp(wt,price,c,n))

Submission status: Time Limit Exceeded

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

MAX_V = sum(x[1] for x in wv)

INF = 1 << 60
dp = [0] + [INF] * MAX_V

for w, v in wv:
    # 退避
    dp_tmp = dp[:]
    for j in range(1, MAX_V + 1):
        prev = max(0, j - v)
        dp_tmp[j] = min(dp[j], dp[prev] + w)
    dp = dp_tmp


print(bisect.bisect_right(dp, W) - 1)

Submission status: Time Limit Exceeded

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

for i in range(1,N+1):    #i番目の荷物
    for j in range(1,W+1):   #上限の重さ
        if j>=w[i-1]:
            dp[j][i]=max(dp[j-w[i-1]][i-1]+v[i-1],dp[j][i-1])
        else:
            dp[j][i]=dp[j][i-1]
            
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

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

dp={}
dp_up={}
V_max=0

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

    V_max+=v

    for j in range(v,V_max+1):
        if j==v:
            if j in dp:
                dp_up[j]=min(dp[j],w)
                j_max=j
            else:
                dp_up[j]=w
                j_max=j
        else:
            if j-v in dp and dp[j-v]+w<=W:
                if j in dp:
                    dp_up[j]=min(dp[j],dp[j-v]+w)
                    j_max=j
                else:
                    dp_up[j]=dp[j-v]+w
                    j_max=j
    dp=dp_up.copy()
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
value=[]
wt=[]
for i in range(n):
    a,b=map(int,input().split())
    wt.append(a)
    value.append(b)
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(1,w+1):
        if wt[i-1]<=j:
            dp[i][j]=max(value[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from  collections import defaultdict


# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, w = map(int, input().split())
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = map(int, input().split())
	dp = [[0 for j in range(w + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			dp[i][j] = dp[i - 1][j]
			if wgt[i - 1] <= j:
				dp[i][j] = max(dp[i][j], val[i - 1] + dp[i - 1][j - wgt[i - 1]])
	ans = dp[-1][-1]
	print(ans)



if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Time Limit Exceeded

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_)
M=sum(v)
dp=[[float('inf')]*(M+1) for i in range(N+1)]
dp[0][0]=0

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# 入力部分
n, limit = map(int, input().split())
w, v = [], []
for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

# dpテーブルの要素数
V = sum(v)

INF = 1 << 60

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

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

dp = np.array(dp)

ans = 0
for arr in dp:
    ans = max(ans, np.where(arr <= limit)[0].max())

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int,input().strip().split(" "))
Vmax = 10**5
dp = [10**9+1] * (Vmax+1)
dp[0] = 0
Vtotal = 0

for _ in range(N):
    w, v = map(int, input().strip().split(" "))
    Vtotal += v
    for i in range(Vtotal-v, -1, -1):
        dp[i+v] = min(dp[i+v], dp[i]+w)

for v in range(Vtotal, -1, -1):
    if dp[v] <= W:
        print(v)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
vmax = 1000*100+1
wmax = 100*10**9
dp = [wmax] * vmax
dp[0] = 0

for i in range(N):
    wi, vi = map(int, input().split())
    ndp = dp[:]
    for j in range(vi, vmax):
        ndp[j] = min(dp[j], dp[j-vi] + wi)
    dp = ndp

v = 0
for i, w in enumerate(dp):    
    if w == wmax:
        continue
    if w <= W:
        v = i
print(v)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
vmax = 1000*100+1
dp = [100*10**9] * vmax
dp[0] = 0

for i in range(N):
    wi, vi = map(int, input().split())
    ndp = [100*10**9] * vmax

    for j in range(vmax):
        if j-vi >= 0:
            ndp[j] = min(dp[j], dp[j-vi] + wi)
        else:
            ndp[j] = dp[j]
    dp = ndp

v = 0
for i, w in enumerate(dp):    
    if w == 100*10**9:
        continue
    if w <= W:
        v = i

print(v)

Submission status: Time Limit Exceeded

Solution code:
def recur(n,w):
    if n==0 or w==0:
        return 0
    elif (n,w) in dp:
        return dp[(n,w)]
    elif l[n-1][0]<=w:
        k=max(recur(n-1,w-l[n-1][0])+l[n-1][1],recur(n-1,w))
        dp[(n,w)]=k
        return k
    else:
        k=recur(n-1,w)
        dp[(n,w)]=k
        return k
n,w=map(int,input().split())
l=[]
for _ in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
dp=dict()
print(recur(n,w))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    W, V = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[float('inf')]*(10**5+10) for i in range(N+1)]
    # for i in range(150):
    #     dp[0][i] = 0
    dp[0][0] = 0

    for i in range(N):
        for v in range(10**5+10):
            if v - V[i] >= 0:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v - V[i]] + W[i])
            dp[i+1][v] = min(dp[i+1][v], dp[i][v])
    ans = 0
    for v in range(10**5 + 10):
        if dp[N][v] <= M:
            ans = v
    print(ans)

if __name__ == '__main__':
    main()