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 collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

N,W = map(int,(input().split()))
ww = []
vv = []

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

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

for i in range(1,N+1):
	weight = ww[i-1]
	value = vv[i-1]
	for j in range(W+1):
		if j >= weight:
			dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight]+value)
		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())
WV = [[0,0]]
for i in range(N):
    WV.append(list(map(int, input().split())))

W1 = WV[0][0]
for i in range(N):
    WV[i][0] -= W1
    

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

W = W-N*W1

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:

N,W = map(int, input().split())
WV = [[0,0]]
for i in range(N):
    WV.append(list(map(int, input().split())))

W1 = WV[0][0]
for i in range(N):
    WV[i][0] -= W1
    

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

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

print(dp[N][W])

Submission status: Time Limit Exceeded

Solution code:
n,w=map(int, input().split())
weight,value=[],[]
for i in range(n):
    a,b=map(int, input().split())
    weight.append(a)
    value.append(b)

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>=weight[i] : dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else: dp[i+1][j]=dp[i][j]
print(dp[n][w])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

w = []
v = []

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

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

Ws = min(W,N*(w[0]+3))

for i in range(1,N+1):
    for j in range(Ws+1):
        if j-w[i-1]<0:
            EP[i][j] = EP[i - 1][j]
        else:
            EP[i][j] = max(EP[i-1][j],EP[i-1][j-w[i-1]] + v[i-1])

print(EP[N][Ws])

Submission status: Time Limit Exceeded

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

w = []
v = []

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

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

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

print(EP[N][W])

Submission status: Time Limit Exceeded

Solution code:
import sys

INF = float('inf')

N, W = map(int, sys.stdin.readline().split())

items = [] * N

for i in range(N):
    w, v = map(int, sys.stdin.readline().split())
    items.append([w,v])
    
dp = [[INF for i in range(W+1)] for j in range(N+1)] #dp[i][j]: i:N+1, j: W+1, iまでの品物を用いて大きさwまでの価値の合計

for i in range(W+1):
    dp[0][i] = 0
    
for i in range(N+1):
    dp[i][0] = 0
    
for i in range(1, N+1):
    for j in range(1, W+1):
        if j - items[i-1][0] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-items[i-1][0]] + items[i-1][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())
arr=[]
for _ in range(N):
    arr.append(list(map(int,input().split())))

def calc(p,w,v):
    if p==N:
        return v
    else:
        if w+arr[p][0]>W:
            return calc(p+1,w,v)
        else:
            return max(calc(p+1,w,v),calc(p+1,w+arr[p][0],v+arr[p][1]))

print(calc(0,0,0))

Submission status: Time Limit Exceeded

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

# i番目以降から重さの総和がj 以下になるように選んだ時の重量
def rec(i,j):
  #既に計算されているなら、メモdp[][]を受け取る
  if dp[i][j]>=0:
    return dp[i][j]
  if i==n:#もう品物がないから終わり
    res=0
  elif w[i]>j:#i番目の荷物は入らないから次へ
    res= rec(i+1,j)
  else:#i番目の荷物が入る場合と入らない場合の両方を試す
    res=max(rec(i+1,j), rec(i+1,j-w[i]) +v[i])
  dp[i][j]=res
  return res

dp=[[-1 for i in range(W+1)] for j in range(n+1)]#メモの初期化
print(rec(0,W))

Submission status: Time Limit Exceeded

Solution code:
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    w_tmp,v_tmp=map(int,input().split())
    w.append(w_tmp)
    v.append(v_tmp)

dp=[[ -1 for _ in range(W+1) ] for _  in range(N+1)]
def rec(i,j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i==N:
         res=0
    elif j<w[i]:
        res=rec(i+1,j)
    else:
        res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
    dp[i][j]=res
    return res

print(rec(0,W))

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(i) for i in input().split(' ')]
w = []
v = []
for i in range(N):
    new_w, new_v = [int(i) for i in input().split(' ')]
    w.append(new_w)
    v.append(new_v)
    
dp = [[-1 for j in range(W+1)] for i in range(N)]
for j in range(W+1):
    if w[0]<=j:
        dp[0][j] = v[0]
    else:
        dp[0][j] = 0

