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:
#https://atcoder.jp/contests/dp/tasks/dp_d
#2019-01-13
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

ans = 0
for i in range(1 << N):
    cnt = 0
    weight = 0
    for j in range(N):
        if i & 1<<j:
            cnt += v[j]
            weight += w[j]
    if weight <= W:
        ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
    
dp = [[0]*(wmax+1) for _ in range(n+1)]

for i in range(1, n+1):
    for wi in range(1, wmax+1):
        if wi-w[i] >= 0:
            dp[i][wi] = max(dp[i-1][wi], dp[i-1][wi-w[i]]+v[i])
        else:
            dp[i][wi] = dp[i-1][wi]
            
print(dp[n][wmax])

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: 0}
for i in range(N):
    for cv, cw in list(dp.items()):
        if cw + w[i] > W:
            continue
        dp[cv + v[i]] = min(
            dp.get(cv + v[i], float('inf')),
            cw + w[i])
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])

def maxvalue_recursive(N, W):
    def memoize(func):
        func.d = d = {}
        def _f(*va):
            if va not in d: d[va] = func(*va)
            return d[va]
        return _f

    @memoize
    def maxvalue(i, w):
        if i < 0: return 0
        if w < ws[i]:
            return maxvalue(i - 1, w)
        else:
            return max(maxvalue(i - 1, w), maxvalue(i - 1, w - ws[i]) + vs[i])

    res = maxvalue(N - 1, W)
    return res

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

#print(maxvalue_recursive(N, W))
print(maxvalue_dp(N, W))

#import timeit
#print(timeit.timeit('maxvalue_recursive(N, W)', globals=globals(), number=10000))
#print(timeit.timeit('maxvalue_dp(N, W)', globals=globals(), number=10000))

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
WV=[]
for _ in range(N):
    WV.append(tuple(map(int,input().split())))
#i番目までの品物をコストw以下になるように選ぶ
dp=[[0]*(N+1) for _ in range(W+1)]
for i in range(1,N+1):
    for w in range(1,W+1):
        if w<WV[i-1][0]:
            dp[w][i]=dp[w][i-1]
        else:
            dp[w][i]=max(dp[w][i-1],dp[w-WV[i-1][0]][i-1]+WV[i-1][1])
print(dp[W][N])

Submission status: Time Limit Exceeded

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

#1からn番目の品物だけを使って、W_remainの重さ以下にする場合の価値総和の最大値
def maxval(n, W_remain):
    if (n,W_remain) not in nw:
        if n == 1:
            nw[n,W_remain] = wv[0][1] if wv[0][0] <= W_remain else 0
        else:
            if W_remain-wv[n-1][0] >= 0:
                m = max((wv[n-1][1] + maxval(n-1, W_remain-wv[n-1][0])),maxval(n-1, W_remain))
            else:
                m = maxval(n-1, W_remain)
            nw[n,W_remain] = m

    return nw[n,W_remain]

print(maxval(N, W))

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: 0}
for i in range(N):
    for cw, cv in list(dp.items()):
        if cw + w[i] > W:
            continue
        dp[cw + w[i]] = max(
            dp.get(cw + w[i], 0),
            cv + v[i])
print(max(dp.values()))

Submission status: Time Limit Exceeded

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

#1からn番目の品物だけを使って、W_remainの重さ以下にする場合の価値総和の最大値
def maxval(n, W_remain):
    if n == 1:
        nw[n,W_remain] = wv[0][1] if wv[0][0] <= W_remain else 0
        return nw[n,W_remain]
    else:
        if W_remain-wv[n-1][0] >= 0:
            m = max((wv[n-1][1] + maxval(n-1, W_remain-wv[n-1][0])),maxval(n-1, W_remain))
        else:
            m = maxval(n-1, W_remain)
        nw[n,W_remain] = m
        return m

print(maxval(N, W))

Submission status: Time Limit Exceeded

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

for _ in range(N):
    a, b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
A = [{0 : 0} for n in range(N + 1)]

