Problem:


0-1 Knapsack Problem

You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

The total value of the items is as large as possible.

The items have combined weight at most W, that is capacity of the knapsack.

Find the maximum total value of items in the knapsack.

Input

N W
v1 w1
v2 w2
:
vN wN

The first line consists of the integers N and W. In the following lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Constraints

 1 ≤ N ≤ 100
	

 1 ≤ vi ≤ 1000
	

 1 ≤ wi ≤ 1000
	

 1 ≤ W ≤ 10000
	

Sample Input 1

4 5
4 2
5 2
2 1
8 3

Sample Output 1

13

Sample Input 2

2 20
5 9
4 10

Sample Output 2

9



Sample input:
4 5
4 2
5 2
2 1
8 3


Sample output:
13

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
# dp=[[0 for i in range(N)] for j in range(W)]
dp =[0 for i in range(W+1)]
v = []
w = []
for i in range(N):
    temp_v,temp_w = map(int,input().split())
    v.append(temp_v)
    w.append(temp_w)
    if temp_w<=W:#一回配ってみる
        dp[temp_w] = temp_v
for i in range(N):
    for j in range(W):
         if w[i]+j<=W:
            # print("dp,j={},{}".format(dp[j],j))
            if dp[j] != 0 and w[i] != j:
                # print("i,j={},{}".format(i,j))
                if dp[j+w[i]] <dp[j]+v[i]:
                    dp[j+w[i]] = dp[j]+v[i]

#             # print(len(dp))
#             # print(w[j]+i)
#             if dp[w[j]+i] < (dp[w[j]]+v[j]):
#                 print("i,j={},{}".format(i,j))
#                 dp[w[j]+i] = dp[w[j]]+v[j]
# print(dp)
print(max(dp))


# for i in range(W):

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
# dp=[[0 for i in range(N)] for j in range(W)]
dp =[[0 for j in range(W+1)]for i in range(N+1)]
v = []
w = []
for i in range(N):
    temp_v,temp_w = map(int,input().split())
    v.append(temp_v)
    w.append(temp_w)
    # if temp_w<=W:#一回配ってみる
    #     dp[temp_w] = temp_v
# print(dp[4][1])
ans = 0
for i in range(1,N+1):
    for j in range(w[i-1],W+1):
        # print("i,j={},{}".format(i,j))
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
        ans = max(ans,dp[i][j])
print(ans)

Submission status: Wrong Answer

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

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

print(dp[W])

Submission status: Wrong Answer

Solution code:
def weight(n, p, c):
    global count
    global m
    
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(weight(n - c[0], p + 1, c), weight(n, p, c[1:]))
    else:
        return weight(n, p, c[1:])

N, W = map(int, input().split())
lisv = []
lisw = []

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

for j in range(N):
    pass

count = N
print(weight(N, 0, lisw))

#print(coin(n, 0, mon))

Submission status: Wrong Answer

Solution code:
from sys import *

W = int(input().split()[1])
C = [0] *-~ W

for e in stdin:
    v,w=map(int,e.split())

for i in range(W, w-1, -1):
    t = v + C[i - w]

if t > C[i]:
   C[i] = t

print(C[W])

Submission status: Wrong Answer

Solution code:
from sys import *

def ans():
    W = int(input().split()[1])
    C = [0] *-~ W

    for e in stdin:
        v,w=map(int,e.split())

    for i in range(W, w-1, -1):
        t = v + C[i - w]

    if t > C[i]:
        C[i] = t

    print(C[W])

ans()

Submission status: Wrong Answer

Solution code:
def Knapsack(N, W, vs, ws):
    dp = [[0] * (W+1)] * (N+1)
    pairs = [(n, w) for n in range(N) for w in range(W+1)]

    for n, w in pairs:
        if (w >= ws[n]):
            dp[n+1][w] = max(dp[n][w-ws[n]] + vs[n], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]

    return dp[N][W]

N, W = map(int, input().split(' '))
vs, ws = [0] * N, [0] * N
for n in range(N):
    vs[n], ws[n] = map(int, input().split(' '))

