Problem:


Score : 100 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

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

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

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

Sample Input 2

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

Sample Output 2

5000000000

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

Sample Input 3

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

Sample Output 3

17

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



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
wv.sort(key=lambda x:x[0])
wv.sort(key=lambda x:-x[1])
weight=0
value=0
for i in range(n):
    if weight+wv[i][0] <= w:
        weight+=wv[i][0]
        value+=wv[i][1]

print(value)

Submission status: Wrong Answer

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

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

print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
weighs,values = [],[]
for i in range(n):
    wa,va = map(int,input().split())
    weighs.append(wa)
    values.append(va)

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

for i in range(w+1):
    maxa = 0
    useda = [0 for i in range(n)]
    for k in range(n):
        if used[i-weighs[k]][k] == 0 and i-weighs[k] >= 0 and dp[i-weighs[k]]+values[k]>maxa:
                maxa = dp[i-weighs[k]]+values[k]
                useda = used[i-weighs[k]][:]
                useda[k] = 1
    dp[i] = maxa
    used[i] = useda

#print(used)
print(dp[w])

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
weighs,values = [],[]
for i in range(n):
    wa,va = map(int,input().split())
    weighs.append(wa)
    values.append(va)

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

for i in range(w+1):
    maxa = 0
    useda = [0 for i in range(n)]
    for k in range(n):
        if used[i-weighs[k]][k] == 0:
            if i-weighs[k] >= 0 and dp[i-weighs[k]]+values[k]>maxa:
                maxa = dp[i-weighs[k]]+values[k]
                useda = used[i-weighs[k]][:]
                useda[k] = 1
    dp[i] = maxa
    used[i] = useda

#print(used)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
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 = np.zeros((N+1, W+1))
print(dp)
for i in range(N):
	for sum_w in range(W+1):
		if sum_w < w[i]:
			dp[i+1, sum_w] = dp[i, sum_w]
		else:
			dp[i+1, sum_w] = np.maximum(dp[i, sum_w], dp[i, sum_w-w[i]]+v[i])
print(int(dp[N, W]))

Submission status: Wrong Answer

Solution code:
import numpy as np
n, wt = map(int, input().split())
 
d = np.full(n*1000+1,wt+1, 'i8')
d[0] = 0
for _ in range(n):
  w, v = map(int, input().split())
  d[v:] = np.minimum(d[v:], d[:-v]+w)
print(np.max(np.where(d<=wt)))

Submission status: Wrong Answer

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

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


mod=10**9+7

T=[1]
for a in A:
	W=[0]		#WA:累積和
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append( x%mod )
		else:	W.append( (W[-1]+x)%mod )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0

Submission status: Wrong Answer

Solution code:
import numpy as np

n,l=map(int,input().split())
l_all=np.zeros(l+1,dtype=int)

for _ in range(n):
  w,v=map(int,input().split())
  l_all[w:]=np.maximum(l_all[w:],l_all[:-w]+v)
  
