Problem:


Knapsack Problem

You have N kinds of 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.

You can select as many items as possible into a knapsack for each kind.

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 8
4 2
5 2
2 1
8 3

Sample Output 1

21

Sample Input 2

2 20
5 9
4 10

Sample Output 2

10

Sample Input 3

3 9
2 1
3 1
5 2

Sample Output 3

27



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


Sample output:
21

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
dp = [0]*(W+1)
for i in range(N):
	a,b = map(int,input().split())
	for j in range(b,W+1,b):
		x = a + dp[j-b]
		if x >= dp[j]:
			dp[j] = x

print(W+1)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
dp = [0]*(W+1)
for i in range(N):
	a,b = map(int,input().split())
	for j in range(b,W+1,b):
		x = a + dp[j-b]
		if x >= dp[j]:
			dp[j] = x

print(dp[W])

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):
	a,b = map(int,input().split())
	for j in range(b,W+1,b):
		x = a + dp[j-b]
		if x >= dp[j]:
			dp[j] = x

print(dp[W])

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):
	a,b = map(int,input().split())
	for j in range(b,W+1,b):
		x = a + dp[j-b]
		if x >= dp[j]:
			dp[j] = x

print(max(dp))

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
goods=[tuple(map(int,input().split())) for _ in range(N)]
goods.sort(key=lambda x:x[0]/x[1],reverse=True)
dp=[0 for w in range(W+1)]
minw=W
for i in range(N):
    if i==0 or (goods[0][0]/goods[0][1]==goods[i][0]/goods[i][1] and minw>goods[i][1]):
        for j in range(W+1):
            dp[j]=goods[i][0]*(j//goods[i][1])
        minw=min(minw,goods[i][1])
        continue
    for w in range(W-minw+1,W+1):
        if w+goods[i][1]>W:continue
        dp[w+goods[i][1]]=max(dp[w+goods[i][1]],dp[w]+goods[i][0])
        minw=min(minw,goods[i][1])
print(dp[W])

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
goods=[tuple(map(int,input().split())) for _ in range(N)]
goods.sort(key=lambda x:x[0]/x[1],reverse=True)
dp=[0 for w in range(W+1)]
minw=W
for i in range(N):
    if i==0 or (goods[0][0]/goods[0][1]==goods[i][0]/goods[i][1] and minw>W%goods[i][1]):
        for j in range(W+1):
            dp[j]=goods[i][0]*(j//goods[i][1])
        minw=W%goods[i][1]
        roop=goods[i][1]
        continue
    for k in range(1+roop):
        weight=minw+roop*k
        if weight%goods[i][1]==0:
            for w in range(W-weight,1+W):
                dp[w]=max(dp[w-goods[i][1]]+goods[i][0],dp[w])
print(dp[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 w == 0:
            continue
        nap[n + 1][w] = max(nap[n][w-(query[n][1] * (w // query[n][1] ))] + query[n][0] *  (w // query[n][1]),nap[n][w])
print(nap[num][weight])

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 w == 0:
            continue
        elif w >= query[n][1]:
            nap[n + 1][w] = max(nap[n+1][w-query[n][1]] + query[n][0] ,nap[n][w-query[n][1]] + query[n][0] ,nap[n][w])
            #nap[n + 1][w] = max(nap[n][w-query[n][1]]nap[n][w-(query[n][1] * (w // query[n][1] ))] + query[n][0] *  (w // query[n][1]),nap[n][w])
print(nap[num][weight])

Submission status: Wrong Answer

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

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

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

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):
	array[i+1]=array[i].copy()
	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=[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):
	array[i+1]=array[i].copy()
	for j in range(W):
		k=1
		while w[i]*k+j<=W:
			array[i+1][w[i]*k+j]=max(array[i+1][w[i]*k+j],array[i][j]+v[i],array[i][w[i]*k+j])
			k+=1


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

Submission status: Wrong Answer

Solution code:
# Knapsack solution
def knapsack(items, capacity):
    items.sort(key = lambda x: x[0] / x[1], reverse=True)
    total_value = 0
    for v, w in items:
        if w > capacity:
            continue
        total_value += v * (capacity // w)
        capacity = capacity % w
        if capacity == 0:
            break
    return total_value

# Acceptance of input
import sys

file_input = sys.stdin

N, W = map(int, file_input.readline().split())

items = [list(map(int, line.split())) for line in file_input]

#Output
ans = knapsack(items, W)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from copy import deepcopy
N, W = tuple(map(int, input().split()))
items = []
for _ in range(N):
    items.append(list(map(int, input().split())))

pre_cost = [0 for _ in range(W+1)]
post_cost = [0 for _ in range(W+1)]
cost = [0 for _ in range(W+1)]

for item in items:
    for w in range(item[1], W+1):
        post_cost[w] = max(pre_cost[w],
                           pre_cost[w-item[1]]+item[0],
                           post_cost[w-item[1]]+item[0])
    pre_cost, post_cost = deepcopy(post_cost), deepcopy(cost)

print(pre_cost[-1])

Submission status: Wrong Answer

Solution code:
def loadItems():
	items = []
	N, maxW = [int(i) for i in input().strip().split()]
	while True:
		item = {}
		item["v"], item["w"] = [int(i) for i in input().strip().split()]
		items.append(item)
		if len(items) == N: break
	return maxW, items

def calc(maxW, items):
	memo = [0]*(maxW+1)
	for item in items:
		for W in range(maxW+1):
			if W + item["w"] <= maxW and (maxW-W) % item["w"] == 0:
				memo[W + item["w"]] = max(memo[W] + item["v"], memo[W + item["w"]])
			else:
				memo[W] = max(memo[W], memo[W-1])

	return memo
maxW, items = loadItems()
print(max(calc(maxW, items)))

Submission status: Wrong Answer

Solution code:
def loadItems():
	items = []
	N, maxW = [int(i) for i in input().strip().split()]
	while True:
		item = {}
		item["v"], item["w"] = [int(i) for i in input().strip().split()]
		items.append(item)
		if len(items) == N: break
	return maxW, items

def calc(maxW, items):
	memo = [0]*(maxW+1)
	for item in items:
		for W in range(maxW+1):
			if W + item["w"] <= maxW and (maxW-W) % item["w"] == 0:
				memo[W + item["w"]] = max(memo[W] + item["v"], memo[W + item["w"]])

	return memo
maxW, items = loadItems()
print(max(calc(maxW, items)))

Submission status: Wrong Answer

Solution code:
def loadItems():
	items = []
	N, maxW = [int(i) for i in input().strip().split()]
	while True:
		item = {}
		item["v"], item["w"] = [int(i) for i in input().strip().split()]
		items.append(item)
		if len(items) == N: break
	return maxW, items

def calc(maxW, items):
	memo = [0]*(maxW+1)
	for item in items:
		for W in range(maxW+1):
			if W + item["w"] <= maxW:
				if (maxW-W) % item["w"] == 0:
					memo[W + item["w"]] = max(memo[W] + item["v"], memo[W + item["w"]])
				else:
					memo[W] = max(memo[W], memo[W-1])

	return memo
maxW, items = loadItems()
print(max(calc(maxW, items)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,w = map(int, input().split())
values = [0]
weights = [0]
counter=0
rest = 0

for i in range(n):
    v,weight = map(int, input().split())
    values.append(v)
    weights.append(weight)

dp=[[0 for i in range(w+1)]for j in range(v+1)]
for i in range(1, n+1):
    for j in range(1, w+1):
        rest = j
        counter = 0
        if(j >= weights[i]):
            while(rest-weights[i]>=0):
                counter = counter+1
                rest = rest - weights[i]
                dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i-1][j-weights[i]*counter]+values[i]*counter)
        else:
            dp[i][j] = dp[i-1][j]
for i in range(n+1):
    print(dp[i])
print(dp[n][-1])

Submission status: Wrong Answer

Solution code:
from collections import namedtuple

if __name__ == '__main__':
    Item = namedtuple('Item', 'v w')
    N, W = map(int, input().split())
    lisItem = [Item(*map(int, input().split())) for _ in range(N)]
    #print(lisItem)
    dp = [[0 for _ in range(W + 1)] for __ in range(N + 1)]
    for i in range(0, N):
        for w in range(W + 1):
            if lisItem[i].w <= w:
                dp[i+1][w] = max(dp[i][w-lisItem[i].w] + lisItem[i].v, dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
    print(dp[N][W])

Submission status: Wrong Answer

Solution code:
N, W = map(int,input().split())
A = []
B = [[0 for j in range(W + 1)]]
for i in range(N):
    A.append(list(map(int, input().split())))
    B.append([0 for j in range(W + 1)])
for i in range(N):
    for j in range(W + 1):
        if j >= A[i][1]:
            B[i + 1][j] = max(B[i][j], B[i][j - A[i][1]] + A[i][0])
print(B[N][W])

Submission status: Time Limit Exceeded

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):
	array[i+1]=array[i].copy()
	for j in range(W):
		k=1
		while w[i]*k+j<=W:
			array[i+1][w[i]*k+j]=max(array[i+1][w[i]*k+j],array[i][j]+v[i]*k,array[i][w[i]*k+j])
			k+=1


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

Submission status: Time Limit Exceeded

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):
		k=0
		while w[i]*k+j<=W:
			array[i+1][w[i]*k+j]=max(array[i+1][w[i]*k+j],array[i][j]+v[i]*k,array[i][w[i]*k+j])
			k+=1


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

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, sv in enumerate(C[:-item_w]):
            V = [v + item_v * j for j, v in enumerate(C[i + item_w::item_w], start=1)]
            C[i] = max(V + [sv])
    print(C[0])

solve()

Submission status: Time Limit Exceeded

Solution code:
def loadItems():
	items = []
	N, maxW = [int(i) for i in input().strip().split()]
	while True:
		item = {}
		item["v"], item["w"] = [int(i) for i in input().strip().split()]
		items.append(item)
		if len(items) == N: break
	return maxW, items

def calc(maxW, items):
	memo = [0]*(maxW+1)

	for item in items:
		for W in range(maxW+1):
			k = 1
			while W + item["w"]*k <= maxW:
				if memo[W] + item["v"]*k > memo[W + item["w"]*k]:
					memo[W + item["w"]*k] = memo[W] + item["v"]*k
				k += 1
	return memo
maxW, items = loadItems()
print(max(calc(maxW, items)))

Submission status: Time Limit Exceeded

Solution code:
# Knapsack Problem
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) for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        v, w = items[i]
        k = 0
        while k * w <= j:
            DP[i+1][j] = max(DP[i+1][j], k*v + DP[i][j-k*w])
            k += 1

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

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int, input().split())
values = [0]
weights = [0]
counter=0
for i in range(n):
    v,weight = map(int, input().split())
    values.append(v)
    weights.append(weight)

for i in range(1,n+1):
    counter=2
    while(w >= weights[i]*counter):
        weights.append(weights[i]*counter)
        values.append(values[i]*counter)
        counter = counter+1

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

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

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

Submission status: Accepted

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

print(max(dp))

Submission status: Accepted

Solution code:
def solve_knapsack(s, n, v, w):
	dp = [[0 for x in range(s+1)] for x in range(n+1)]	
	for i in range(n):
		for j in range(1, s+1):
			if w[i] > j:
				dp[i+1][j] = dp[i][j]
			else:
				dp[i+1][j] = max(dp[i][j], max(dp[i+1][j-w[i]]+v[i], dp[i][j-w[i]]+v[i]))
	return dp[n][s]
	
n, s = map(int, input().split())
v = [0]*n
w = [0]*n
for i in range(n):
	v[i], w[i] = map(int, input().split())
print(solve_knapsack(s, n, v, w))

Submission status: Accepted

Solution code:
# time complexity: O(NW)
# space complexity: O(NW)

import sys
fin = sys.stdin.readline
N, W = [int(elem) for elem in fin().split()]
items = [[int(elem) for elem in fin().split()] for _ in range(N)]


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

for i in reversed(range(N)):
    for j in range(W + 1):
        value, weight = items[i]
        if j < weight:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = max(dp[i + 1][j],
                           dp[i + 1][j - weight] + value,
                           dp[i][j - weight] + value)

print(dp[0][W])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
goods=[tuple(map(int,input().split())) for _ in range(N)]
goods.sort(key=lambda x:x[0]/x[1],reverse=True)
dp=[0 for w in range(W+1)]
minw=W
for i in range(N):
    if i==0 or (goods[0][0]/goods[0][1]==goods[i][0]/goods[i][1] and minw>W%goods[i][1]):
        for j in range(W+1):
            dp[j]=goods[i][0]*(j//goods[i][1])
        minw=W%goods[i][1]
        roop=goods[i][1]
        continue
    for k in range(1+roop):
        weight=minw+roop*k
        if weight>W:
            for w in range(goods[i][1],1+W):
                dp[w]=max(dp[w-goods[i][1]]+goods[i][0],dp[w])
            break
        if weight%goods[i][1]==0:
            for w in range(W-weight,1+W):
                if w-goods[i][1]<0:continue
                dp[w]=max(dp[w-goods[i][1]]+goods[i][0],dp[w])
print(dp[W])

Submission status: Accepted

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,dp[i+1][j-w]+v)
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
value=[]
weight=[]
#suck=[]
for i in range(N):
    v_temp,w_temp=list(map(int,input().split()))
    value.append(v_temp)
    weight.append(w_temp)
#    suck.append(temp)

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

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

Submission status: Accepted

Solution code:
import copy
length, cap = map(int, input().split(" "))
dp = [0] * (cap + 1)
items = []
for _ in range(length):
    a, b = map(int, input().split(" "))
    items.append([a, b])

for item in items:
    v, w = item
    temp_dp = copy.copy(dp)
    temp_dp[w] = max(temp_dp[w], v)
    for j in range(cap):
        if temp_dp[j] and w + j <= cap:
            temp_dp[w + j] = max(temp_dp[w + j], v + temp_dp[j])
    dp = temp_dp
answer = max(dp)
print(answer)

Submission status: Accepted

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

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

print(dp[W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def knappack(N, W, vs, ws):
    dp = [0] * (W + 1)
    for i in range(N):
        for j in range(ws[i], W + 1):
            dp[j] = max(dp[j], dp[j - ws[i]] + vs[i])
            
    return dp[-1]
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    Nstr, Wstr = line.split()
    N, W = int(Nstr), int(Wstr)
    vs, ws = [], []
    for i in range(N):
        line = sys.stdin.readline()
        v, w = line.split()
        v, w = int(v), int(w)
        vs.append(v)
        ws.append(w)
    sys.stdout.write(str(knappack(N, W, vs, ws)))
    sys.stdout.write('\n')

Submission status: Accepted

Solution code:
from sys import stdin
import operator

readline = stdin.readline


n, total_wait = map(int, readline().split())
value_wait = [list(map(int, readline().split())) for _ in range(n)]
value_wait.sort(key=operator.itemgetter(1), reverse=True)

dp = [0] * (total_wait + 1)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#C
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][i-w[j]] + v[j])
        else:
            dp[j][i] = dp[j-1][i]

print(dp[N][W])

Submission status: Accepted

Solution code:
n, w = map(int, raw_input().split())
dp = [0] * (w+1)
for _ in range(n):
    v, tw = map(int, raw_input().split())
    dp[tw] = v
    for i in range(w+1):
        if dp[i] != 0 and i+tw <= w:
            dp[i+tw] = max(dp[i+tw], dp[i] + v)
print max(dp)

Submission status: Accepted

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C
"""
 
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: Accepted

Solution code:
# coding: utf-8

from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from __future__ import absolute_import

def array2d(row, col, init = None):
    return [[init for _ in range(col)] for _ in range(row)]

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

dpt = array2d(N + 1, W + 1)

def dp(i, j):
    if dpt[i][j] is not None:
        return dpt[i][j]
    if i == 0:
        dpt[i][j] = 0
        return 0
    if j < w[i-1]:
        dpt[i][j] = dp(i-1, j)
        return dpt[i][j]
    dpt[i][j] = max(dp(i-1, j), dp(i, j-w[i-1]) + v[i-1])
    return dpt[i][j]

for i in range(N + 1):
    for j in range(W + 1):
        dp(i, j)
print(dp(N, W))

Submission status: Accepted

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

Submission status: Accepted

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):
    for j in range(products[i][1], W + 1):
        product_in = DP[j - products[i][1]] + products[i][0]
        if product_in >= DP[j]:
            DP[j] = product_in
        else:
            DP[j] = DP[j]
print(DP[W])

Submission status: Accepted

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[i], W+1):
        dp[j] = max(dp[j-w[i]] + v[i], dp[j])
print dp[W]

Submission status: Accepted

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

for _ in range(n):
    v, w = map(int, input().split())
    for k in range(cap - w + 1):
        new_v = dp[k] + v
        if dp[k + w] < new_v:
            dp[k + w] = new_v

print(max(dp))

Submission status: Accepted

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

dp = [[0]*(W+1) for i 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] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i], dp[i-1][j-w[i]]+v[i])

print(dp[N][W])

Submission status: Accepted

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)]
query = sorted(query,key = lambda x:x[1],reverse = True)
for n in range(num):
    for w in range(weight + 1):
        if w == 0:
            continue
        elif w >= query[n][1]:
            nap[n + 1][w] = max(nap[n+1][w-query[n][1]] + query[n][0] ,nap[n][w-query[n][1]] + query[n][0] ,nap[n][w])

print(nap[num][weight])

Submission status: Accepted

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

Submission status: Accepted

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

"""
input:
3 9
2 1
3 1
5 2

output:
27
"""

import sys
from collections import namedtuple


def solve():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.value, item.weight
        for cp in range(w, real_cp + 1):
            dp[cp] = max(dp[cp], dp[cp - w] + v)

    return dp[-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[0]*(m+1)
for _ in range(n):
    v,w=map(int,input().split())
    for i in range(w,m+1):dp[i]=max(dp[i],dp[i-w]+v)
print(dp[m])

Submission status: Accepted

Solution code:
# coding: utf-8
"""docstring"""


def arr2d(d1, d2, init=None):
    return [[init for i in range(d2)] for j in range(d1)]


def solve(N, W):
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = map(int, input().split())

    # dp[i][j]: item 0..i ??????weight sum <= j ??¨????????????????????¶????????§????????§???value sum
    # (i: 0..N-1, j: 0..W)
    dp = arr2d(N, W + 1, 0)
    # i==0
    for j in range(0, W + 1):
        dp[0][j] = (j // w[0]) * v[0]
    for i in range(1, N):
        for j in range(0, W + 1):
            dp[i][j] = dp[i-1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])
                dp[i][j] = max(dp[i][j], dp[i][j-w[i]] + v[i])
    return dp[-1][-1]


def main():
    n, w = map(int, input().split())
    print(solve(n, w))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(value[W])

Submission status: Accepted

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

gra = [0]*(W+1)

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

print(max(gra))

Submission status: Accepted

Solution code:
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C, C[item_w:]), start=item_w):
            v1, v2 = vals
            C[i] = max(v1 + item_v, v2)
    print(C[W])

solve()

Submission status: Accepted

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

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

dp = [0] * (W+1)

for i in range(N):
    item_v, item_w = map(int, readline().split())
    for w in range(W-item_w+1):
        if dp[w+item_w] < dp[w] + item_v:
            dp[w+item_w] = dp[w] + item_v

print(max(dp))

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N, W = map(int, input().split())
    items = []
    for _ in range(N):
        v, w = map(int, input().split())
        items.append((v, w))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        v, w = items[i][0], items[i][1]
        for j in range(W + 1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            if j + w < len(dp[0]):
                dp[i][j + w] = max(dp[i][j + w], dp[i][j] + v)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

print(cost[-1])

Submission status: Accepted

Solution code:
INF = 10 ** 12

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

items =[] * N

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

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

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
def solve():
    
    INF = 10 ** 12
    
    N, W = map(int, input().split())
    
    items =[] * N
    
    for i in range(N):
        v, w = map(int, input().split())
        items.append([v,w])
    
    dp = [[INF for i in range(W+1)] for j in range(N+1)]
    
    for i in range(W+1):
        dp[0][i] = 0
    
    for i in range(N+1):
        dp[i][0] = 0
    
    for i in range(1,N+1): #1<= i <= N
        for j in range(1, W+1): # 1 <= j <= W
            if j - items[i-1][1] >= 0:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - items[i-1][1]] + items[i-1][0], dp[i][j - items[i-1][1]] + items[i-1][0])
            else:
                dp[i][j] = dp[i-1][j]
    
    print(dp[N][W])

if __name__ == '__main__':
    solve()