Problem:


Score : 100 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

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

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

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

Sample Input 2

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

Sample Output 2

5000000000

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

Sample Input 3

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

Sample Output 3

17

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



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int,input().split())
li=[[int(i) for i in input().split()] for j in range(n)]

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
n, w = [int(i) for i in stdin.readline().split(' ')]
weights = []
values = []
for i in range(0, n):
    cur = [int(i) for i in stdin.readline().split(' ')]
    weights.append(cur[0])
    values.append(cur[1])

dp = defaultdict(lambda: defaultdict(int))
dp[0][0] = 0+0
for minInd in range(0, n):
    for allowed in range(0, w):
        dp[minInd+1][allowed] = max(dp[minInd+1][allowed], dp[minInd][allowed])
        if allowed+weights[minInd] <= w:
            dp[minInd+1][allowed+weights[minInd]] = max(dp[minInd+1][allowed+weights[minInd]], dp[minInd][allowed]+values[minInd])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict
import sys,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,w = inpl()
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = inpl()
dp = [[0 for i in range(w+1)] for j in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

memo = {}
def get_key(idx, w):
	return str(idx) + ":" + str(w)

#Errichto's implementation
def knapsack(n, w, weights, vals):
	dp = [0] * (w+1)
	for i in xrange(0, n):
		for w_a in xrange(w-weights[i], -1, -1):
			#print "weight already:", w_a
			#print "w[i]:", weights[i]
			#print "dp[w_a+ weights[i]", dp[weights[i]+w_a]
			#print "dp[w_a]:", dp[w_a]
			dp[weights[i]+w_a] = max(dp[weights[i]+w_a], dp[w_a] + vals[i])
			#print "setting dp[w_a+ weights[i]", dp[weights[i]+w_a]
	max_val = 0;
	for j in xrange(w+1):
		max_val = max(max_val, dp[j])
	return max_val


def knapsack_rec(n, w, weights, vals, idx):
	if idx == n:
		return 0
	if w == 0:
		return 0
	key_str = get_key(w, idx)
	if key_str in memo.keys():
		return memo[key_str]
	
	if weights[idx] > w:
		memo[key_str] = knapsack_rec(n, w, weights, vals, idx+1)
	else:
		memo[key_str] =  max(knapsack_rec(n, w-weights[idx], weights, vals, idx+1) + vals[idx], 
							 knapsack_rec(n, w, weights, vals, idx+1))
	return memo[key_str]

def knapsack_2d(n, w, weights, vals):
	dp = [[0] * (w+1) for i in xrange(n+1)]
	for i in xrange(1, n+1):
		for j in xrange(1, w+1):
			if weights[i-1] > j:
				dp[i][j] = dp[i-1][j]
			else:
				dp[i][j] = max(dp[i-1][j], vals[i-1] + dp[i-1][j-weights[i-1]])
	#rint dp
	return dp[n][w]
 	
	
def read_input():
	#Read the input N
	a = sys.stdin.readline().split()
	n = int(a[0])
	w = int(a[1])
	w_l = [0] * n
	v_l = [0] * n
	for i in xrange(n):
		a = sys.stdin.readline().split()
		w_l[i] = int(a[0])
		v_l[i] = int(a[1])
	result = knapsack(n, w, w_l, v_l)
#	result = knapsack_rec(n, w, w_l,v_l, 0)
	print result
		
if __name__ == '__main__':
	 read_input()

Submission status: Time Limit Exceeded

Solution code:
def A(w, v, n,V):
    mem=[0 for i in range(V+1)]
    if n == 0 or V == 0:
        return 0
 
    for i in range(n):
        for j in range(V,w[i]-1,-1):
            mem[j] = max(mem[j], v[i]+ mem[j - w[i]])
    return mem[V]
n,V=input().split()
n,V=int(n),int(V)
 
w=[0]*n
v=[0]*n
for i in range(n):
  x,y=input().split()
  w[i],v[i]=int(x),int(y)
 
print(A(w,v,n,V))

Submission status: Time Limit Exceeded

Solution code:
import sys

memo = {}
def get_key(idx, w):
	return str(idx) + ":" + str(w)

def knapsack_rec(n, w, weights, vals, idx):
	if idx == n:
		return 0
	if w == 0:
		return 0
	key_str = get_key(w, idx)
	if key_str in memo.keys():
		return memo[key_str]
	
	if weights[idx] > w:
		memo[key_str] = knapsack_rec(n, w, weights, vals, idx+1)
	else:
		memo[key_str] =  max(knapsack_rec(n, w-weights[idx], weights, vals, idx+1) + vals[idx], 
							 knapsack_rec(n, w, weights, vals, idx+1))
	return memo[key_str]

def knapsack(n, w, weights, vals):
	dp = [[0] * (w+1) for i in xrange(n+1)]
	for i in xrange(1, n+1):
		for j in xrange(1, w+1):
			if weights[i-1] > j:
				dp[i][j] = dp[i-1][j]
			else:
				dp[i][j] = max(dp[i-1][j], vals[i-1] + dp[i-1][j-weights[i-1]])
	#rint dp
	return dp[n][w]
 	
	
def read_input():
	#Read the input N
	a = sys.stdin.readline().split()
	n = int(a[0])
	w = int(a[1])
	w_l = [0] * n
	v_l = [0] * n
	for i in xrange(n):
		a = sys.stdin.readline().split()
		w_l[i] = int(a[0])
		v_l[i] = int(a[1])
#	result = knapsack(n, w, w_l, v_l)
	result = knapsack_rec(n, w, w_l,v_l, 0)
	print result
		
if __name__ == '__main__':
	 read_input()

Submission status: Time Limit Exceeded

Solution code:
import sys

def knapsack(n, w, weights, vals):
	dp = [[0] * (w+1) for i in xrange(n+1)]
	for i in xrange(1, n+1):
		for j in xrange(1, w+1):
			if weights[i-1] > j:
				dp[i][j] = dp[i-1][j]
			else:
				dp[i][j] = max(dp[i-1][j], vals[i-1] + dp[i-1][j-weights[i-1]])
	#rint dp
	return dp[n][w]
 	
	
def read_input():
	#Read the input N
	a = sys.stdin.readline().split()
	n = int(a[0])
	w = int(a[1])
	w_l = [0] * n
	v_l = [0] * n
	for i in xrange(n):
		a = sys.stdin.readline().split()
		w_l[i] = int(a[0])
		v_l[i] = int(a[1])
	result = knapsack(n, w, w_l, v_l)
	print result
		
if __name__ == '__main__':
	 read_input()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
n, w = [int(i) for i in stdin.readline().split(' ')]
weights = []
values = []
for i in range(0, n):
    cur = [int(i) for i in stdin.readline().split(' ')]
    weights.append(cur[0])
    values.append(cur[1])

dp = defaultdict(lambda: defaultdict(int))
dp[0][0] = 0
for minInd in range(0, n):
    for allowed in range(0, w):
        dp[minInd+1][allowed] = max(dp[minInd+1][allowed], dp[minInd][allowed])
        if allowed+weights[minInd] <= w:
            dp[minInd+1][allowed+weights[minInd]] = max(dp[minInd+1][allowed+weights[minInd]], dp[minInd][allowed]+values[minInd])

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

Submission status: Time Limit Exceeded

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

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] * (W+1) for _ in range(N+1)]
for i in range(N):
  for w in range(W+1):
    if w >= items[i][0]:
      dp[i+1][w] = max(dp[i][w-items[i][0]]+items[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())
wv_array = [[int(x) for x in input().split()] for y in range(n)]

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

index = 1
for ww, vv in wv_array:
    for capacity in range(1, w + 1):
        if ww <= capacity:
            dp[index][capacity] = max(dp[index - 1][capacity - ww] + vv, dp[index-1][capacity])
        else:
            dp[index][capacity] = dp[index - 1][capacity]
    index += 1
print(max(dp[n]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

print(table[n][W])

Submission status: Time Limit Exceeded

Solution code:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


N, W = map(int, input().split())
w = [0] * N
v = [0] * N

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

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from itertools import imap as map, izip as zip
from __builtin__ import xrange as range
from math import ceil
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
import sys
import os
import re
inf = float('inf')
mod = int(1e9) + 7
mod_ = 998244353
 
'''
Check for special cases (n=1)
One wrong submission = 10 mins penalty!
do smth instead of nothing and stay organized
'''

dp = dict()

def solve(n, cap, weights, values, ind):
	if ind == n:
		return 0
	if dp.get((ind, cap)):
		return dp[(ind, cap)]
		
	if cap >= weights[ind]:
		ans1 = values[ind] + solve(n, cap-weights[ind], weights, values, ind+1)
		ans2 = solve(n, cap, weights, values, ind+1)
		dp[(ind, cap)] = max(ans1, ans2)
	else:
		dp[(ind, cap)] = solve(n, cap, weights, values, ind+1)
	return dp[(ind, cap)]

def main():
	n, cap = map(int, input().split())
	weights, values = [0]*n, [0]*n
	for i in range(n):
		weights[i], values[i] = map(int, input().split())
	print(solve(n, cap, weights, values, 0))




BUFSIZE = 8192
class FastI(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = StringIO()
		self.newlines = 0
 
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()
 
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count("\n") + (not b)
			ptr = self._buffer.tell()
			self._buffer.seek(0, 2), self._buffer.write(
				b), self._buffer.seek(ptr)
		self.newlines -= 1
		return self._buffer.readline()
class FastO(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = __pypy__.builders.StringBuilder()
		self.write = lambda s: self._buffer.append(s)
 
	def flush(self):
		os.write(self._fd, self._buffer.build())
		self._buffer = __pypy__.builders.StringBuilder()
def print(*args, **kwargs):
	sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop("end", "\n"))
	if kwargs.pop("flush", False):
		file.flush()
def gcd(x, y):
	while y:
		x, y = y, x % y
	return x
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
	def bootstrap(cont):
		call, arg = cont.switch()
		while True:
			call, arg = cont.switch(to=continulet(
				lambda _, f, args: f(*args), call, arg))
	cont = continulet(bootstrap)
	cont.switch()
	main()

Submission status: Time Limit Exceeded

Solution code:
n, s = [int(i) for i in  input().split()]
weights = []
values = []

for _ in range(n):
    w, v = [int(i) for i in input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in range(limit+1)] for _ in range(n)]

    prev = [0 for _ in range(limit+1)]

    if weights[0] <= limit:
        for w in range(weights[0], limit+1):
            prev[w] = values[0]

    for i in range(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in range(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))

Submission status: Time Limit Exceeded

Solution code:
n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in xrange(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in xrange(limit+1)] for _ in xrange(n)]

    prev = [0 for _ in xrange(limit+1)]

    if weights[0] <= limit:
        for w in xrange(weights[0], limit+1):
            prev[w] = values[0]

    for i in xrange(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in xrange(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))

Submission status: Time Limit Exceeded

Solution code:
n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in range(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in range(limit+1)] for _ in range(n)]

    prev = [0 for _ in range(limit+1)]

    if weights[0] <= limit:
        for w in range(weights[0], limit+1):
            prev[w] = values[0]

    for i in range(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in range(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))

Submission status: Time Limit Exceeded

Solution code:
n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in range(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    f = [[0 for _ in range(limit+1)] for _ in range(n)]

    if weights[0] <= limit:
        for w in range(weights[0], limit+1):
            f[0][w] = values[0]

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

    return f[-1][-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))

Submission status: Time Limit Exceeded

Solution code:
nums, weight = map(int,input().split())
ary  = [0 for i in range(nums)]
for i in range(nums):
    ary[i] = list(map(int,input().split()))
dp =[[0 for i in range(weight+1)]for i in range(nums+1)]

check = 0
for i in range(nums):
    for x in range(weight+1):
        if x - ary[i][0] >= 0:
            check = dp[i][x -ary[i][0]] + ary[i][1]
            if check > dp[i+1][x]:
                dp[i+1][x] = check

        check = dp[i][x]
        if check > dp[i+1][x]:
            dp[i+1][x] = check

print(dp[nums][weight])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
INF = 10**11+1
dp = [[-1]*(W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  w,v = A[i-1]
  for j in range(W+1):
    dp[i][j] = dp[i-1][j]
    if j >= w and dp[i-1][j-w] != -1:
      dp[i][j] = max(dp[i-1][j-w]+v,dp[i][j])
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
INF = 10**11+1
dp = [[-1]*(W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  w,v = A[i-1]
  for j in range(W+1):
    if dp[i-1][j] != -1:
      dp[i][j] = dp[i-1][j]
    if j >= w and dp[i-1][j-w] != -1:
      dp[i][j] = max(dp[i-1][j-w]+v,dp[i][j])
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    things = []
    for i in range(N):
        things.append(LI())

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

    for i, wv in enumerate(things):  # 10**2
        w, v = wv
        if i == 0:
            for weight in range(W+1):  # 10**5
                knapsack_dp[i][weight] = 0 if weight < w else v
        else:
            for weight in range(W+1):
                if weight-w < 0:
                    knapsack_dp[i][weight] = knapsack_dp[i-1][weight]
                else:
                    knapsack_dp[i][weight] = max(knapsack_dp[i-1][weight], knapsack_dp[i-1][weight-w]+v)

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

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,W=map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]



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


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

Submission status: Time Limit Exceeded

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

memo = [[None  for _ in range(W+1)] for _ in range(N+1)]

def rec(check_item,residual_w):
    if memo[check_item][residual_w]:
        return memo[check_item][residual_w]    
    if check_item == N:
        res = 0
    elif residual_w < w_list[check_item]:
        res = rec(check_item+1, residual_w)
    else:
#         print(check_item,residual_w)
        res = max(rec(check_item+1,residual_w),
                  rec(check_item+1,residual_w-w_list[check_item])+v_list[check_item])
    memo[check_item][residual_w] = res
    
    return res

print(rec(0,W))

Submission status: Time Limit Exceeded

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

def main():
    N,W = map(int,input().split())
    dp = [0 for _ in range(W+1)]
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(W-nm+1)[::-1]:
            a = nm
            if dp[j+a] < dp[j] + nv:
                dp[j+a] = dp[j] + nv
    print(max(dp))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

def main():
    N,W = map(int,input().split())
    X = [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 w in range(W+1):
            if X[i][0] <= w:
                dp[i+1][w] = max(dp[i][w-X[i][0]]+X[i][1],dp[i+1][w])
            else:
                dp[i+1][w] = dp[i][w]
    dp = np.array(dp)
    print(dp.max())

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, W = map(int, input().split())
    items = [0] * N

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

    dp = [0] * (W + 1)

    for value, weight in items:
        for w in range(W + 1)[:: -1]:
            if w - weight >= 0:
                dp[w] = max(dp[w], dp[w - weight] + value)

    print(dp[W])

sol()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
I = lambda : map(int,stdin.readline().split())

N,tw = I()

w,v = [],[]

for i in range(N):
	W,V = I()
	w.append(W)
	v.append(V)

# print w,v
mat = []
for i in range(N+1):
	mat.append([0]*(tw+1))

# print mat[1][1]
for i in range(1,N+1):
	for j in range(1,tw+1):
		# print i,j
		no_curr = mat[i-1][j]
		yes_curr = 0
		weight_curr = w[i-1]
		if (j >= weight_curr):
			yes_curr = v[i-1] + mat[i-1][j - weight_curr]
		mat[i][j] = max(no_curr,yes_curr)
print mat[N][tw]

Submission status: Time Limit Exceeded

Solution code:

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

print(dp[W])

Submission status: Time Limit Exceeded

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

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

print(dp[W])

Submission status: Time Limit Exceeded

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

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

print(dp[W])

Submission status: Time Limit Exceeded

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

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

print(dp[W])

Submission status: Time Limit Exceeded

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

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

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

print(dp[W])

Submission status: Time Limit Exceeded

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

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

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

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

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n,w = [int(j) for j in raw_input().split()]
wt = []
v = []
for i in range(n):
        x,y = [int(j) for j in raw_input().split()]
        wt.append(x)
        v.append(y)
# dp = [[0 for i in range(n)] for j in range(w)]
dp = dict()
for i in range(n):
        for j in range(1,w+1):
                if wt[i]>j:
                        try:
                                dp[i,j] = dp[i-1,j]
                        except:
                                if i-1<0 or w<=0:
                                    dp[i,j] = 0    
                else:
                        if i-1<0:
                                dp[i,j] = v[i]
                        elif j-wt[i] <= 0:
                                dp[i,j] = max(v[i], dp[i-1,j])
                        else: 
                                dp[i,j] = max(dp[i-1,j-wt[i]]+v[i], dp[i-1,j])
                        

print(dp[n-1,w])

Submission status: Time Limit Exceeded

Solution code:
n,w = [int(j) for j in input().split()]
wt = []
v = []
for i in range(n):
        x,y = [int(j) for j in input().split()]
        wt.append(x)
        v.append(y)
# dp = [[0 for i in range(n)] for j in range(w)]
dp = dict()
for i in range(n):
        for j in range(1,w+1):
                if wt[i]>j:
                        try:
                                dp[i,j] = dp[i-1,j]
                        except:
                                if i-1<0 or w<=0:
                                    dp[i,j] = 0    
                else:
                        if i-1<0:
                                dp[i,j] = v[i]
                        elif j-wt[i] <= 0:
                                dp[i,j] = max(v[i], dp[i-1,j])
                        else: 
                                dp[i,j] = max(dp[i-1,j-wt[i]]+v[i], dp[i-1,j])
                        

print(dp[n-1,w])

Submission status: Time Limit Exceeded

Solution code:
wi,vi = 0, 1
N,W = map(int, input().split())

nupList = [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):

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#D
n,W = list(map(int,input().split()))
w = [0]*n
v = [0]*n
for i in range(n):
    w[i],v[i] = list(map(int,input().split()))
    
dp = [[0 for i in range(W+1)] for j in range(n)]
for i in range(n): #品物iまで
    for j in range(W+1):
        if j == 0:
            dp[i][j] = 0
            continue
        if j-w[i] >= 0:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i])
        else:
            dp[i][j] = dp[i-1][j]
print(max([dp[i][W]for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
N, W = list(map(int, input().split()))
W += 1
A = [[0] * W for _ in range(N)]
wi, vi = list(map(int, input().split()))

for w in range(W):
    A[0][w] = 0 if w < wi else vi

for i in range(1, N):
    wi, vi = list(map(int, input().split()))
    for w in range(W):
        A[i][w] = max([
            A[i-1][w_] + vi for w_ in range(w - wi + 1)
        ] + [A[i-1][w]])

print(max(A[-1]))

Submission status: Time Limit Exceeded

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

  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #入る可能性はない
        dp[i+1][w]=dp[i][w]
  return dp[N][W]

N,W = map(int,input().split(' '))
WEIGHT = []
VALUE = []
for i in range(N):
  w,v = map(int,input().split(' '))
  WEIGHT.append(w)
  VALUE.append(v)
print(knapsack(N,W,WEIGHT,VALUE))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int,input().split(' '))
DP = [[None]*(W+1)]*(N+1)
WV = list(tuple(map(int,input().split(' '))) for i in range(N))
DP[0] = [0]*(W+1)
for i in range(0,N):
  DP[i+1] = [None]*(W+1)
  for j in range(0,W+1):
    if WV[i][0] > j:
      DP[i+1][j] = DP[i][j]
    else:
      DP[i+1][j] = max(DP[i][j],DP[i][j-WV[i][0]] + WV[i][1])
print(DP[-1][-1])

Submission status: Time Limit Exceeded

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

wi = [ 0 for _ in range(N)]
vi = [ 0 for _ in range(N)]
for i in range(N):
    wi[i], vi[i] = [int(x) for x in input().split(' ')]

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]*(w+1)#dp[i]:重さiにおける最大価値
for i in range(n):#あるi番目の品物について
    for j in range(w,wv[i][0]-1, -1):
        dp[j] = max( dp[j], dp[j-wv[i][0]]+wv[i][1] )#i番目の品物を使うほうが良い場合は値を更新

print(max(dp))

Submission status: Time Limit Exceeded

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

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

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

print(dp[N][W])