Problem:


Score : 400 points

Problem Statement

You have N items and a bag of strength W.
The i-th item has a weight of w_i and a value of v_i.

You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

Constraints

1 ≤ N ≤ 100

1 ≤ W ≤ 10^9

1 ≤ w_i ≤ 10^9

For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.

1 ≤ v_i ≤ 10^7

W, each w_i and v_i are integers.

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 total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.



Sample input:
4 6
2 1
3 4
4 10
3 4


Sample output:
11

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, w = (int(x) for x in input().split())
dp = [[0 for i in range(w+1)] for j in range(n+1)] 
for i in range(n):
    a, b = (int(x) for x in input().split())
    for j in range(w+1):
        if j < a:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max([dp[i][j], dp[i][j-a]+b])
print(max(list(itertools.chain.from_iterable(dp))))

Submission status: Time Limit Exceeded

Solution code:
#060_D
n, w_ = map(int, input().split())
w, v = [], []

for _ in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
    
dp = [[0 for _ in range(w_+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, w_+1):
        if j < w[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])

print(dp[n][w_])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
wv = []
for _ in range(N):
  w,v = map(int,input().split())
  wv.append([w,v])
def rec(n,uplimit_w):
  ans = 0
  if n == N:
    return 0
  elif wv[n][0] > uplimit_w:
    return rec(n+1,uplimit_w)
  else:
    ans = max(rec(n+1,uplimit_w),rec(n+1,uplimit_w - wv[n][0])+wv[n][1])
    return ans
print(rec(0,W))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    x, y = map(int, input().split())
    w.append(x)
    v.append(y)
dp = [[0 for _ in range(W+2)] for _ in range(N+2)]
for i in range(N):
    for j in range(W+1):
        if j < w[i]:
            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:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def Knapsack1(w0,W,w,v): # n個の品物(重さw[i],価値v[i]) 総重量W以内での価値の最大化 計算量O(W*N)
    n=len(w)
    # dp[i][j] : i番目の品物で重さj以下の価値の最大値
    dp=[[0 for _ in range((w0+3)*n+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(W+1):
            dp[i][j]=max( dp[i][j],dp[i-1][j] )
            if j >= w[i-1]+w0:
                dp[i][j]=max(dp[i][j],dp[i-1][j-w[i-1]-w0]+v[i-1])
    print(max(dp[n]))


def main():
    n,W = inpm()
    w = []
    v = []
    w0 = 0
    for i in range(n):
        wv = inpl()
        if i == 0:
            w0 = wv[0]
        w.append(wv[0]-w0)
        v.append(wv[1])
    Knapsack1(w0,W,w,v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def Knapsack2(W,w,v): # n個の品物(重さw[i],価値v[i]) 価値iを達成する重量の最小化 計算量O(V*N)
    n=len(w)
    v_max=10**7+5
    # dp[i] : 価値iの組み合わせを達成する重量の最小値
    dp=[0]+[float('inf') for _ in range(v_max+1)]
    for i in range(n):
        for j in range(v_max,v[i]-1,-1):
            if j >= v[i]:
                dp[j]=min(dp[j],dp[j-v[i]]+w[i])
    ans=0
    for i in range(v_max+1):
        if dp[i]<=W:
            ans=i
    print(ans)

def main():
    n,W = inpm()
    w = []
    v = []
    for _ in range(n):
        wv = inpl()
        w.append(wv[0])
        v.append(wv[1])
    Knapsack2(W,w,v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

a = wv[0][0]
d = dict()

# i=0
d[str([0, 0])] = 0

for i in range(1, n + 1):
    for ii in range(i + 1):
        for j in range(a * ii, (a + 3) * ii + 1):
            # print(i, j)
            if j < wv[i - 1][0]:
                tmp = 0
                if str([i - 1, j]) in d:
                    tmp = max(tmp, d[str([i - 1, j])])
                d[str([i, j])] = tmp

            else:
                tmp = 0
                if str([i - 1, j]) in d:
                    tmp = max(tmp, d[str([i - 1, j])])
                if str([i - 1, j - wv[i - 1][0]]) in d:
                    tmp = max(tmp, d[str([i - 1, j - wv[i - 1][0]])] + wv[i - 1][1])

                d[str([i, j])] = tmp

ans = 0
for k in d.keys():
    w = int(k.split(', ')[1][:-1])
    if w <= W:
        ans = max(ans, d[k])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値(ときどき逆になることがあるので注意)
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])

print(knapsack(n,w,li))

Submission status: Time Limit Exceeded

Solution code:

def examD():
    N, W = LI()
    w = [0]*N
    v = [0]*N
    w[0], v[0] = LI()
    wbasic = w[0]
    for i in range(1,N):
        a, b = LI()
        w[i] = a-wbasic
        v[i] = b
    w[0] = 0
    dp =[[[0]*(3*N+1) for _ in range(N+1)]for _ in range(N+1)]
    for i in range(N):
        for j in range(N+1):
            for k in range(3*N+1):
                dp[i+1][j][k] = max(dp[i][j][k], dp[i+1][j][k])
                if w[i]<=k and j>=1:
                    if j*wbasic+k<=W:
                        dp[i+1][j][k] = max(dp[i][j-1][k-w[i]]+v[i], dp[i+1][j][k])
    ans = 0
    for v in dp[N]:
        ans = max(ans,max(v))
#        print(v)
    print(ans)


import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

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 i in range(W + 1)] for j in range(N + 1)]
for i in range(N-1, -1, -1):
	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:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,l[i][0]-1,-1):
        dp[j]=max(dp[j],dp[j-l[i][0]]+l[i][1])
print(dp[-1])

Submission status: Time Limit Exceeded

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

for index in range(n):
    for weight in range(w+1):
        if wlist[index] > weight:
            dp[index+1][weight] = dp[index][weight]
        elif wlist[index] <= weight:
            dp[index+1][weight] = max(dp[index][weight],
                                        dp[index][weight - wlist[index]] + vlist[index])

print(dp[n][w])

Submission status: Time Limit Exceeded

Solution code:
n,weight = map(int, input().split())
dp = [[0 for _ in range(weight+1)] for _ in range(n+1)]

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

Submission status: Time Limit Exceeded

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

w = [-1 for i in range(N)]
v = [-1 for i in range(N)]

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

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

def rec_dp(i,j):
    #もうない
    if i == N:
        return 0
    #既に調べてある
    if dp[i][j] != -1:
        return dp[i][j]
    #残りの容量が足りない
    elif j<w[i]:
        res = rec_dp(i+1,j)
    else:
        res = max(rec_dp(i+1,j),rec_dp(i+1,j-w[i])+v[i])
    return res

print(rec_dp(0,W))

Submission status: Time Limit Exceeded

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

w = [-1 for i in range(N)]
v = [-1 for i in range(N)]

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

def dfs(i,j):
    #終了条件
    if i == N:
        res = 0
    #残りの容量が足りない場合は次の荷物へ
    elif  j<w[i]:
        res = dfs(i+1,j)
    else:
        #選択しない場合/する場合
        res = max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
    return res

print(dfs(0,W))

Submission status: Time Limit Exceeded

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

w = [-1 for i in range(N)]
v = [-1 for i in range(N)]

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

#荷物を1つだけ入れた状態で、各許容重量の最大値を初期値として持たせる
for i in range(w[0],W+1):
    dp[0][i] = v[0]

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

'''
for i in range(N):
    print(dp[i])
'''

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

Submission status: Time Limit Exceeded

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

w = [-1 for i in range(N)]
v = [-1 for i in range(N)]

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

#荷物を1つだけ入れた状態で、各許容重量の最大値を初期値として持たせる
for i in range(w[0],W+1):
    dp[0][i] = v[0]

for i in range(1,N):
    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])