print(l_all[l-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,W=map(int,input().split())
k=[]
for i in range(n):
    w,v=map(int,stdin.readline().split())
    k.append((w,v,w/v))
k.sort(key=lambda tup: tup[2])
c=0
i=0
while W>0 and i<n:
    if W-k[i][0]>=0:
        c+=k[i][1]
        W-=k[i][0]
    i+=1
print(c)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n,W=map(int,input().split())
k=[]
for i in range(n):
    w,v=map(int,stdin.readline().split())
    k.append((w,v,v/w))
k.sort(key=lambda tup: tup[2])
c=0
i=0
while W>0 and i<n:
    if W-k[i][0]>=0:
        c+=k[i][1]
        W-=k[i][0]
    i+=1
print(c)

Submission status: Wrong Answer

Solution code:
def solve(n, w, items):
    dp = [[0] * (w + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        prev = i - 1
        weight, value = items[i - 1][0], items[i - 1][1]
        for j in range(1, w + 1):
            dp[i][j] = max(dp[i][j], dp[prev][j])
            if j - weight >= 0:
                dp[i][j] = max(dp[prev][j], dp[i][j - weight] + value)
    return max(dp[n])

def main():
    n, w = map(int, input().split())
    items = []
    for i in range(n):
        items.append(list(map(int, input().split())))
    ans = solve(n, w, items)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def solve(n, w, items):
    dp = [[0] * (w + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        prev = i - 1
        weight, value = items[i - 1][0], items[i - 1][1]
        for j in range(1, w + 1):
            dp[i][j] = max(dp[i][j], dp[prev][j])
            if j - weight >= 0:
                dp[i][j] = max(dp[prev][j], dp[i][j - weight] + value)
    return dp[n][w]

def main():
    n, w = map(int, input().split())
    items = []
    for i in range(n):
        items.append(list(map(int, input().split())))
    ans = solve(n, w, items)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def solve(n, w, items):
    dp = [[0] * (w + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, w + 1):
            prev = i - 1
            dp[i][j] = max(dp[i][j], dp[prev][j])
            weight, value = items[i - 1][0], items[i - 1][1]
            if j - weight >= 0:
                dp[i][j] = max(dp[i][j], dp[i][j - weight] + value)
    return dp[n][w]

def main():
    n, w = map(int, input().split())
    items = []
    for i in range(n):
        items.append(list(map(int, input().split())))
    ans = solve(n, w, items)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
class Solution(object):
    def knapsack1(self, w, vals):
        vals.insert(0, [0,0])
        # vals = sorted(vals, key=lambda x: x[0])
        dp = [[0 for _ in range(w+1)] for _ in range(len(vals))]

        for i in range(1, len(vals)):
            for j in range(1, w+1):

                curr_w, curr_v = vals[i]
                # print(i, j, curr_w, curr_v)
                if curr_w <= j:
                    # print('in 1')
                    dp[i][j] = max(dp[i-1][j], curr_v + dp[i-1][j-curr_w])
                else:
                    # print('in 2')
                    dp[i][j] = max(dp[i][j], dp[i-1][j])

        # print(dp)
        print(dp[-1][-1])











if __name__ == '__main__':
    n, w = map(int, input().strip().split())
    vals = []
    for i in range(n):
        vals.append(list(map(int, input().strip().split())))
    sol = Solution()
    res = sol.knapsack1(w, vals)
    print(res)

Submission status: Wrong Answer

Solution code:
class Solution(object):
    def knapsack1(self, w, vals):
        vals.append([0,0])
        vals = sorted(vals, key=lambda x: x[0])
        dp = [[0 for _ in range(w+1)] for _ in range(len(vals))]

        for i in range(1, len(vals)):
            for j in range(1, w+1):

                curr_w, curr_v = vals[i]
                # print(i, j, curr_w, curr_v)
                if curr_w <= j:
                    # print('in 1')
                    dp[i][j] = curr_v + dp[i-1][j-curr_w]
                else:
                    # print('in 2')
                    dp[i][j] = dp[i-1][j]

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











if __name__ == '__main__':
    n, w = map(int, input().strip().split())
    vals = []
    for i in range(n):
        vals.append(list(map(int, input().strip().split())))
    sol = Solution()
    res = sol.knapsack1(w, vals)
    print(res)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


def solve():
    MaxV = 10**3*N+1
    dp = [[float('inf')]*MaxV for _ in range(N+1)]
    dp[0][0] = 0

    for i in range(1, N+1):
        for v in range(MaxV):
            if items[i-1][1] <= v:
                dp[i][v] = min(dp[i-1][v], dp[i-1]
                               [v-items[i-1][1]]+items[i-1][0])
            else:
                dp[i][v] = dp[i-1][v]
    ans = 0
    for i, v in enumerate(dp[N]):
        if v <= W:
            ans = i

    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin
n, w =  [int(x) for x in stdin.readline().rstrip().split()]
item = []
for i in range(n):
    item.append([int(x) for x in stdin.readline().rstrip().split()])
dp = [[0] * (w + 1) for i in range(n + 1)]
lw = 0
for i in range(1, n + 1):
    for maxw in range(w + 1):
        inw = maxw + item[i - 1][0]
        if inw <= w:
            dp[i][inw] = max(dp[i - 1][inw], dp[i - 1][maxw] + item[i - 1][1])
print(dp[n][w])

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


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

    # init
    # update
    for i in range(1, N+1):
        for w in range(W+1):
            if w-items[i-1][0] >= 0:
                dp[i][w] = max(dp[i-1][w], dp[i-1]
                               [w-items[i-1][0]]+items[i-1][1])
            else:
                dp[i][w] = dp[i-1][w]

    print(max(dp[N]))


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


solve2()

Submission status: Wrong Answer

Solution code:
import numpy as np
IN = lambda:map(int, input().split())
 
n,k = IN()
dp = np.full(n*1000+1, k+1, dtype=int)
dp[0] = 0
 
for _ in range(n):
    w,v = IN()
    dp[v:] = np.minimum(dp[:-v]+w, dp[v:])
print(np.max(np.where(dp <= k)))

Submission status: Wrong Answer

Solution code:
import numpy as np
n,w = map(int, input().split())
 
items = list(map(int, input().split()) for _ in [0]*n)
dp = np.zeros(w+1, dtype='int64')
 
for weight, value in items:
    print(np.maximum(dp[weight:], dp[:w-weight+1] + value))
    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)
print(dp.max())

Submission status: Wrong Answer

Solution code:
import numpy as np
n,w = map(int, input().split())

items = list(map(int, input().split()) for _ in range(n))
dp = np.zeros(w+1, dtype='int32')

for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)
print(dp.max())

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(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):
    for sum_w in range(1, W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

for n in dp:
    print(n)
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
#vvww=[0]*N
vw=[0]*N
weight=0
value=0
maew=0
maev=0

for i in range(0,N):
  a,b=map(int,input().split())
  vw[i]=[b,a]
    
#print(vw)
vw.sort(reverse=True)
#print(vw)

for aa,bb in vw:
  if weight+bb<=W:
    value+=aa
    weight+=bb
    maew=bb
    maev=aa
    #print(aa,bb)
  elif aa==maev and maew>bb:
    weight=weight-maew+bb
    
print(value)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
vvww=[0]*N
vw=[0]*N
weight=0
value=0

for i in range(0,N):
  a,b=map(int,input().split())
  vvww[i]=[a,b]
vvww.sort()
for i in range(0,N):
  vw[i]=[vvww[i][1],vvww[i][0]]
    
#print(vw)
vw.sort(reverse=True)
#print(vw)

for aa,bb in vw:
  if weight+bb<=W:
    value+=aa
    weight+=bb
    #print(aa,bb)
print(value)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
vw=[0]*N
weight=0
value=0

for i in range(0,N):
  b,a=map(int,input().split())
  vw[i]=[a,b]
  
#print(vw)
vw.sort(reverse=True)
#print(vw)

for aa,bb in vw:
  if weight+bb<=W:
    value+=aa
    weight+=bb
    #print(aa,bb)
print(value)

Submission status: Wrong Answer

Solution code:
n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

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

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

print(max(dp[0]))

Submission status: Wrong Answer

Solution code:
n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

dp=[[float('-inf') for i in range(k+1)] for j in range(n+1)]

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

print(dp[0][-1])

Submission status: Wrong Answer

Solution code:
n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

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

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

print(dp[0][-1])

Submission status: Wrong Answer

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

#weight DP
wdp = [0 for i in range(W+1)]

for i in range(N):
    update = [i for i in range(W) if wdp[i]>0]
    weight = wv[i][0]
    value = wv[i][1]
    
    # 0 
    if weight <= W:
        wdp[weight] = max(wdp[weight],value)
    
    #update
    for j in update:
        if weight + j <= W:
            wdp[weight+j] = max(wdp[weight+j],wdp[j]+value)

print(max(wdp))

Submission status: Wrong Answer

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

#weight DP
wdp = [0 for i in range(W+1)]

for i in range(N):
    update = [i for i in range(W) if wdp[i]>0]
    weight = wv[i][0]
    value = wv[i][1]
    
    # 0 
    wdp[weight] = max(wdp[weight],value)
    
    #update
    for j in update:
        if weight + j <= W:
            wdp[weight+j] = max(wdp[weight+j],wdp[j]+value)

print(max(wdp))

Submission status: Wrong Answer

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

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

def calc(clw,clv,cw,cv):
    for i,val in enumerate(clw):
        if cw-val<0:
            continue
        return calc(clw[:i]+clw[i+1:],clv[:i]+clv[i+1:],cw-val,cv+clv[i])
    return cv

grs = []
for i,val in enumerate(lw):
    if W-val<0:
        continue
    grs.append(calc(lw[:i]+lw[i+1:],lv[:i]+lv[i+1:],W-val,lv[i]))

print(max(grs))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
n1=n
n=m
m=n1 
mat=[0]*(n+1)
for i in range(m):
      s,w=map(int,input().split())
      for j in range(n-1, 0, -1):
            if s <= j+1:
                  mat[j+1]=(max(mat[j+1],w+mat[j+1-s]))
print(mat[n])

Submission status: Wrong Answer

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)

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
	#i番目の品物
	for sum_w in range(W+1):
		#入れるとき
		if sum_w - w[i] >=0:
			dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
		else:
			dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])

Submission status: Wrong Answer

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)

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

Submission status: Wrong Answer

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)

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

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

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

Submission status: Wrong Answer

Solution code:
n, we = map(int, input().split())

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in input().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c
    if best<dp[lim+w]: best=dp[lim+w]


print(best)

Submission status: Wrong Answer

Solution code:
n, we = map(int, input().split())

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in input().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c
    print(dp)
    if best<dp[lim+w]: best=dp[lim+w]


print(best)

Submission status: Wrong Answer

Solution code:
n, we = map(int, input().split())

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in input().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt+w, we)
    for j in range(lim, w-1, -1):
        if dp[j]<(dp[j-w] + c) : dp[j]=dp[j-w] + c
    # print(dp)
    if best<dp[lim]: best=dp[lim] 