def rec(i, j):
    if not dp[i][j] == -1:
        return dp[i][j]
    if w[i]<=j:
        dp[i][j] = max(rec(i-1, j), rec(i-1, j-w[i])+v[i])
        #print(i, j, rec(i-1, j), rec(i-1, j-w[i])+v[i])
        return dp[i][j]
    else:
        dp[i][j] = rec(i-1, j)
        return dp[i][j]

print(rec(N-1,W))

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(i) for i in input().split(' ')]
w = []
v = []
for i in range(N):
    new_w, new_v = [int(i) for i in input().split(' ')]
    w.append(new_w)
    v.append(new_v)
    
dp = [[0 for j in range(W+1)] for i in range(N)]
for j in range(W+1):
    if w[0]<=j:
        dp[0][j] = v[0]
    
for i in range(1,N):
    for j in range(W+1):
        if w[i]<=j:
            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(dp[N-1][W])

Submission status: Time Limit Exceeded

Solution code:

# input
NW = [int(x) for x in input().split(" ")]
N = NW[0]
W = NW[1]

w = []
v = []

for _ in range(N):
	wv = [int(x) for x in input().split(" ")]
	w.append(wv[0])
	v.append(wv[1])

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

# 品物i-Nまでを使って容量Wのナップサックにいれられる品物の価値の総和の最大値
def rec(i, Wrec):
	if i >= N:
		return 0
	if memo[Wrec][i] != -1:
		return memo[Wrec][i]

	a = -1
	if Wrec - w[i] >= 0:
		a = v[i]+rec(i+1, Wrec-w[i])
	b = rec(i+1, Wrec)

	ret =  max(a, b)
	memo[Wrec][i] = ret
	return ret

print(rec(0,W))

Submission status: Time Limit Exceeded

Solution code:
# input
NW = [int(x) for x in input().split(" ")]
N = NW[0]
W = NW[1]

w = []
v = []

for _ in range(N):
	wv = [int(x) for x in input().split(" ")]
	w.append(wv[0])
	v.append(wv[1])

# 品物i-Nまでを使って容量Wのナップサックにいれられる品物の価値の総和の最大値
def rec(i, Wrec):
	if i >= N:
		return 0

	a = -1
	if Wrec - w[i] >= 0:
		a = v[i]+rec(i+1, Wrec-w[i])
	return max(
		a, #品物iを入れる
		rec(i+1, Wrec) #品物iを入れない
		)

print(rec(0,W))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, W0 = map(int, raw_input().split())
items = [map(int, raw_input().split()) for i in range(N)]
w0, _ = items[0]
dp = np.full((N, N*4), -1)
def dfs(i, W):
    if i < 0:
        return 0
    if (W-N*w0 >= 0) and (dp[i][W-N*w0] != -1):
        return dp[i][W-N*w0]
    w, v = items[i]
    res = dfs(i-1, W)
    if W >= w:
        res = max(res, dfs(i-1, W-w) + v)
    if (W-N*w0 >= 0):
        dp[i][W-N*w0] = res
    return res
print dfs(N-1, W0)

Submission status: Time Limit Exceeded

Solution code:

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

weights = []
values = []
for i in range(N):
    lst = [int(e) for e in input().split()]
    weights.append(lst[0])
    values.append(lst[1])

#df = np.array(ary)

def rec(i, j):
    if i == N:
        return 0
    elif j < weights[i]:
        return rec(i+1, j)
    else:
        return max(rec(i+1, j), rec(i+1, j-weights[i]) + values[i])

print(rec(0, W))

Submission status: Time Limit Exceeded

Solution code:

ini=map(int,raw_input().split())
lis=[]
for i in range(ini[0]):
    a=map(int,raw_input().split())
    lis.append(a)
 
lis.sort(key=lambda x:x[0])

def wight(loc,sum,val):
    ans=val
    if sum!=ini[1]:
        for i in range(ini[0]-loc):
            if sum+lis[i+loc][0]<=ini[1]:
                pre=wight(i+loc+1,sum+lis[i+loc][0],val+lis[i+loc][1])
                if pre>ans:
                    ans=pre
            else:
                break
    return ans

ca=wight(0,0,0)
     
print ca

Submission status: Time Limit Exceeded

Solution code:
# ARC60 D input
nw = list(map(int, input().split()))
N = nw[0]
w_limit = nw[1]

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