'''
for i in range(N):
    print(dp[i])
'''

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

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
a = []
for _ in range(n):
    w_in, v_in = map(int, input().split())
    a.append([w_in, v_in])

dp = [0 for _ in range((n + 1)*(w + 1))]
for j in range(w + 1):
    for i in range(n):
        w_in, v_in = a[i]
        if j + w_in <= w:
            dp[((i + 1) * (w)) + j + w_in] = max(dp[((i + 1) * w) + j + w_in], dp[(i * w) + j] + v_in)
            if i + 2 <= n:
                dp[((i + 2) * w) + j + w_in] = dp[((i + 1) * w) + j + w_in]
        dp[(i + 1) * w + j] = max(dp[(i + 1) * w + j], dp[i * w + j])
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n, w = map(int, input().split())
a = []
for _ in range(n):
    w_in, v_in = map(int, input().split())
    a.append([w_in, v_in])

dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for j in range(w + 1):
    for i in range(n):
        w_in, v_in = a[i]
        if j + w_in <= w:
            dp[i + 1][j + w_in] = max(dp[i + 1][j + w_in], dp[i][j] + v_in)
            if i + 2 <= n:
                dp[i + 2][j + w_in] = max(dp[i + 2][j + w_in], dp[i + 1][j + w_in])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max([max(d) for d in dp]))