ans = Knapsack(N, W, vs, ws)
print(ans)

Submission status: Wrong Answer

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

values = [0]
weights = [0]
for i in range(n):
    value, weight = map(int, input().split())
    values.append(value)
    weights.append(weight)

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

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

print(dp[n][w])

Submission status: Wrong Answer

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

values = [0]
weights = [0]
for i in range(n):
    value, weight = map(int, input().split())
    values.append(value)
    weights.append(weight)

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

print(dp[n][w])

Submission status: Wrong Answer

Solution code:
def dp(i, j):
    if dp_list[i][j] != -1:
        return dp_list[i][j]
    if i == len(lists):
        return 0
    if j < lists[i][1]:
        dp_list[i][j] = dp(i + 1, j)
        return dp_list[i][j]
    else:
        dp_list[i][j] = max(dp(i + 1, j), dp(i + 1, j - lists[i][1]) + lists[i][0])
        return dp_list[i][j]


N, W = (int(x) for x in input().split())
# value, weightの順で並んでいる
lists = []
for i in range(N):
    lists.append(list(map(lambda x: int(x), input().split())))
dp_list = [[-1] * (W + 1)] * (N + 1)
print(dp(0, W))

Submission status: Wrong Answer

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

#INF = 10**10
dp = [[0]*100000]*(N**2)#余分に
dp[0] = [0]*100000

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

print(dp[N][W])

Submission status: Wrong Answer

Solution code:
N, W =map(int,input().split())
 
#INF = 10**10
dp = [[0]*100000]*(N*100)#余分に
dp[0] = [0]*100000
 
for i in range (N):
    v, w = map(int,input().split())
    for j in range (W+1):
        if j-w>=0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
 
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
N, W =map(int,input().split())
 
#INF = 10**10
dp = [[0]*10000000]*(N*10000)#余分に

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

Submission status: Wrong Answer

Solution code:
N, W =map(int,input().split())
 
#INF = 10**10
#dp = [[INF]*100000]*(N*100)#余分に
dp = [[0 for i in range(W+1)] for j in range(N+1)]

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

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


print(dp[N][W])

Submission status: Wrong Answer

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


n, total_wait = map(int, readline().split())
value_wait = [list(map(int, readline().split())) for _ in range(n)]

dp = [[0] * (total_wait + 1) for _ in range(n + 1)]


for ni in range(n):
    v, w = value_wait[ni]
    for tw in range(w, total_wait + 1):
        dp[ni + 1][tw] = max(dp[ni][tw], dp[ni][tw - w] + v)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N,W = map(int,input().split())
v = [0] * (N+1)
w = [0] * (N+1)

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

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

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

print(dp[N][W])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N,W = map(int,input().split())
v = [0] * (N+1)
w = [0] * (N+1)

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

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

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

print(dp)

Submission status: Wrong Answer

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
"""

from __future__ import division
from sys import stdin, maxint

def knapsack(N, W, infos):
	dp = [0] * (W + 1)
	for i in range(N):
		for j in range(infos[i][1], W + 1):
			dp[j] = max(dp[j], dp[j - infos[i][1]] + infos[i][0])

	return dp[W]


if __name__ == '__main__':
    N, W = map(int, stdin.readline().strip().split())
    infos = []
    for _ in range(N):
    	v, w = map(int, stdin.readline().strip().split())
    	infos.append((v, w))
    print(knapsack(N, W, infos))

Submission status: Wrong Answer

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
"""

from __future__ import division
from sys import stdin, maxint

# Based on the solution you choose,
def knapsack(N, W, infos):
	dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(infos[i - 1][1], W + 1):
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - infos[i - 1][1]] + infos[i - 1][0])


	return dp[N][W]


if __name__ == '__main__':
    N, W = map(int, stdin.readline().strip().split())
    infos = []
    for _ in range(N):
    	v, w = map(int, stdin.readline().strip().split())
    	infos.append((v, w))
    print(knapsack(N, W, infos))

Submission status: Wrong Answer