# ARC60 D recursive with memorization
dp = [{} for i in range(w_limit+1) for j in range(N+1)]
def rec_dp(i, j):
    if(j in dp[i]):
        return dp[i][j]
    
    res = 0
    if(i == N):
        res = 0
    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])
    
    dp[i][j] = res
    return res

print(rec_dp(0, w_limit))

Submission status: Time Limit Exceeded

Solution code:
ini=map(int,raw_input().split())
lis=[]
for i in range(ini[0]):
	a=map(int,raw_input().split())
	lis.append(a)

def wight(loc,sum,val):
	ans=val
	if sum!=ini[1]:
		for i in range(ini[0]-loc):
			if sum+lis[i+loc][0]<=ini[1]:
				pre=wight(i+loc+1,sum+lis[i+loc][0],val+lis[i+loc][1])
				if pre>ans:
					ans=pre
	return ans

ca=wight(0,0,0)

print ca

Submission status: Time Limit Exceeded

Solution code:
ini=map(int,raw_input().split())
lis=[]
for i in range(ini[0]):
	a=map(int,raw_input().split())
	lis.append(a)

def wight(loc,sum,val):
	ans=val
	for i in range(ini[0]-loc):
		if sum+lis[i+loc][0]<=ini[1]:
			pre=wight(i+loc+1,sum+lis[i+loc][0],val+lis[i+loc][1])
			if pre>ans:
				ans=pre
	return ans

ca=wight(0,0,0)

print ca

Submission status: Time Limit Exceeded

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

    ans = []
    mask = 0
    while mask < 1<<N:
        i = 0
        w = 0
        v = 0
        while i < N:
            if mask & 1<<i:
                w += WN[i]
                if w > W:
                    break
                else:
                    v += VN[i]
            i += 1
        if w <= W:
            ans.append(v)
        mask += 1

    print(max(ans))

main()

Submission status: Time Limit Exceeded

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

    ans = []
    mask = 0
    while mask < 1<<N:
        i = 0
        w = 0
        v = 0
        while i < N:
            if mask & 1<<i:
                w += WN[i]
                v += VN[i]
            i += 1
        if w <= W:
            ans.append(v)
        mask += 1

    print(max(ans))

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, W = map(int, input().split())
    VN = []
    WN = []
    for i in range(N):
        w, v = map(int, input().split())
        WN.append(w)
        VN.append(v)

    ans = 0
    mask = 0
    while mask < 1<<N:
        i = 0
        w = []
        v = []
        while i < N:
            if mask & 1<<i:
                w.append(WN[i])
                v.append(VN[i])
            i += 1
        if sum(w) <= W:
            ans = max(ans, sum(v))
        mask += 1

    print(ans)

main()

Submission status: Time Limit Exceeded

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

def check(N,W,w,v):
    cost_now=0
    for i in range(1,N+1):
        tmp=list(itertools.combinations(w,i))
        for tmptmp in tmp:
            sumsum = sum([ele[1] for ele in tmptmp])
            if sumsum <= W:
                cost_tmp=sum([v[ele[0]] for ele in tmptmp])
                if cost_tmp > cost_now:
                     cost_now = cost_tmp
    return cost_now

print(check(N,W,w,v))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

from collections import defaultdict
import itertools

if __name__ == "__main__":
    N, W = map(int, raw_input().split(" "))

    items = defaultdict(list)
    item_num = defaultdict(int)
    for i in range(N):
        w, v = map(int, raw_input().split(" "))
        if i == 0:
            w_list = range(w, w + 4)
        items[w].append(v)
        item_num[w] += 1

    for k in items.keys():
        items[k].sort(reverse = True)

    cum = defaultdict(list)
    for k in items.keys():
        sum_val = 0
        for e in items[k]:
            sum_val += e
            cum[k].append(sum_val)

    max_val = 0
    weights = items.keys()
    kinds = len(items.keys())
    for element in itertools.product(range(N + 1), repeat = kinds):
        w_sum = 0
        over_flag = False
        for i in range(kinds):
            if element[i] > item_num[weights[i]]:
                over_flag = True
                break
            w_sum += weights[i] * element[i]

        if w_sum > W or over_flag:
            continue

        val = 0
        for i in range(kinds):
            if element[i] >= 1:
                val += cum[weights[i]][element[i] - 1]
        if val > max_val:
            max_val = val

    print max_val

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

from collections import defaultdict
import itertools