Submission status: Time Limit Exceeded

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

w = [-1 for i in range(N)]
v = [-1 for i in range(N)]

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

#荷物を1つだけ入れた状態で、各許容重量の最大値を初期値として持たせる
for i in range(w[0],W+1):
    dp[0][i] = v[0]

for i in range(1,N):
    for j in range(W+1):
        #
        if j < w[i]:
            dp[i][j] = dp[i-1][j]
        #比較 詰めた一個前/詰めてちょうど/
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-w[i]]+v[i])


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,W = inputMap()
    
    DP = [[INF for _ in range(10**7)] for _ in range(N+1)]
    
    for i in range(N):
        w,v = inputMap()
        
        if i == 0:
            DP[i+1][0] = 0
            DP[i+1][v] = w
                
        else:
            for j in range(10**7):
                if DP[i][j] == INF:
                    continue
                DP[i+1][j] = min(DP[i+1][j], DP[i][j])
                DP[i+1][j+v] = min(DP[i+1][j+v], DP[i][j] + w)
                    
    ans = -1
    for i,val in enumerate(DP[N]):
        if val <= W:
            if ans < i:
                ans = i
            
    print(ans)
    
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

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

def knapsack(i, w) :
    if i == N :
        return 0
    
    M = knapsack(i + 1, w)
    
    if w >= wv[i][0] :
        M = max(M, knapsack(i + 1, w - wv[i][0]) + wv[i][1])
        
    return M
    
print(knapsack(0, W))

Submission status: Time Limit Exceeded

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

def knapsack(i, w) :
    if i == N :
        return 0
    
    M = knapsack(i + 1, w)
    
    if w >= wv[i][0] :
        M = max(M, knapsack(i + 1, w - wv[i][0]) + wv[i][1])
        
    return M
    