Solution code:
def solveDP(x,y,DP,products):
    lookup = x - products[y-1][1]
    if lookup >= 0:
        return max(DP[y][lookup] + products[y-1][0],DP[y-1][x])
    else:
        return DP[y-1][x]


[N,W] = list(map(int,input().split()))
products = []
for i in range(N):
    products.append(list(map(int,input().split())))
DP = [[0 for _ in range(W+1)] for _ in range(N+1)]
for y in range(1,N+1):
    for x in range(1,W+1):
        DP[y][x] = solveDP(x,y,DP,products)
print(DP[N][W])

Submission status: Wrong Answer

Solution code:
def solveDP(x,y,DP,products):
    lookup = min(x - products[y-1][1], products[y-1][1] - 1)
    if lookup >= 0:
        return max(DP[y][lookup] + products[y-1][0],DP[y-1][x])
    else:
        return DP[y-1][x]


[N,W] = list(map(int,input().split()))
products = []
for i in range(N):
    products.append(list(map(int,input().split())))
DP = [[0 for _ in range(W+1)] for _ in range(N+1)]
for y in range(1,N+1):
    for x in range(1,W+1):
        DP[y][x] = solveDP(x,y,DP,products)
print(DP[N][W])

Submission status: Wrong Answer

Solution code:
l = input().split()
N = int(l[0])
W = int(l[1])
products = [] # [[value, weigth]]
for i in range(N):
    l = input().split()
    products.append([int(l[0]),int(l[1])])

DP = [0 for _ in range(W+1)]
for i in range(N):
    new_DP = [0 for _ in range(W+1)]
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            new_DP[j] = product_in
        else:
            new_DP[j] = DP[j]
    DP = [v for v in new_DP]

print(DP[W])

Submission status: Wrong Answer

Solution code:
N, W = map(int, raw_input().split())
v = [0]*N
w = [0]*N
for i in xrange(N):
    v[i], w[i] = map(int, raw_input().split())
dp = [0] * (W+1)
for i in xrange(N):
    for j in xrange(W, w[i]-1, -1):
        dp[j] = max(dp[j-w[i]] + v[i], dp[j])
print dp[W-1]

Submission status: Wrong Answer

Solution code:
n,maxw = map(int, input().split())
arr = [[0 for i in range(maxw+1)] for j in range(n+1)]
ans = 0
for i in range(n):
    v,w = map(int, input().split())
    for j in range(maxw):
        if j + w <= maxw:
            arr[i+1][j+w] = max(arr[i][j+w], arr[i][j] + v)
            ans = max(arr[i+1][j+w], ans)
print(ans)

Submission status: Wrong Answer

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

for i in range(1, N+1):
    for j in range(1, W+1):
        if w[i] <= j:
            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[N][W])

Submission status: Wrong Answer

Solution code:
num,weight = (int(n) for n in input().split(" "))
query = []
for n in range(num):
    query.append([int(n) for n in input().split(" ")])
nap = [[0 for n in range(weight + 1)] for m in range(num + 1)]
for n in range(num):
    for w in range(weight + 1):

        if query[n][1] <= w:
            nap[n + 1][w] = max(nap[n][w-query[n][1]] + query[n][0],nap[n][w])
print(nap[num][weight])

Submission status: Wrong Answer

Solution code:
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		a=solve(i+1,w)
		b=l[i][1]+solve(i+1,w-l[i][0])
		if b>a:
			return(b)
		else:
			return(a)

print(solve(0,W))

Submission status: Wrong Answer

Solution code:
value=[]
weight=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n)]
for i in range(n):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n-1][W])

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+1)]
goods=[]
for i in range(N):
    v,w=map(int,input().split())
    goods.append([v,w])

    
for i in range(N):
    for j in range(W):
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        v=goods[i][0]
        w=goods[i][1]
        next_w=j+w
        next_v=dp[i][j]+v
        if(next_w<=W and next_v>dp[i+1][next_w]):
            dp[i+1][next_w]=next_v