print(best)

Submission status: Wrong Answer

Solution code:
import sys
 
n, we = map(int, input().split())
 
cf=[(0, 0)]*n
 
cf = sorted(tuple( int(x) for x in input().split()) for _ in range(n))
 
dp=[0]*(we+1)
 
best=0
cnt=1
lim=0
 
for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we)
    for j in range(lim, w-1, -1):
        if dp[j]<(dp[j-w] + c) : dp[j]=dp[j-w] + c
    if best<dp[lim]: best=dp[lim] 
 
 
print(best)

Submission status: Wrong Answer

Solution code:
import sys

n, we = map(int, input().split())

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in input().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we)
    for j in range(lim, w-1, -1):
        if dp[j]<(dp[j-w] + c) : dp[j]=dp[j-w] + c
    print(dp)
    if best<dp[lim]: best=dp[lim] 


print(best)

Submission status: Wrong Answer

Solution code:
import sys

n, we = map(int, input().split())

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in input().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we)
    for j in range(lim, w, -1):
        if dp[j]<(dp[j-w] + c) : dp[j]=dp[j-w] + c
    print(dp)
    if best<dp[lim]: best=dp[lim] 


print(best)

Submission status: Wrong Answer

Solution code:
import numpy as np 

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

w_all = np.zeros(W + 1, dtype=int)

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