print(knapsack(0, W))

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int,input().split())
weights = N*[0]
values = N*[0]
for i in range(N):
    weights[i], values[i] = map(int,input().split())

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 weights[i] <= w:
            dp[i+1][w]=max(dp[i][w-weights[i]]+values[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy
N, W = map(int, raw_input().split())
pre = []
V = 0
for i in range(N):
    w, v = map(int, raw_input().split())
    V += v
    pre.append((w, v))
minw = min(pre)[0]
items1 = []
items2 = []
items3 = []
items4 = []
for w, v in pre:
    if w == minw:
        items1.append((w, v))
    elif w == minw + 1:
        items2.append((w, v))
    elif w == minw + 2:
        items3.append((w, v))
    else:
        items4.append((w, v))
items1.sort(reverse=True)
items2.sort(reverse=True)
items3.sort(reverse=True)
items4.sort(reverse=True)
items = [items1, items2, items3, items4]
memo = {}

def dfs(indice, W, value):
    if W < 0:
        return -(10**9)
    if W < minw or W == 0:
        return value
    if indice in memo:
        return memo[indice]
    outOfAmmo = True
    indicel = list(indice)
    sofar = -(10**9)
    for i in range(4):
        if indice[i] < len(items[i]):
            outOfAmmo = False
            new_indice = deepcopy(indicel)
            new_indice[i] += 1
            current_item = items[i][indice[i]]
            sofar = max(sofar, dfs(tuple(new_indice), W-current_item[0], value+current_item[1]))
    memo[indice] = sofar
    if outOfAmmo:
        return value
    return sofar
print dfs((0, 0, 0, 0), W, 0)

Submission status: Time Limit Exceeded

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

knap = [0 for i in range(W+1)]
mono = []

for i in range(N):
    w,v = map(int, input().split())
    mono.append([w,v])
mono.sort(key = lambda x:x[1], reverse=True)
for w, v in mono:
    for i in range(w, W+1)[::-1]:
        if knap[i] < knap[i-w] + v:
            knap[i] = knap[i-w] + v
print(knap[W])

Submission status: Time Limit Exceeded

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

knap = [0 for i in range(W+1)]
mono = []

for i in range(N):
    w,v = map(int, input().split())
    mono.append([w,v])
    
for w, v in mono:
    for i in range(w, W+1)[::-1]:
        knap[i] = max(knap[i], knap[i-w] + v)
print(knap[W])

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

N,W = 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] = map(int,input().split())

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


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

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

MAX_NUM = []
len_weights = 0
def dfs(nums):
    if len(nums) == len_weights:
        sum_w = 0
        value = 0
        for i in range(len_weights):
            sum_w += weights[i] * nums[i]
            value += sum(items[weights[i]][0:nums[i]])
        return value if sum_w <= W else 0
    value = 0
    i = len(nums)
    for j in range(MAX_NUM[i] + 1):
        value = max(value, dfs(nums + [j]))
    return value

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

for v in items.values():
    v.sort(reverse=True)

weights = sorted(items.keys())
len_weights = len(weights)
for w in weights:
    MAX_NUM.append(W // w)
print(dfs([]))

Submission status: Time Limit Exceeded

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

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

INF = float("inf")
dp = [[-INF for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):
  dp[0][i] = 0

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

Submission status: Time Limit Exceeded

Solution code:
def func(n, W, w):
    # ナップザック問題
    # 残り荷物 iつで,残り容量jの場合の最大価値
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
    for i in range(1, len(dp)):
        for j in range(len(dp[0])):
            if j-w[-i][0] >= 0:
                dp[i][j] = max(dp[i-1][j-w[-i][0]] + w[-i][1], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    # for i in range(len(dp)):
        # print(dp[i])
    return dp[n][W]
n, W = [int(i) for i in input().split()]
w = [[0, 0] for _ in range(n)]
for i in range(n):
    w[i] = [int(i) for i in input().split()]
print(func(n, W, w))
"""
# print("print(\" vs \" + str(func({}, {}, {})))".format(n, W, w))
print("11 vs " + str(func(4, 6, [[2, 1], [3, 4], [4, 10], [3, 4]])))
print("13 vs " + str(func(4, 6, [[2, 1], [3, 7], [4, 10], [3, 6]])))
print("400 vs " + str(func(4, 10, [[1, 100], [1, 100], [1, 100], [1, 100]])))
print("0 vs " + str(func(4, 1, [[10, 100], [10, 100], [10, 100], [10, 100]])))
"""

Submission status: Time Limit Exceeded

Solution code:

def solve(N, W, WVs):
    Ws = {}
    # print(N, ",", W, ",", WVs)
    for w, v in WVs:
        Ws.setdefault(w, []).append(v)
    for w, v in Ws.items():
        Ws[w] = sorted(v, key=lambda x: -x)
    wkeys = sorted(Ws.keys())

    m = 0
    for n1 in range(N + 1):
        w1 = n1 * wkeys[0]
        v1 = sum(Ws[wkeys[0]][:n1])
        if w1 > W:
            break
        for n2 in range(N - n1 + 1):
            if len(wkeys) >= 2:
                w2 = n2 * wkeys[1]
                v2 = sum(Ws[wkeys[1]][:n2])
            else:
                w2, v2 = 0, 0
            if w1 + w2 > W:
                break
            for n3 in range(N - n1 - n2 + 1):
                if len(wkeys) >= 3:
                    w3 = n3 * wkeys[2]
                    v3 = sum(Ws[wkeys[2]][:n3])
                else:
                    w3, v3 = 0, 0
                if w1 + w2 + w3 > W:
                    break
                for n4 in range(N - n1 - n2 - n3 + 1):
                    if len(wkeys) >= 4:
                        w4 = n4 * wkeys[3]
                        v4 = sum(Ws[wkeys[3]][:n4])
                    else:
                        w4, v4 = 0, 0

                    if w1 + w2 + w3 + w4 > W:
                        break
                    m = max(m, v1 + v2 + v3 + v4)

    return m


if __name__ == "__main__":
    N, W = map(int, input().split(" "))
    WVs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, W, WVs))

Submission status: Time Limit Exceeded

Solution code:
N,W = (int(i) for i in input().split())
weight =[]
value =[]
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]

for i in range(N):
  w,v = (int(i) for i in input().split())
  weight.append(int(w))
  value.append(int(v))
print(knapsack(N,W,weight,value))

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
wlist = [0] * N
vlist = [0] * N
for i in range(N):
	wlist[i], vlist[i] = map(int, input().split())
minw = min(wlist)
w = list()
for i in range(4):
	w.append(list())
for i in range(N):
	w[wlist[i] - minw].append(vlist[i])
for i in range(4):
	w[i].sort(reverse = True)
ans = 0
for i in range(len(w[0]) + 1):
	for j in range(len(w[1]) + 1):
		for k in range(len(w[2]) + 1):
			for l in range(len(w[3]) + 1):
				sumw = 0
				sumv = 0
				for z in range(i):
					sumw += minw
					sumv += w[0][z]
				for z in range(j):
					sumw += minw + 1
					sumv += w[1][z]
				for z in range(k):
					sumw += minw + 2
					sumv += w[2][z]
				for z in range(l):
					sumw += minw + 3
					sumv += w[3][z]
				if sumw <= W:
					ans = max(ans, sumv)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def abc060_d():
    from itertools import combinations
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    value = 0
    for i in range(1, n + 1):
        criteria = value
        for comb in combinations(wv, i):
            tmp_w = 0
            tmp_v = 0
            for a in comb:
                tmp_w += a[0]
            if tmp_w > w:
                continue
            else:
                for a in comb:
                    tmp_v += a[1]
                if tmp_v > criteria:
                    criteria = tmp_v
        if value > criteria:
            print(value)
            return None
        else:
            value = criteria
    print(value)


abc060_d()

Submission status: Time Limit Exceeded

Solution code:

#MAX_N = 25; # nの最大値

#入力
n, W = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
w = []
v = []
for i in range(n):
    w.append(s[i][0])
    v.append(s[i][1])
# DPテーブル
# dp[i][j]はi番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値を表す。
dp = []
for i in range(n + 1):
    dp.append([])
for p in range(n + 1):
    for q in range(W + 1):
        dp[p].append(-1)

#iが大きくjが小さい順（使える品物と容量が少ない順）にメモの値が確定
#def solve_dp2():
for j in range(W + 1):
    dp[n][j] = 0
for i in range(n - 1, -1, -1):
    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:

#MAX_N = 25; # nの最大値

#入力
n, W = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
w = []
v = []
for i in range(n):
    w.append(s[i][0])
    v.append(s[i][1])

# メモ化テーブル。
# dp[i][j]はi番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値を表す。
# -1なら値が未決定であることを表す
dp = []
for i in range(n + 1):
    dp.append([])
for p in range(n + 1):
    for q in range(W + 1):
        dp[p].append(-1)

# i番目以降の品物から重さの和がj以下なるように選んだときの、
# 取りうる価値の総和の最大値を返す関数
def rec(i, j):
    if dp[i][j] != -1:
    # すでに調べたことがあるならその結果を再利用
        return dp[i][j]

    #res = 0
    if i == n:
    # 品物がもう残っていないときは、価値の和の最大値は0で確定
        res = 0
        dp[i][j] = res
    elif j < w[i]:
    # 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理
    # i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする
        res = rec(i + 1, j)
        dp[i][j] = res
    else:
    # 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])#深さ優先探索
        dp[i][j] = res
    return dp[i][j]


print(rec(0, W))

Submission status: Time Limit Exceeded

Solution code:

#MAX_N = 25; # nの最大値

#入力
n, W = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
w = []
v = []
for i in range(n):
    w.append(s[i][0])
    v.append(s[i][1])

# i番目以降の品物から重さの和がj以下なるように選んだときの、
# 取りうる価値の総和の最大値を返す関数
def rec(i, j):
    #res = 0
    if i == n:
    # 品物がもう残っていないときは、価値の和の最大値は0で確定
        res = 0
    elif j < w[i]:
    # 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理
    # i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする
        res = rec(i + 1, j)
    else:
    # 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ
        res = max(rec(i + 1, j),rec(i + 1, j - w[i]) + v[i])
    return res

print(rec(0, W))

Submission status: Time Limit Exceeded

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

for i in range(1, n+1):
  items[i][0],items[i][1] = map(int,input().split())

for i in range(1,n+1):
  for j in range(1,w+1):
    if items[i][0] <= j:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-items[i][0]]+items[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())