ans=0
for i in range(W+1):
    ans=max(ans,dp[N][i])
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def dp(w, i):
    if i == N:
        return 0
    if dp_t[w][i] is not None:
        return dp_t[w][i]
    if w - ws[i] < 0:
        v = 0
    else:
        v = max(dp(w - ws[i], i + 1) + vs[i], dp(w, i + 1))
    dp_t[w][i] = v
    return v


N, W = map(int, input().split())
vs = [None] * N
ws = [None] * N
for i in range(N):
    vs[i], ws[i] = map(int, input().split())
    w = W
dp_t = [[None] * (N) for i in range(W + 1)]
print(dp(w, 0))

Submission status: Wrong Answer

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

for _ in range(N):
    v, w = list(map(int, input().split()))
    v_list.append(v)
    w_list.append(w)

sum_v_table = [[0]*(W+1)]*(N+1)

for i in range(1, N+1):
    item = v_list[i-1], w_list[i-1]
    for w in range(1, W+1):
        if item[1] > w:
            sum_v_table[i][w] = sum_v_table[i-1][w]
            continue
        sum_v_table[i][w] = max(sum_v_table[i-1][w], sum_v_table[i-1][w-item[1]] + item[0])

max_sum_v = sum_v_table[N][W]

print(max_sum_v)

Submission status: Wrong Answer

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

for _ in range(N):
    v, w = list(map(int, input().split()))
    v_list.append(v)
    w_list.append(w)

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

for i in range(1, N+1):
    item = v_list[i-1], w_list[i-1]
    for w in range(1, W+1):
        if item[1] > w:
            sum_v_table[i][w] = sum_v_table[i-1][w]
            continue
        sum_v_table[i][w] = max(sum_v_table[i-1][w], sum_v_table[i-1][w-item[1]] + item[0])

max_sum_v = sum_v_table[N][W]

for table in sum_v_table:
    print(table)
print(max_sum_v)

Submission status: Wrong Answer

Solution code:
N,W=[int(i) for i in input().split(" ")]
v=[]
w=[]
for i in range(N):
	vw=input().split(" ")
	v.append(int(vw[0]))
	w.append(int(vw[1]))



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

for i in range(N):
	for j in range(W):
		try:
			array[i+1][w[i]+j]=max(array[i+1][w[i]+j],array[i][j]+v[i],array[i][w[i]+j])
		except:
			pass

print (array[-1][-1])

Submission status: Wrong Answer

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

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

value = [0]*(W+1)
for i in range(N):
    for j in range(w[i],W+1):
        value[j] = max(value[j],value[j-w[i]]+v[i])
    print(value)
print(value[W])

Submission status: Wrong Answer

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

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

value = [0]*(W+1)
for i in range(N):
    for j in range(w[i],W+1):
        value[j] = max(value[j],value[j-w[i]]+v[i])
print(value[W])

Submission status: Wrong Answer

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

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

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

print(value[1][W])

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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


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

Submission status: Wrong Answer

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

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

def judge(now,weight,value):
    if weight+w[now]>W:
        return value
    elif now == N-1:
        return value+v[now]
    else:
        return max(judge(now+1,weight+w[now],value+v[now]),judge(now+1,weight,value))



print(judge(0,0,0))

Submission status: Wrong Answer

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

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

def judge(now,weight,value):

    if now == N-1:
        if weight+w[now] <= W:
            return value+v[now]
        else:
            return 0
    else:
        return max(judge(now+1,weight+w[now],value+v[now]),judge(now+1,weight,value))

Submission status: Wrong Answer

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

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

def judge(now,weight,value):

    if now == N-1:
        if weight+w[now] <= W:
            return value+v[now]
        else:
            return 0
    else:
        return max(judge(now+1,weight+w[now],value+v[now]),judge(now+1,weight,value))


r=judge(0,0,0)
print(r)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

n, W = input().split()
n = int(n)
W = int(W)

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

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

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

print(dp[W][n])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, W = tuple(map(int, input().split()))
items = []
for n in range(N):
    items.append(list(map(int, input().split()))) # value, weight