print(w_all[W - 1])

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W = map(int,input().split())
dp=np.zeros(W+1,dtype="int32")
for i in range(N):
	w,v = map(int,input().split())

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W = map(int,input().split())
dp=np.zeros(W+1,dtype="int64")
for i in range(N):
	w,v = map(int,input().split())

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
N, W = [int(_) for _ in input().split()]
WV = [[int(_) for _ in input().split()] for _ in range(N)]
dp = {}
dp[0] = 0
for w, v in WV:
    for k in dp.copy():
        if k + w <= W:
            dp[k + w] = max(dp.get(k + w, 0), dp[k] + v)
print(max([v for k, v in dp.items()]))

Submission status: Wrong Answer

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

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

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

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

def maxvalue_dp(N, W, ws, vs):
    import numpy as np
    dp = np.zeros(W + 1, 'int32')
    ws = np.array(ws, 'int32')
    vs = np.array(vs, 'int32')
    for i in range(N):
        idx = np.arange(W + 1) - ws[i]
        dp = np.maximum(dp, (dp[idx] + vs[i]) * (idx >= 0))
    return dp[-1]

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())
it = iter(map(int, open(0).read().split()))
dp = np.zeros(W + 1, dtype=int)
for w, v in zip(it, it):
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

a = []
b = []

for _ in range(n):
    x, y = map(int, input().split())

    a.append(x)
    b.append(y)

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