dp = {(0,0)}
ans = 0
for i in range(n):
  a,b = map(int,input().split())
  gone = set()
  for num,nu in dp:
    gone.add((num,nu))
    if num + a <= w:
      gone.add((num+a,nu+b))
      ans = max(ans,nu+b)
  dp = gone
print(ans)

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

for i in range(N - 1, -1, -1):
    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:
N,W=map(int,input().split())
w,v=[None]*N,[None]*N
inf=float('inf')
dp=[[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
  w[i],v[i]=map(int,input().split())

for i in range(N-1,-1,-1):
  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:
import numpy as np
n,w = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    if i == 0:
      ti = x1
      zero = 0
      iti = 0
      ni = 0
      san = 0
    if x1 == ti:
      zero += 1
    elif x1 == ti+1:
      iti += 1
    elif x1 == ti+2:
      ni += 1
    else:
      san +=1
    x.append([x1,y1])
x.sort()
zer = x[:zero]
one = x[zero:iti+zero]
two = x[iti+zero:iti+ni+zero]
three = x[iti+ni+zero:zero+iti+ni+san]
zer.append([0,0])
one.append([0,0])
two.append([0,0])
three.append([0,0])
zer = sorted(zer,key = lambda x: -x[1])
one = sorted(one,key = lambda x: -x[1])
two = sorted(two,key = lambda x: -x[1])
three = sorted(three,key = lambda x: -x[1])
ans = 0
zer = np.array(zer)
one = np.array(one)
two = np.array(two)
three = np.array(three)
for i in range(len(zer)):
  for j in range(len(one)):
    for k in range(len(two)):
      for l in range(len(three)):
        omo = sum(zer[:i,0]) + sum(one[:j,0]) + sum(two[:k,0]) + sum(three[:l,0])
        kati  = sum(zer[:i,1]) + sum(one[:j,1]) + sum(two[:k,1]) + sum(three[:l,1])
        if omo <= w:
          ans = max(ans,kati)
print(ans)