if __name__ == "__main__":
    N, W = map(int, raw_input().split(" "))

    items = defaultdict(list)
    item_num = defaultdict(int)
    for i in range(N):
        w, v = map(int, raw_input().split(" "))
        if i == 0:
            w_list = range(w, w + 4)
        items[w].append(v)
        item_num[w] += 1

    for k in items.keys():
        items[k].sort(reverse = True)

    max_val = 0
    weights = items.keys()
    kinds = len(items.keys())
    for element in itertools.product(range(N + 1), repeat = kinds):
        w_sum = 0
        for i in range(kinds):
            w_sum += weights[i] * element[i]
        if w_sum > W:
            continue
        val = 0
        for i in range(kinds):
            val += sum(items[weights[i]][:element[i]])
        if val > max_val:
            max_val = val

    print max_val

Submission status: Time Limit Exceeded

Solution code:

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

wv = [[0 for i in range(2)] for j in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

wv.sort()

for i in range(N):
    Wsum[i+1] = Wsum[i] + wv[i+1][0]
    Vsum[i+1] = Vsum[i] + wv[i+1][1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #制約が0のときも価値は0
    if W2 == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は入れられない
    if W2 < wv[i][0]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-wv[i][0])+wv[i][1] , nap(i-1,W2) )
    
            
print(nap(N,W))

Submission status: Time Limit Exceeded

Solution code:

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

wv = [[0 for i in range(2)] for j in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

sorted(wv)

for i in range(N):
    Wsum[i+1] = Wsum[i] + wv[i+1][0]
    Vsum[i+1] = Vsum[i] + wv[i+1][1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #制約が0のときも価値は0
    if W2 == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は入れられない
    if W2 < wv[i][0]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-wv[i][0])+wv[i][1] , nap(i-1,W2) )
    
            
print(nap(N,W))

Submission status: Time Limit Exceeded

Solution code:

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

wv = [[0 for i in range(2)] for j in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

sorted(wv)

for i in range(N):
    Wsum[i+1] = Wsum[i] + wv[i+1][0]
    Vsum[i+1] = Vsum[i] + wv[i+1][1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < wv[i][0]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-wv[i][0])+wv[i][1] , nap(i-1,W2) )
    
            
print(nap(N,W))

Submission status: Time Limit Exceeded

Solution code:

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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))

Submission status: Time Limit Exceeded

Solution code:

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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] < W2:
        return Vsum[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))

Submission status: Time Limit Exceeded

Solution code:

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

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

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

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    W3 = 0
    for j in range(i):
        W3 = W3 + w[j+1]
    if W3 < W2:
        V3 = 0
        for j in range(i):
            V3 = V3 + v[j+1]
        return V3
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))

Submission status: Time Limit Exceeded

Solution code:

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

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

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

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))

Submission status: Time Limit Exceeded

Solution code:

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

w = [0]*N
v = [0]*N
Vmax = [[0 for i in range(W+1)] for j in range(N+1)]

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


# i個目の品物を追加
for i in range(N):
    for j in range(W+1):
        if j<w[i]:
            Vmax[i+1][j] = Vmax[i][j]
            continue        
        if Vmax[i][j-w[i]] + v[i] <= Vmax[i][j]:
            Vmax[i+1][j] = Vmax[i][j]
            continue
        else:
            Vmax[i+1][j] = Vmax[i][j-w[i]] + v[i]      


            
print(Vmax[N][W])

Submission status: Time Limit Exceeded

Solution code:

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

w = [0]*N
v = [0]*N
Vmax = [[0 for i in range(W+1)] for j in range(N+1)]

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


# i個目の品物を追加
for i in range(N):
    for j in range(W+1):
        Vmax[i+1][j] = Vmax[i][j]
        
        if j<w[i]:
            Vmax[i+1][j] = Vmax[i][j]
            continue
        
        if Vmax[i][j-w[i]] + v[i] > Vmax[i][j]:
            Vmax[i+1][j] = Vmax[i][j-w[i]] + v[i]
        else:
            Vmax[i+1][j] = Vmax[i+1][j]
            
    

            
print(Vmax[N][W])

Submission status: Time Limit Exceeded

Solution code:
N,W=list(map(int,input().split()))
v=[[],[],[],[]]
kosu=[0,0,0,0]
kr=list(map(int,input().split()))
v[0].append(kr[1])
w0=kr[0]
for i in range(1,N):
    kr=list(map(int,input().split()))
    v[kr[0]-w0].append(kr[1])