for i in range(n+1):
    for j in range(w + 1):
        if i == 0 or j == 0: t[i][j] = 0
        elif b[i-1] <= j: t[i][j] = max(a[i-1] + t[i-1][j - b[i-1]], t[i-1][j])
        else: t[i][j] = t[i-1][j]

print(t[n][w])

Submission status: Wrong Answer

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

dp = [[None]*(W+1) for i in range(N+1)]
dp[0][0] = 0
sumw = ans = 0
for i in range(1,N+1):
    w,v = src[i-1]
    sumw += w
    for j in range(min(W,sumw)+1):
        if dp[i-1][j] is None: continue
        v0 = 0 if dp[i][j] is None else dp[i][j]
        dp[i][j] = max(v0, dp[i-1][j])
        if j+w > W: break
        v1 = 0 if dp[i][j+w] is None else dp[i][j+w]
        dp[i][j+w] = max(v1, dp[i-1][j] + v)
        ans = max(ans, dp[i][j+w])
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, raw_input().split())
obj = []
for i in xrange(N):
    w, v = map(int, raw_input().split())
    obj.append((w, v))
dp = [[-1 for _ in xrange(W+1)] for i in xrange(N)]

dp[0][0] = 0
dp[0][obj[0][0]] = obj[0][1]

for i in xrange(1, N):
    w, v = obj[i]
    for j in xrange(W+1):
        if dp[i-1][j] != -1:
            dp[i][j] = dp[i-1][j]
    for j in xrange(W+1):
        if dp[i-1][j] != -1 and j + w <= W:
            dp[i][j+w] = max(dp[i][j]+v, dp[i][j+w])
res = 0
for i in xrange(W+1):
    res = max(dp[N-1][i], res)
print res

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
 
N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))
 
dp = defaultdict(int)
 
dp[0] = 0
 
for v,w in WV:
    for nw, nv in list(dp.items()):
        if nw+w <= W:
            dp[nw+w] = max(dp[nw+w], nv+v)
            
print(max(dp.values()))

Submission status: Time Limit Exceeded

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

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

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

for i in range(n):
    for sum_w in range(w + 1):
        if sum_w - wv[i][0] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(dp[n][w])

Submission status: Time Limit Exceeded

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

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

for i in range(n):
    for sum_w in range(w + 1):
        if sum_w - wv[i][0] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print(max(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

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

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

    print(dp[-1][-1])
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,W = [int(c) for c in input().split()]
wv = [[int(c) for c in input().split()] for d in range(N)]

dp = [[0]*(W+1) for c in range(N)]
#i番目の品物まで候補としたとき(使うかはわからない)、重さj以下のときの価値の総量がdp[i][j]
for i in range(N):
    for j in range(W+1):
        #重さj以下で、iを使うときと使わないときの大きい方
        if j-wv[i][0] >= 0:
            dp[i][j] = max([dp[i-1][j-wv[i][0]]+wv[i][1],dp[i-1][j]])
        else:
            dp[i][j] = dp[i-1][j]

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

Submission status: Time Limit Exceeded

Solution code:
def knapsack(wt, val, W, n,t):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max( 
val[n-1] + knapsack( 
wt, val, W-wt[n-1], n-1,t),  
knapsack(wt, val, W, n-1,t)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1,t) 
        return t[n][W] 
n,w=map(int,input().split())
v,wt=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    v.append(b)
    wt.append(a)
t = [[-1 for i in range(w + 1)] for j in range(n + 1)]
print(knapsack(wt, v, w, n,t))

Submission status: Time Limit Exceeded

Solution code:
def knap(v,wt,n,w,dp):
    if n<0:
        return 0
    if dp[n][w]!=-1:
        return dp[n][w]
    if wt[n]>w:
        dp[n][w]= knap(v,wt,n-1,w,dp)
        return dp[n][w]
    else:
        dp[n][w]= max(v[n]+knap(v,wt,n-1,w-wt[n],dp),knap(v,wt,n-1,w,dp))
        return dp[n][w]
n,w=map(int,input().split())
v,wt=[],[]
for _ in range(n):
    a,b=map(int,input().split())
    v.append(b)
    wt.append(a)
dp=[]
for i in range(n+1):
    temp=[-1]*(w+1)
    dp.append(temp)
ans=knap(v,wt,n-1,w,dp)
print(ans)