for n in range(1, N + 1):
    w, v = map(int, input().split())
    keys = list(A[n - 1].keys())
    keys.sort(reverse=True)
    for key in keys:
        A[n][key] = A[n - 1][key]
        if key + w <= W:
            val = 0
            if key + w in A[n - 1].keys():
                val = A[n - 1][key + w]
            A[n][key + w] = max(A[n - 1][key] + v, val)
        else:
            A[n][key] = A[n - 1][key]

print(max(A[N].values()))

Submission status: Time Limit Exceeded

Solution code:
import sys
LI = lambda: list(map(int, sys.stdin.readline().split()))
N, W = LI()
dp = [0] * (W + 1)
for weight, value in sorted(LI() for _ in range(N)):
    for w in range(W - weight, -1, -1):
        if dp[w + weight] < dp[w] + value:
            dp[w + weight] = dp[w] + value
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple
Item = namedtuple('Item', ['weight', 'value'])
N, W = map(int, input().split())
items = [Item(*map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i, item in enumerate(items, 1):
    for cap in range(1, W + 1):
        if cap - item.weight >= 0:
            dp[i][cap] = max(dp[i - 1][cap],
                             dp[i - 1][cap - item.weight] + item.value)
        else:
            dp[i][cap] = dp[i - 1][cap]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,w = LI()
    aa = [LI() for _ in range(n)]
    r = [0] * (w+1)
    for a,b in aa:
        for i in range(w-a,-1,-1):
            if r[i+a] < b + r[i]:
                r[i+a] = b + r[i]

    return max(r)


print(main())

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N, W = LI()
L = [LI() for _ in range(N)]

# dp[w]: 容量wのナップザックの価値の総和の最大値
dp = [0] * (W + 1)
for weight, value in L:
    for w in range(W + 1)[::-1]:
        if w - weight < 0:
            continue
        dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[W])

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N, W = LI()
L = [LI() for _ in range(N)]

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W = map(int, input().split(' '))
WV = [list(map(int, input().split(' '))) for i in range(N)]
WV = np.array(WV)
# dp = [[0 for j in range(W+1)) for i in range(N)]
dp = np.zeros((N, W+1))

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
n, W = map(int, input().split())
dp = [-1] * int(1e6)
dp[0] = 0
for w, v in (map(int, readline().split()) for _ in range(n)):
    for j in range(W - w + 1, -1, -1):
        if dp[j] != -1 and dp[j + w] < dp[j] + v:
            dp[j + w] = dp[j] + v
print(max(dp[:W + 1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
n, W = map(int, input().split())
dp = [-1] * int(1e6)
dp[0] = 0
for i in range(n):
    w, v = map(int, readline().split())
    for j in range(W - w + 1, -1, -1):
        if dp[j] != -1 and dp[j + w] < dp[j] + v:
            dp[j + w] = dp[j] + v
print(max(dp[:W + 1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import collections

def update(dp, x, y, v):
    dp[x][y] = max(dp[x][y], v)

N, W = map(int, input().split())
dp = [collections.defaultdict(int) for _ in range(N + 1)]
for i in range(N):
    w, v = map(int, input().split())
    for j in dp[i]:
        update(dp, i + 1, j, dp[i][j])
        if j + w <= W:
            update(dp, i + 1, j + w, dp[i][j] + v) 
    update(dp, i + 1, w, v)

print(max(dp[N].values()))

Submission status: Time Limit Exceeded

Solution code:
n,W = (int(i) for i in input().split())
w,v = [],[]
for i in range(n):
    tmp = list(int(i) for i in input().split())
    w.append(tmp[0])
    v.append(tmp[1])

dp = list(list(0 for i in range(W+1)) for i in range(n+1))
for j in range(W+1):
    dp[n][j]=0

tmp = list(range(n))
i_rng = sorted(tmp, reverse=True)
for i in i_rng:
    for j in range(W+1):
        if j<w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]]+v[i])
print(dp[0][W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


class Item:
	def __init__(self):
		self.weight = 0
		self.value = 0

	def __repr__(self):
		return "(" + str(self.weight) + ", " + str(self.value) + ")"

items = []



def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def main():
	N, W = [int(x) for x in input().split()]
	global items
	
	for _ in range(0, N):
		x = Item()
		x.weight, x.value = [int(y) for y in input().split()]
		items.append(x)


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

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

	print(dp[N][W])

    

if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

class Item:
	def __init__(self):
		self.weight = 0
		self.value = 0

	def __repr__(self):
		return "(" + str(self.weight) + ", " + str(self.value) + ")"

items = []


def main():
	N, W = [int(x) for x in input().split()]
	global items
	
	for _ in range(0, N):
		x = Item()
		x.weight, x.value = [int(y) for y in input().split()]
		items.append(x)


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

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

	print(dp[N][W])

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値を返す
def f(i, j):
    # 終了条件
    if i == N:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    w, v = w_v[i]

    # これ以上入らないとき
    if j - w < 0:
        dp[i][j] = f(i+1, j)

    # まだ入るときは両方試す
    else:
        dp[i][j] = max(f(i+1, j), f(i+1, j-w)+v)
    return dp[i][j]

print(f(0, W))

Submission status: Time Limit Exceeded

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

def f(i, _w, _v):
    # 終了条件
    if i == N:
        return _v
    w, v = w_v[i]
    # i番目のものは入らないとき
    if _w + w > W:
        return f(i+1, _w, _v)

    # まだ入るときは両方試す
    else:
        return max(f(i+1, _w, _v), f(i+1, _w+w, _v+v))

print(f(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
n,wgt=map(int,input().split())
a=[]
v=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    v.append(y)

d={}

def dp(wgt,n): 
    if n==0 or wgt==0: 
        return 0
    if(a[n-1]>wgt):
        if((wgt,n-1) in d):
            return d[(wgt,n-1)] 
        return dp(wgt,n-1) 
    else:
        d1=0
        if (wgt,n-1) in d:
            d1=d[(wgt,n-1)]
        else:
            d1=dp(wgt,n-1)
        d2=0
        if (wgt-a[n-1],n-1) in d:
            d2=d[(wgt-a[n-1],n-1)]
        else:
            d2=dp(wgt-a[n-1],n-1)
        return max(v[n-1]+d2,d1)
print(dp(wgt,n))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] for i in goods])
dp = [float("inf") for i in range(v_sum + 1)]
dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        dp[j] = min(dp[j - goods[i][1]] + goods[i][0], dp[j])
 
for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        break

Submission status: Time Limit Exceeded

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

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


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

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

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

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


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

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
 
memo = [None] * (N * (W + 1))
def search(i, w, v):
    # end
    if i == N: return v
    # continue
    if memo[i * W + w] != None: return memo[i * W + w]
    dw, dv = wv[i]
    rets = [search(i + 1, w, v)]
    if w + dw <= W: rets.append(search(i + 1, w + dw, v + dv))
    ret = max(rets)
    memo[i * W + w] = ret
    return ret
 
print(search(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
n,wgt=map(int,input().split())
a=[]
v=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    v.append(y)

def dp(wgt,n): 
    if n==0 or wgt==0: 
        return 0
    if(a[n-1]>wgt): 
        return dp(wgt,n-1) 
    else: 
        return max(v[n-1]+dp(wgt-a[n-1],n-1),dp(wgt,n-1))
print(dp(wgt,n))

Submission status: Time Limit Exceeded

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

dp=[[-1 for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    a=[int(j) for j in input().split()]
    w.append(a[0])
    v.append(a[1])

def dfs(i,j):
    if dp[i][j]!=-1:
        return dp[i][j]
    if i==n:
        dp[i][j]=0
        return 0
    elif j<w[i]:
        dp[i][j]=dfs(i+1,j)
        return dfs(i+1,j)
    else:
        dp[i][j]=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
        return max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])

print(dfs(0,W))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())

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

for i in range(a):
	w,h = map(int,input().split())
	for j in range(b,w-1,-1):
		dp[j] = max(dp[j],dp[j-w] + h)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
a,b = map(int,input().split())

dp = [0 for i in range(b+10**6)]

for i in range(a):
	w,h = map(int,input().split())
	for j in range(b+10**6-1,w-1,-1):
		dp[j] = max(dp[j],dp[j-w] + h)

print(max(dp[:b+1]))

Submission status: Time Limit Exceeded

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

for i in range(n):
    a=[int(j) for j in input().split()]
    w.append(a[0])
    v.append(a[1])

def dfs(i,j):
    if i==n:
        return 0
    elif j<w[i]:
        return dfs(i+1,j)
    else:
        return max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])

print(dfs(0,W))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
c = []
for i in range(n):#h:高さ
    c.append([int(m) for m in input().split()])
dp = []
for i in range(n):
    dp.append([])
for i in range(n):
    for j in range(w + 1):
        dp[i].append(0)
dp[0][c[0][0]] = c[0][1]
#dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i][0](w)] + c[i][1](v))
#max(dp[n - 1])
for i in range(1, n):
    for j in range(w + 1):
        if j - c[i][0] >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i][0]] + c[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print(max(dp[n - 1]))

Submission status: Time Limit Exceeded

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

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

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

print(dp[n][w])

Submission status: Time Limit Exceeded

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

def Knap(i, lest, memo = {}): #残り重量lest時にi番目の品物を考慮するときの最大の価値
    if lest == 0:
        return 0
    elif i == N-1:
        return (Items[i][1] if Items[i][0] <= lest else 0)
    try:
        return memo[(i, lest)]
    except KeyError:
        WithToTake = 0
        if Items[i][0] <= lest:
            WithToTake = Items[i][1] + Knap(i+1, lest-Items[i][0], memo)
        WithoutToTake = Knap(i+1, lest, memo)
        memo[(i, lest)] = max(WithToTake, WithoutToTake)
        return max(WithToTake, WithoutToTake)

memo = {}
print(Knap(0, W, memo))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
# dp[i+1][w] i+1番目まで品物を選んで重さwのときの価値の最大値
# dp[0] = [0]*(W+1)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if  w - info[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w-info[i][0]] + info[i][1],dp[i][w])
        else:    
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
info = [list(map(int,input().split())) for i in range(N)]
# dp[i+1][w] i+1番目まで品物を選んで重さwのときの価値の最大値
# dp[0] = [0]*(W+1)
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if  w - info[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w-info[i][0]] + info[i][1],dp[i][w])
        else:    
            dp[i+1][w] = dp[i][w]
print(max(dp[N]))

Submission status: Time Limit Exceeded

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

    ans1 = f(N, W, wv)
    ans2 = simple(N, W, wv)

    # assert ans == ans2

    print(ans2)


def simple(N, W, wv):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, 1):
        for _w in range(1, W + 1):
            bef = dp[i-1][_w]
            dp[i][_w] = bef

            # 入れ替え
            if _w - w >= 0:
                changed = dp[i-1][_w - w] + v
                dp[i][_w] = max(bef, changed)

    ans = dp[N][W]
    return ans


def f(N, W, wv):
    """
    品物100を入れる入れないの 2^100 試せばOKだが、無理

    Nの入れる個数
        0から100
        正確にはN個までの選択なので、N個入れていないときもある
    最終容量     
        0から10^5
        正確にはWまでの重さなので、W以下のときもある
    10^7なら間に合いそう

    追加できるならば、追加してみる
    追加するものと入れ替えを試してみる
        追加の重さを引いたときの価値
        前の価値まま
            の大きい方
    """
    dp = [[-float("inf")] * (W + 1)
          for _ in range(N + 1)]

    # 品物を入れていないならば、価値はない
    # 品物を入れていないならば、重さはないので、価値はない
    # wi, vi >= 1 より
    dp[0] = [0] * (W + 1)
    for i in range(1, N + 1):
        dp[i][0] = 0

    for i, (w, v) in enumerate(wv, 1):
        for _w in range(1, W + 1):
            # まずは1つ前で補完, 価値は品物追加すれば単調増加なのでOK
            bef = dp[i-1][_w]
            dp[i][_w] = bef

            # 追加
            # 品物ループの内側にある重さのループではあるが、
            # このループでは何回も追加しないようになっている
            if _w + w <= W:
                changed = dp[i-1][_w] + v
                bef = dp[i-1][_w + w]
                # 補完と入れ替えを合わせると追加も兼ねている？
                # dp[i][_w + w] = max(bef, changed)

            # 入れ替え
            if _w - w >= 0:
                changed = dp[i-1][_w - w] + v
                bef = dp[i-1][_w]
                dp[i][_w] = max(bef, changed)

    # 補完により必ず[N][W] で最大
    # ans = max(dp[N])
    ans = dp[N][W]

    # from pprint import pprint
    # import sys
    # pprint(dp, stream=sys.stderr)
    return ans


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,W=map(int,input().split())
l=[]
arr=[[0]*(W+1) for i in range(n+1)]
for i in range(n):
  l.append(list(map(int,input().split())))
for i in range(n+1):
  for j in range(W+1):
    if(i==0 or j==0):
      arr[i][j]=0
    else:
      if(l[i-1][0]<=j):
        arr[i][j]=max(l[i-1][1]+arr[i-1][j-l[i-1][0]],arr[i-1][j])
      else:
        arr[i][j]=arr[i-1][j]
print(arr[n][W])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def 解():
    input = sys.stdin.readline

    N,W=[int(_) for _ in input().split()]
    dp={0:0}
    for i in range(N):
        w,v=[int(_) for _ in input().split()]
        for j in dp.copy():
            if dp[j]+w <= W:
                if j+v in dp:
                    dp[j+v] = min(dp[j+v],dp[j]+w)
                else:
                    dp[j+v] = dp[j]+w

    print(max(dp.keys()))
解()

Submission status: Time Limit Exceeded

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

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

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

memo = [None] * (N * (W + 1))
def search(i, w, v):
    # end
    if i == N: return v
    # continue
    if memo[i * W + w] != None: return memo[i * W + w]
    dw, dv = wv[i]
    rets = [search(i + 1, w, v)]
    if w + dw <= W: rets.append(search(i + 1, w + dw, v + dv))
    ret = max(rets)
    memo[i * W + w] = ret
    return ret

print(search(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# _*_ coding:utf-8 _*_
#  Atcoder_DPCollection_Contest01-d
#  TODO https://atcoder.jp/contests/dp/tasks/dp_d

N,W = map(int,input().strip().split(' '))
objectRange = range(0,N,+1)
weightList = []
valueList = []

for _ in objectRange:
	w_tmp,v_tmp = map(int,input().strip().split(' '))
	weightList.append(w_tmp)
	valueList.append(v_tmp)

DPTable = [[-1 for _ in range(0,W+1,+1)] for _ in range(0,N+1,+1)]

def selectObjectSolve(i,j):
	answer = -1
	if DPTable[i][j] != -1:
		return DPTable[i][j]
	else:
		if i == N:
			#  SELECT FINISH
			answer = 0
		elif j < weightList[i]:
			# Not Select i , because over clearly weight
			answer = selectObjectSolve(i+1,j)
		else:
			answer = max(selectObjectSolve(i+1,j),selectObjectSolve(i+1,j-weightList[i])+valueList[i])
	DPTable[i][j]=answer
	return answer

solution = selectObjectSolve(0,W)
print("{}".format(solution))

Submission status: Time Limit Exceeded

Solution code:
import sys
def 解():
    input = sys.stdin.readline

    N,W=[int(_) for _ in input().split()]
    #dp = [[0]*(W+1) for _  in range(N+1)]
    dp = [0]*(W+1)

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