for i in range(4):
    v[i].sort()
    v[i].reverse()
kos=[len(v[0]),len(v[1]),len(v[2]),len(v[3])]
def toru(a,b,c,d,nw):
    max=0
    if a<kos[0] and W>=nw+w0 and max<toru(a+1,b,c,d,nw+w0)+v[0][a]:
        max=toru(a+1,b,c,d,nw+w0)+v[0][a]
    if b<kos[1] and W>=nw+w0+1 and max<toru(a,b+1,c,d,nw+w0+1)+v[1][b]:
        max=toru(a,b+1,c,d,nw+w0+1)+v[1][b]
    if c<kos[2] and W>=nw+w0+2 and max<toru(a,b,c+1,d,nw+w0+2)+v[2][c]:
        max=toru(a,b,c+1,d,nw+w0+2)+v[2][c]
    if d<kos[3] and W>=nw+w0+3 and max<toru(a,b,c,d+1,nw+w0+3)+v[3][d]:
        max=toru(a+1,b,c,d+1,nw+w0+3)+v[3][d]
    return max


maxv=toru(0,0,0,0,0)

print(maxv)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, W = map(int, raw_input().split())
w = np.array([])
v = np.array([])
for i in range(N):
    temp0, temp1 = map(int, raw_input().split())
    w = np.append(w, temp0)
    v = np.append(v, temp1)

def searchTable(item, weight):
    for i in range(len(table)):
        if table[i][0] == item and table[i][1] == weight:
            return True, table[i][2]
    return False, -1

def function(item, weight, table):
    flag, data = searchTable(item, weight)
    if flag:
        return data
    if item == N:
        result = 0
    elif weight < w[item]:
        result = function(item + 1, weight, table)
    else:
        result = max(function(item + 1, weight - w[item], table) + v[item], function(item + 1, weight, table))
    table = np.append(table, np.array([item, weight, result]))
    return result

table = np.array([])
print(int(function(0, W, table)))

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)] # 全て0、何も選ばない
selected = [[0 for _ in range(W+1)] for _ in range(N+1)]

items = [(0,0)] # [(weight:int, value:int)]
for i in range(N):
    weight, value = map(int, input().split())
    items.append((weight, value))

def update(w, i):
    def item_in(w, i):
        if ((w - items[i][0]) < 0):
            return 0
        elif i - 1 < 0:
            return items[i][1]
        else:
            return DP[i - 1][w - items[i][0]] + items[i][1]

    def not_in(x, y):
        return DP[i-1][w]

    return max(item_in(w, i), not_in(w, i))

for i in range(1, N+1):
    for w in range(items[i][0]-1,W+1):
        DP[i][w] = update(w, i)

print(DP[N][W])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, w = map(int, input().split())
ws = np.zeros(n, dtype=int)
vs = np.zeros(n, dtype=int)
for i in range(n):
    ws[i], vs[i] = map(int, input().split())
max_w = np.max(w)
min_w = np.min(w)

def search_max(i, v_vsorted, w_vsorted, sum_v, sum_w):
    if i >= n:
        return sum_v
    max_v1 = search_max(i + 1, v_vsorted, w_vsorted, sum_v, sum_w)
    sum_v += v_vsorted[i]
    sum_w += w_vsorted[i]
    if sum_w <= w:
        max_v2 = search_max(i + 1, v_vsorted, w_vsorted, sum_v, sum_w)
    else:
        return max_v1
    return max(max_v1, max_v2)
max_v = search_max(0, vs, ws, 0, 0)
print(max_v)

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)] # 全て0、何も選ばない
selected = [[0 for _ in range(W+1)] for _ in range(N+1)]

items = [(0,0)] # [(weight:int, value:int)]
for i in range(N):
    weight, value = map(int, input().split())
    items.append((weight, value))

def update(w, i):
    def item_in(w, i):
        if ((w - items[i][0]) < 0):
            return 0
        elif i - 1 < 0:
            return items[i][1]
        else:
            return DP[i - 1][w - items[i][0]] + items[i][1]

    def not_in(x, y):
        return DP[i-1][w]

    return max(item_in(w, i), not_in(w, i))

for i in range(N+1):
    for w in range(W+1):
        DP[i][w] = update(w, i)

print(DP[N][W])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

