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:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,W=LI()
m={}
for i in range(n):
    w,v=LI()
    if w in m:
        m[w].append(v)
    else:
        m[w]=[v]

a=[]
for i,j in m.items():
    sj=sorted(j)[::-1]
    aj=[sum(j)]
    for x in sj:
        aj+=[aj[-1]-x]
    a.append([i,len(j),aj])

cnt0=[0]*len(m.items())
weights=[i for i,j,k in a]

ans=0
sys.setrecursionlimit(10**6)

def dfs(cnt):
    global ans
    tot=0
    V=0
    for i in range(len(cnt)):
        tot+=cnt[i]*weights[i]
        if cnt[i]>a[i][1]:
            return
        V+=a[i][2][0]-a[i][2][cnt[i]]
    if tot>W:
        return
    ans=max(ans,V)
    for i in range(len(cnt)):
        l=[cnt[i] + (1 if i==j else 0) for j in range(len(cnt))]
        dfs(l)

dfs(cnt0)

print(ans)

Submission status: Time Limit Exceeded

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

def main():
  N, constW = map(int, input().split())
  WV = [list(map(int, input().split())) for _ in range(N)]
  W0 = WV[0][0]
  L = [[] for _ in range(4)]
  for w, v in WV:
    w -= W0
    L[w].append(v)
  L[0].sort(reverse=True)
  L[1].sort(reverse=True)
  L[2].sort(reverse=True)
  L[3].sort(reverse=True)
  ans = 0
  for i in range(1, constW//W0 + 1):
    rest = constW - i*W0
    for j in range(min(rest//3, i) + 1):
      rest1 = rest - 3*j
      for k in range(min(rest1//2, i-j) + 1):
        rest2 = rest1 - 2*k
        for l in range(min(rest2, i-j-k) + 1):
          temp = sum(L[3][:j]) + sum(L[2][:k]) + sum(L[1][:l]) + sum(L[0][:i-j-k-l])
          ans = max(ans, temp)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, wmax = map(int, input().split())
dp = [defaultdict(int) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    w, v = map(int, input().split())
    if i == 0:
        w0 = w
    for j in range(n+1):
        for k in range(300):
            weight = j*w0+k
            if weight <= wmax:
                if weight - w >= 0:
                    dp[i+1][weight] = max(dp[i+1][weight], dp[i][weight - w] + v)
                dp[i+1][weight] = max(dp[i+1][weight], dp[i][weight])

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

Submission status: Time Limit Exceeded

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

ans=0
for i in range(2**n):
  weight,val=0,0
  for j in range(n):
    if i>>j&1:
      if weight+WV[j][0]<=w:
        weight+=WV[j][0]
        val+=WV[j][1]
      else:
        break
  ans=max(ans,val)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
items = [tuple(map(int, input().split())) for i in range(N)]
items.insert(0, (0, 0))

v_max = sum([x[1] for x in items])

dp = [[10**13 for _ in range(v_max+1)] for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
    for j in range(v_max+1):
        # print(i,j)
        # take item
        if j-items[i][1] >= 0:
            dp[i][j] = dp[i-1][j-items[i][1]]+items[i][0]

        dp[i][j] = min(dp[i][j], dp[i-1][j])

# print(dp[N])

ans = 0
for i in range(v_max+1):
    if dp[N][i] <= W:
        ans = i

print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N,M = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(N)]
    dp = [0 for _ in range(M+1)]
    for i in range(N):
        for j in range(M-X[i][0]+1)[::-1]:
            dp[j+X[i][0]] = max(dp[j+X[i][0]],dp[j]+X[i][1])

    print(max(dp))

if __name__ == "__main__":
    main()

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

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
v_max = sum([i[1] for i in items])
INF = 10**12
dp = np.array([[INF for j in range(v_max+1)] for _ in range(N+1)])
dp[0, 0] = 0
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.minimum(dp[i-1, :-v] + w, dp[i-1, v:])
ans = 0
for v in range(v_max, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
dp = np.array([[0 for j in range(W+1)] for _ in range(N+1)])
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.maximum(dp[i-1, :-w] + v, dp[i-1, w:])
print(dp[N, W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
import heapq
from copy import deepcopy

# 各重さごとに価値降順でソート
# とっていく
# 重さ合計は w0 * k ~ (w0 + 3) * kのどれか N=100だと15000通りくらい

def solve(N: int, W: int, ws: "List[int]", vs: "List[int]"):
    w0 = ws[0]
    dp = defaultdict(lambda: [-1, []]) # dp[w]: 重さ合計wでの[最大価値, [w, w+1, w+2, w+3の数のリスト]]
    dp[0] = [0, [[0, 0, 0, 0]]]
    Q = []
    items = defaultdict(list)
    for w, v in zip(ws, vs):
        items[w].append(v)
    for w in range(w0, w0+4):
        items[w].sort(reverse=True)
    heapq.heappush(Q, 0)
    while len(Q) > 0:
        w_c = heapq.heappop(Q)
        if w_c > W:
            break
        v_c = dp[w_c][0]
        w_counts = dp[w_c][1]
        for w_count in w_counts:
            for i in range(4):
                if w_count[i] >= len(items[w0+i]):
                    continue
                
                v_n = v_c + items[w0+i][w_count[i]]
                w_n = w_c + w0+i
                if v_n < dp[w_n][0]:
                    continue
                
                w_count_n = deepcopy(w_count)
                w_count_n[i] += 1
                if v_n == dp[w_n][0]:
                    if w_count_n not in dp[w_n][1]:
                        dp[w_n][1].append(w_count_n)
                elif v_n > dp[w_n][0]:
                    dp[w_n][1] = [w_count_n]
                    dp[w_n][0] = v_n
                if w_n not in Q:
                    heapq.heappush(Q, w_n)
    res = 0
    for w in range(W+1):
        if dp[w][0] > res:
            res = dp[w][0]
    print(res)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in range(w+1):
  if i >= lis[0][0]:
    dp[0][i] = lis[0][1] 

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys, os
import numpy as np

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    N, W = f()
    w = np.zeros((N+1,1), dtype = int)
    v = np.zeros((N+1,1), dtype = int)

    for i in range(1,1+N):
        wtmp, vtmp = f()
        w[i] = wtmp
        v[i] = vtmp

    dp = np.zeros((N+1, N+1, 3*N+1), dtype = int)

    for i in range(1,N+1):
        for j in range(0,i+1):
            for k in range(3*j+1):
                dp[i][j][k] = dp[i-1][j][k]
                if k-(w[i] - w[1]) >=0 and j-1>=0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-(w[i] - w[1])] + v[i])

    ans = 0
    for j in range(N+1):
        for k in range(3*j+1):
            if j*w[1] + k <= W:
                ans = max(ans, dp[N][j][k])

    print(ans)




solve()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,W = (int(_) for _ in input().split())
    W = W+1
    w = []
    v = []
    for i in range(N):
        s1,s2 = (int(_) for _ in input().split())
        w.append(s1)
        v.append(s2)
    dp = []
    for i in range(N):
        dp.append(list(0 for _ in range(W)))
    
    for i in range(N):
        for j in range(w[i]-1,W):
            if(j>=w[i]):
                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[N-1]))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,W = (int(_) for _ in input().split())
    W = W+1
    w = []
    v = []
    for i in range(N):
        s1,s2 = (int(_) for _ in input().split())
        w.append(s1)
        v.append(s2)
    dp = []
    for i in range(N):
        dp.append(list(0 for _ in range(W)))
            
    for i in range(N):
        for j in range(W):
            if(j>=w[i]):
                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[N-1]))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w1, v1 = map(int, input().split())
vs[0].append(v1)
for i in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)
#print(vs)
for i in range(4):
    vs[i].sort()
#print(vs)
ans = 0
for i in range(N + 1):
    if i * w1 > W:
        break
    if i == 0:
        si = 0
    else:
        si = sum(vs[0][-i:])
    for j in range(N + 1 - i):
        if i * w1 + j * (w1 + 1) > W:
            break
        sj = si
        if j > 0:
            sj += sum(vs[1][-j:])
        for k in range(N + 1 - i - j):
            if i * w1 + j * (w1 + 1) + k * (w1 + 2) > W:
                break
            sk = sj
            if k > 0:
                sk += sum(vs[2][-k:])
            for l in range(N + 1 - i - j - k):
                if i * w1 + j * (w1 + 1) + k * (w1 + 2) + l * (w1 + 3) > W:
                    break
                sl = sk               
                if l > 0:
                    sl += sum(vs[3][-l:])
                ans = max(ans, sl)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,W = map(int, input().split())
iw,v = map(int, input().split())
d = {
    0: [v]
    ,1: []
    ,2: []
    ,3: []
}
for _ in range(1,n):
    w,v = map(int,input().split())
    d[w-iw].append(v)

for i in range(4):
    d[i] = sorted(d[i], reverse=True)

ret = -1
for i in range(n+1):
    if i*iw>W:
        break
    for j in range(n-i+1):
        if i*iw+j*(iw+1)>W:
            break
        for k in range(n-(i+j)+1):
            if i*iw+j*(iw+1)+k*(iw+2)>W:
                break
            for l in range(n-(i+j+k)+1):
                if i*iw+j*(iw+1)+k*(iw+2)+l*(iw+3)>W:
                    continue
                V = sum(d[0][:i])+sum(d[1][:j])+sum(d[2][:k])+sum(d[3][:l])
                ret = max(ret, V)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())

DP1 = [0 for _ in range(W+1)]
DP2 = [0 for _ in range(W+1)]

for w, v in A:
    for i in range(w, W+1):
        DP2[i] = max(DP1[i], DP1[i-w] + v)
    DP1 = deepcopy(DP2)

print(DP1[-1])

Submission status: Time Limit Exceeded

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

N, W = map(int, raw_input().split(' '))
w, v = [], []
for i in range(N):
    _w, _v = map(int, raw_input().split(' '))
    w.append(_w)
    v.append(_v)

toriuru_w = [0]
for p in range(N):
    toriuru_w.extend([w[0]*(p+1) + i for i in range(3*p+4)])
toriuru_w = list(set(toriuru_w))
toriuru_w = filter(lambda x: x <= W, toriuru_w)

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

#toriuru_w = [0, 5, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21]
def floor_like(n):
    min_, max_ = 0, len(toriuru_w)
    while max_ - min_ > 1:
        if n < toriuru_w[(min_ + max_) / 2]:
            max_ = (min_ + max_) / 2
        elif n > toriuru_w[(min_ + max_) / 2]:
            min_ = (min_ + max_) / 2
        else:
            return (min_ + max_) / 2

    return min_

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


print dp[-1][-1]

Submission status: Time Limit Exceeded

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

N, W = map(int, raw_input().split(' '))
w, v = [], []
for i in range(N):
    _w, _v = map(int, raw_input().split(' '))
    w.append(_w)
    v.append(_v)

toriuru_w = [0]
for p in range(N):
    toriuru_w.extend([w[0]*(p+1) + i for i in range(3*p+4)])
toriuru_w = list(set(toriuru_w))
toriuru_w = filter(lambda x: x <= W, toriuru_w)

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

#toriuru_w = [0, 5, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21]
def floor_like(n):
    min_, max_ = 0, len(toriuru_w)
    while min_ != max_:
        if n <= toriuru_w[(min_ + max_) / 2]:
            max_ = (min_ + max_) / 2
        else:
            min_ = (min_ + max_) / 2 + 1
            if min_ >= len(toriuru_w):
                return len(toriuru_w) - 1

    if toriuru_w[min_] == n:
        return min_
    else:
        return max(0, min_ - 1)


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


print dp[-1][-1]

Submission status: Time Limit Exceeded

Solution code:


temp = [int(i) for i in input().split()]

N = temp[0]
maxWeight = temp[1]


matrix = [[0 for i in range(maxWeight+1)] for j in range(N)]


# for i in range(N):
# 	matrix[i][0] = 0

value = []
weight = []

# items are stored as tuples (w, v) 
for i in range(N):
	x = [int(i) for i in input().split()]
	weight.append((x[0], x[1]))


for item in range(N):

	minStart = min(weight)[0]

	for totalWeight in range(minStart, maxWeight+1):		# we start from weight 0
		
		currentWeight = weight[item][0]

		if item == 0:
			if totalWeight < currentWeight:
				matrix[item][totalWeight] = 0
			
			else:
				matrix[item][totalWeight] = weight[item][1]


		else:
			if totalWeight < currentWeight:
				matrix[item][totalWeight] = matrix[item-1][totalWeight]

			else:
				pos1 = weight[item][1] + matrix[item-1][totalWeight-weight[item][0]]
				pos2 = matrix[item-1][totalWeight]
				matrix[item][totalWeight] = max(pos1, pos2)

# for i in matrix:
# 	print(i)

print(matrix[N-1][maxWeight])

Submission status: Time Limit Exceeded

Solution code:


temp = [int(i) for i in input().split()]

N = temp[0]
maxWeight = temp[1]


matrix = [[None for i in range(maxWeight+1)] for j in range(N)]


# for i in range(N):
# 	matrix[i][0] = 0

value = []
weight = []

# items are stored as tuples (w, v) 
for i in range(N):
	x = [int(i) for i in input().split()]
	weight.append((x[0], x[1]))

# weight.sort()

# for i in matrix:
# 	print(i)

# for i in weight:
# 	print(i)


for item in range(N):

	for totalWeight in range(maxWeight+1):		# we start from weight 0
		
		currentWeight = weight[item][0]

		if item == 0:
			if totalWeight < currentWeight:
				matrix[item][totalWeight] = 0
			
			else:
				matrix[item][totalWeight] = weight[item][1]


		else:
			if totalWeight < currentWeight:
				matrix[item][totalWeight] = matrix[item-1][totalWeight]

			else:
				pos1 = weight[item][1] + matrix[item-1][totalWeight-weight[item][0]]
				pos2 = matrix[item-1][totalWeight]
				matrix[item][totalWeight] = max(pos1, pos2)

# for i in matrix:
# 	print(i)

print(matrix[N-1][maxWeight])

Submission status: Time Limit Exceeded

Solution code:


temp = [int(i) for i in input().split()]

N = temp[0]
maxWeight = temp[1]


matrix = [[None for i in range(maxWeight+1)] for j in range(N)]


# for i in range(N):
# 	matrix[i][0] = 0

value = []
weight = []

# items are stored as tuples (w, v) 
for i in range(N):
	x = [int(i) for i in input().split()]
	weight.append((x[0], x[1]))

weight.sort()

# for i in matrix:
# 	print(i)

# for i in weight:
# 	print(i)


for item in range(N):

	for totalWeight in range(maxWeight+1):		# we start from weight 0
		
		currentWeight = weight[item][0]

		if item == 0:
			if totalWeight < currentWeight:
				matrix[item][totalWeight] = 0
			
			else:
				matrix[item][totalWeight] = weight[item][1]


		else:
			if totalWeight < currentWeight:
				matrix[item][totalWeight] = matrix[item-1][totalWeight]

			else:
				pos1 = weight[item][1] + matrix[item-1][totalWeight-weight[item][0]]
				pos2 = matrix[item-1][totalWeight]
				matrix[item][totalWeight] = max(pos1, pos2)

# for i in matrix:
# 	print(i)

print(matrix[N-1][maxWeight])

Submission status: Time Limit Exceeded

Solution code:

def knap_sack(w,ws,vs,n):
    k=[[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:
                k[i][j]=0
            elif ws[i-1]<=j:
                k[i][j]=max(vs[i-1]+k[i-1][j-ws[i-1]],k[i-1][j])
            else:
                k[i][j]=k[i-1][j]
    return k[n][w]



def main():
    line = input()
    line = line.split(' ')
    n = int(line[0])
    w = int(line[1])
    weight=[]
    val=[]
    for i in range(n):
        line=input()
        line=line.split(' ')
        weight.append(int(line[0]))
        val.append(int(line[1]))
    print(knap_sack(w,weight,val,n))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def knapsack(W,ws,vs,index):
    if W==0 or index==0:
        return 0
    if (ws[index-1]>W):
        return knapsack(W,ws,vs,index-1)
    return max(vs[index-1]+knapsack(W-ws[index-1],ws,vs,index-1),knapsack(W,ws,vs,index-1))


def main():
    line = input()
    line = line.split(' ')
    n = int(line[0])
    w = int(line[1])
    weight=[]
    val=[]
    for i in range(n):
        line=input()
        line=line.split(' ')
        weight.append(int(line[0]))
        val.append(int(line[1]))
    print(knapsack(w,weight,val,n))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
from itertools import izip


def sol(n, w, wis, vis):
    rv = 0
    best = dd(int)
    for i, (wi, vi) in enumerate(izip(wis, vis)):
        if wi < w:
            best[(wi, i)] = max(best[(wi, i)], vi)
            rv = max(vi, rv)

    frontline = [(i, wis[i], vis[i]) for i in xrange(n - 1, -1, -1)]
    while frontline:
        last, cw, cv = frontline.pop()
        for i in xrange(last + 1, n):
            nw, nv = cw + wis[i], cv + vis[i]
            if nw <= w and best[(nw, i)] < nv:
                best[(nw, i)] = nv
                frontline.append((i, nw, nv))
                rv = max(rv, nv)

    return rv


if __name__ == "__main__":
    n, w = map(int, raw_input().strip().split())
    wis, vis = [], []
    for _ in xrange(n):
        wi, vi = map(int, raw_input().strip().split())
        wis.append(wi)
        vis.append(vi)
    print sol(n, w, wis, vis)

Submission status: Time Limit Exceeded

Solution code:
#-*- coding: utf-8 -*-

def knapsack2(items, W):
    N = len(items)
    C = [[0 for _i in xrange(W+1)] for _j in xrange(N+1)]
    for i in range(N+1)[1:]:
        v, w = items[i-1]
        for j in range(W+1)[1:]:
            if j < w:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(C[i-1][j-w]+v, C[i-1][j])

    return C[-1][-1]


def input_str(row):
    res = []
    for _ in xrange(row):
        res.append(raw_input().split())
    return res


N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack2(items, W)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
inf = 1 << 32
 
def solve():
    N, W = map(int, input().split())
    ws = []
    vs = []
 
    for i in range(N):
        wi, vi = map(int, input().split())
        ws.append(wi)
        vs.append(vi)
 
    dp = [[[-inf]*(3*N + 1) for j in range(N + 1)]
                              for i in range(N + 1)]
 
    dp[0][0][0] = 0
 
    for i in range(N):
        for j in range(N + 1):
            for k in range(3*N + 1):
                dp[i + 1][j][k] = dp[i][j][k]
 
                if j - 1 >= 0 and k - (ws[i] - ws[0]) >= 0:
                    dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k - (ws[i] - ws[0])] + vs[i])
 
    ans = 0
 
    for j in range(N + 1):
        for k in range(3*N + 1):
            if ws[0]*j + k <= W:
                ans = max(ans, dp[N][j][k])
 
    print(ans)
 
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W = map(int, input().split())
    i = 0
    wv = []
    while i < N:
        wv.append(tuple(map(int, input().split())))
        i += 1

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

    print(dp[N][W])

main()

Submission status: Time Limit Exceeded

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

    dp = [[0 for i in range(W+1)] for j in range(N+1)]
    i = 1
    while i <= N:
        item = tuple(map(int, input().split()))
        for w in range(1, W+1):
            if item[0] <= w:
                dp[i][w] = max(item[1] + dp[i-1][w - item[0]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
        i += 1

    print(dp[N][W])

main()

Submission status: Time Limit Exceeded

Solution code:
from operator import sub
n, w = map(int, input().split())
data = [list(map(int, input().split())) for i in range(n)]
data.sort()
def brute(data, i, ww, n):
  if ww > 0 and i < n and data[i][0] <= ww:
    return max(brute(data, i+1, ww, n), data[i][1] + brute(data, i+1, ww-data[i][0], n))
  else: 
    return 0 
    
print(brute(data, 0, w, n))

Submission status: Time Limit Exceeded

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

#######################################

WNlist = arr = [[-1 for i in range(N+1)] for j in range(W+1)]
MonoList = []

for w,v in [ map(int,input().split()) for _ in range(N) ]:
	MonoList.append([w,v])

#MonoList = sorted(MonoList, key=lambda x:(x[0],x[1]), reverse=True)


def C(n,w):
	if n <= -1:
		return 0
	elif w == 0:
		return 0
	elif MonoList[n][0] > w:
		WNlist[w][n] = C(n-1,w)
		return C(n-1,w)

	if not WNlist[w][n] == -1:
		return WNlist[w][n]

	else:
		WNlist[w][n] = max( MonoList[n][1] + C(n-1,w-MonoList[n][0]) , C(n-1,w) )
		return WNlist[w][n]

print ( C(N-1,W) )

Submission status: Time Limit Exceeded

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

#######################################

WNlist = arr = [[0 for i in range(N)] for j in range(W)]
MonoList = []

for w,v in [ map(int,input().split()) for _ in range(N) ]:
	MonoList.append([w,v])

#MonoList = sorted(MonoList, key=lambda x:(x[0],x[1]), reverse=True)

def C(n,w):
	if n <= -1:
		return 0
	elif w == 0:
		return 0
	elif MonoList[n][0] > w:
		return C(n-1,w)

	else:
		return max( MonoList[n][1] + C(n-1,w-MonoList[n][0]) , C(n-1,w) )

print ( C(N-1,W) )

Submission status: Time Limit Exceeded

Solution code:
N, W = map(int, input().split())
ws = []
vs = []

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

w1 = ws[0]
s = 0

for i in range(N):
	ws[i] -= w1
	s += ws[i]

dp = [[[0]*(s+1) for i in range(N+1)] for k in range(N)]
for k in range(N):
	for i in range(1,N+1):
		for j in range(s+1):
			if j >= ws[i-1]:
				dp[k][i][j] = max(dp[k-1][i-1][j-ws[i-1]]+vs[i-1], dp[k][i-1][j])
			else:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i-1][j])
			if j > 0:
				dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
ans = 0
for k in range(N):
	if W < (k+1)*w1:
		break
	ans = max(ans, dp[k][N][min(W-(k+1)*w1, s)])
print(ans)
from sys import stderr
print(dp, file=stderr)