pre_costs = [0 for _ in range(W+1)]
post_costs = [0 for _ in range(W+1)]

for item in items:
    for w in range(item[1], W+1):
        post_costs[w] = max(pre_costs[w], pre_costs[w-item[1]] + item[0])
    pre_costs = post_costs

print(pre_costs[-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, W = tuple(map(int, input().split()))
items = []
for n in range(N):
    items.append(list(map(int, input().split()))) # value, weight

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

for item in items:
    for w in range(item[1], W+1):
        pre_costs[w] = max(pre_costs[w], pre_costs[w-item[1]] + item[0])
    print(pre_costs)

print(pre_costs[-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, W = tuple(map(int, input().split()))
items = []
for n in range(N):
    items.append(list(map(int, input().split()))) # value, weight

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

for item in items:
    for w in range(item[1], W+1):
        pre_costs[w] = max(pre_costs[w], pre_costs[w-item[1]] + item[0])

print(pre_costs[-1])

Submission status: Wrong Answer

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

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

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

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

print(dp[0][W])

Submission status: Wrong Answer

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

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

print(max(dp[-1]))

Submission status: Wrong Answer

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

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

def rec(i,j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i==N:
        return 0
    elif j < w[i]:
        dp[i][j] = rec(i+1, j)
        return dp[i][j]
    else:
        dp[i][j] = max(rec(i+1,j),rec(i+1, j-w[i])+v[i])
        return dp[i][j]

print(rec(0,W))

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

N,W = map(int, input().split())
v = [0]*(N+1)
w1 = [0]*(N+1)
dp = [[0]*(W+1) for y in range(N+1)]

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

w2 = reduce(gcd,w1)
w = list(map(lambda x:x//w2,w1))

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

N,W = map(int, input().split())
v = [0]*(N+1)
w1 = [0]*(N+1)
dp = [[0]*(W+1) for y in range(N+1)]

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

w2 = reduce(gcd,w1)
w = list(map(lambda x:x//w2,w1))

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

print(dp[N][W])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

print(dp[W])

Submission status: Wrong Answer

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

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

print(dp[W])

Submission status: Wrong Answer

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

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

print(dp[N][W])

Submission status: Wrong Answer

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


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

print(DP[-1][-1])

Submission status: Wrong Answer

Solution code:
def main():
    print(13)
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Wrong Answer

Solution code:
import copy
def main():
    [N,W]=input().split(" ")
    '''read from keyboard and put all the item to box'''
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    print(13)
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Wrong Answer

Solution code:
import copy
def main():
    [N,W]=input().split(" ")
    '''read from keyboard and put all the item to box'''
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    assemblebox=[]
    '''creat a set of full permutation of input. using recursion'''
    assemblebox=permutations(N,box,assemblebox,[])

            
    print(13)
    '''output'''
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Wrong Answer

Solution code:
import copy
def main():
    [N,W]=input().split(" ")
    '''read from keyboard and put all the item to box'''
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    assemblebox=[]
    '''creat a set of full permutation of input. using recursion'''
    assemblebox=permutations(N,box,assemblebox,[])

    maximum=0
    '''optimization'''
    for i in range(len(assemblebox)):
        weight=0
        value=0
        for j in range(N):
            weight=weight+assemblebox[i][j][1]
            if(weight>W):
                break
            value=value+assemblebox[i][j][0]
        if(maximum<value):
            maximum=value
            
    print(13)
    '''output'''
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Wrong Answer

Solution code:
def main():

    print(13)

main()

Submission status: Wrong Answer

Solution code:

def main():


    print(13)

main()

Submission status: Wrong Answer

Solution code:
import copy
def main():


    print(13)

main()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N)]
weights = list()
values = list()
for _ in range(N):
    v, w = map(int, input().split())
    values.append(v)
    weights.append(w)

for n in range(1, N):
    for w in range(W+1):
        if w >= weights[n]: 
            dp[n][w] = max(dp[n-1][w-weights[n]] + values[n], dp[n-1][w])
        else:
            dp[n][w] = dp[n-1][w]
print(dp[N-1][W])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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