def max_value(items, space):
    if len(items) == 1:
        if space >= items[0][0]:
            return items[0][1]
        else:
            return 0

    selected = 0
    not_selected = 0
    if space >= items[0][0]:
        selected = items[0][1] + max_value(items[1:], space - items[0][0])
        not_selected = max_value(items[1:], space)

    return max(selected, not_selected)

def main(argv):
    line = sys.stdin.readline()
    while line:
        n, w = map(lambda x: int(x), line.split(" ", 2))

        items = []
        for i in range(n):
            weight, value = map(lambda x: int(x), raw_input().split(" ", 2))
            items.append((weight, value))

        items = sorted(items, key=lambda x: x[0])
        print(max_value(items, w))

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Time Limit Exceeded

Solution code:

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

for _ in range(N):
  tmp = input().split()
  w.append(int(tmp[0]))
  v.append(int(tmp[1]))

dp = []

for i in range(W+1):
  dp.append([])
  dp[i] = [0] * (N + 1)
  for j in range(N+1):
    if(j == 0):
      continue
    if(i - w[j-1] >= 0):
      dp[i][j] = max(dp[i][j-1], dp[i-w[j-1]][j-1] + v[j-1], dp[i][j])
    else:
      dp[i][j] = max(dp[i][j-1], dp[i][j])
print(dp[W][N])

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)

from functools import lru_cache

@lru_cache(maxsize = 10000)
def d(i, j):
    if i == 0:
        if w[0] <= j:
            return v[0]
        else:
            return 0
    else:
        if j >= w[i]:
            return max(d(i-1, j), d(i-1, j-w[i]) + v[i])
        else:
            return d(i-1, j)

print(d(N - 1, W))

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)

from functools import lru_cache

@lru_cache(maxsize = 10001)
def d(i, j):
    if i == 0:
        if w[0] <= j:
            return v[0]
        else:
            return 0
    else:
        if j >= w[i]:
            return max(d(i-1, j), d(i-1, j-w[i]) + v[i])
        else:
            return d(i-1, j)



print(d(N - 1, W))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

def max_value(items, space):
    if len(items) == 1:
        if space >= items[0][0]:
            return items[0][1]
        else:
            return 0

    selected = 0
    if space >= items[0][0]:
        selected = items[0][1] + max_value(items[1:], space - items[0][0])
    not_selected = max_value(items[1:], space)

    return max(selected, not_selected)

def main(argv):
    line = sys.stdin.readline()
    while line:
        n, w = map(lambda x: int(x), line.split(" ", 2))

        items = []
        for i in range(n):
            weight, value = map(lambda x: int(x), raw_input().split(" ", 2))
            items.append((weight, value))

        items = sorted(items, key=lambda x: x[0], reverse=True)
        print(max_value(items, w))

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Time Limit Exceeded

Solution code:
N, W = [int(x) for x in input().split()]
item = list()
for i in range(N):
	item.append([int(x) for x in input().split()])

w1 = item[0][0]
class1 = list()
class2 = list()
class3 = list()
class4 = list()
for i in range(N):
		if item[i][0] - w1 == 0:
			class1.append(item[i][1])
		elif item[i][0] - w1 == 1:
			class2.append(item[i][1])
		elif item[i][0] - w1 == 2:
			class3.append(item[i][1])			
		else:
			class4.append(item[i][1])			

class1.sort(reverse=True)
class2.sort(reverse=True)
class3.sort(reverse=True)
class4.sort(reverse=True)			

class1.insert(0, 0)
class2.insert(0, 0)
class3.insert(0, 0)
class4.insert(0, 0)

value = 0
weight = 0
maxvalue = 0

for i in range(len(class1) + 1):
	for j in range(len(class2) + 1):
		for k in range(len(class3) + 1):
			for l in range(len(class4)+ 1):
				for x in range(i):
					value += class1[x]
					if x != 0:
						weight += w1
				for y in range(j):
					value += class2[y]
					if y != 0:
						weight += w1 + 1
				for z in range(k):
					value += class3[z]
					if z != 0:
						weight += w1 + 2
				for w in range(l):
					value += class4[w]
					if w != 0:
						weight += w1 + 3
				if weight > W:
					weight = 0
					value = 0
				elif value > maxvalue:
					maxvalue = value
				weight = 0
				value = 0

print(maxvalue)