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:
import random
import copy

def get_population():
    population = []
    for i in range(individual_length):
        population.append([random.randint(0,1) for j in range(gene_length)])
    return population

def evaluate(pop):
    pop.sort(reverse=True)
    return pop

def two_point_crossover(parent1, parent2):
    r1 = random.randint(0, gene_length-1)
    r2 = random.randint(r1, gene_length-1)
    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]
    return child

def mutate(parent):
    r = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent)
    child[r] = 1 if child[r]==0 else 0
    return child

def fitness(pop):
    value = 0
    weoght = 0
    for i in range(N):
        if pop[i]:
            value += L[i][1]
            weoght += L[i][0]
    if weoght <= W:
        return value
    else:
        return 0

N,W = [int(zz) for zz in input().split()]
L = [[0,0] for _ in range(N)]

for i in range(N):
    p,q = [int(zz) for zz in input().split()]
    L[i][0] = p
    L[i][1] = q

gene_length = N # 遺伝子長
individual_length = 50 # 個体数
generation = 500 # 世代数
mutate_rate = 0 # 突然変異の確率
elite_rate = 0.1 # エリート選択の割合

pop = evaluate([(fitness(p), p) for p in get_population()])

for i_episode in range(generation):

    eva = evaluate(pop)
    elites = eva[:int(len(pop)*elite_rate)]

    pop = elites
    while len(pop) < individual_length:
        if random.random() < mutate_rate:
            m = random.randint(0, len(elites)-1)
            child = mutate(elites[m][1])
        else:
            m1 = random.randint(0, len(elites)-1)
            m2 = random.randint(0, len(elites)-1)
            child = two_point_crossover(elites[m1][1], elites[m2][1])
        pop.append((fitness(child), child))

eva = evaluate(pop)
print(pop[0][0])

Submission status: Wrong Answer

Solution code:
import random
import copy

def get_population():
    population = []
    for i in range(individual_length):
        population.append([random.randint(0,1) for j in range(gene_length)])
    return population

def evaluate(pop):
    pop.sort(reverse=True)
    return pop

def two_point_crossover(parent1, parent2):
    r1 = random.randint(0, gene_length-1)
    r2 = random.randint(r1, gene_length-1)
    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]
    return child

def mutate(parent):
    r = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent)
    child[r] = 1 if child[r]==0 else 0
    return child

def fitness(pop):
    value = 0
    weoght = 0
    for i in range(N):
        if pop[i]:
            value += L[i][1]
            weoght += L[i][0]
    if weoght <= W:
        return value
    else:
        return 0

N,W = [int(zz) for zz in input().split()]
L = [[0,0] for _ in range(N)]

for i in range(N):
    p,q = [int(zz) for zz in input().split()]
    L[i][0] = p
    L[i][1] = q

gene_length = N # 遺伝子長
individual_length = 50 # 個体数
generation = 500 # 世代数
mutate_rate = 0 # 突然変異の確率
elite_rate = 0.2 # エリート選択の割合

pop = evaluate([(fitness(p), p) for p in get_population()])

for i_episode in range(generation):

    eva = evaluate(pop)
    elites = eva[:int(len(pop)*elite_rate)]

    pop = elites
    while len(pop) < individual_length:
        if random.random() < mutate_rate:
            m = random.randint(0, len(elites)-1)
            child = mutate(elites[m][1])
        else:
            m1 = random.randint(0, len(elites)-1)
            m2 = random.randint(0, len(elites)-1)
            child = two_point_crossover(elites[m1][1], elites[m2][1])
        pop.append((fitness(child), child))

eva = evaluate(pop)
print(pop[0][0])

Submission status: Wrong Answer

Solution code:
import random
import copy

def get_population():
    population = []
    for i in range(individual_length):
        population.append([random.randint(0,1) for j in range(gene_length)])
    return population

def evaluate(pop):
    pop.sort(reverse=True)
    return pop

def two_point_crossover(parent1, parent2):
    r1 = random.randint(0, gene_length-1)
    r2 = random.randint(r1, gene_length-1)
    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]
    return child

def mutate(parent):
    r = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent)
    child[r] = 1 if child[r]==0 else 0
    return child

def fitness(pop):
    value = 0
    weoght = 0
    for i in range(N):
        if pop[i]:
            value += L[i][1]
            weoght += L[i][0]
    if weoght <= W:
        return value
    else:
        return 0

N,W = [int(zz) for zz in input().split()]
L = [[0,0] for _ in range(N)]

for i in range(N):
    p,q = [int(zz) for zz in input().split()]
    L[i][0] = p
    L[i][1] = q

gene_length = N # 遺伝子長
individual_length = 30 # 個体数
generation = 1000 # 世代数
mutate_rate = 0 # 突然変異の確率
elite_rate = 0.2 # エリート選択の割合

pop = evaluate([(fitness(p), p) for p in get_population()])

for i_episode in range(generation):

    eva = evaluate(pop)
    elites = eva[:int(len(pop)*elite_rate)]

    pop = elites
    while len(pop) < individual_length:
        if random.random() < mutate_rate:
            m = random.randint(0, len(elites)-1)
            child = mutate(elites[m][1])
        else:
            m1 = random.randint(0, len(elites)-1)
            m2 = random.randint(0, len(elites)-1)
            child = two_point_crossover(elites[m1][1], elites[m2][1])
        pop.append((fitness(child), child))

eva = evaluate(pop)
print(pop[0][0])

Submission status: Wrong Answer

Solution code:
import random
import copy

def get_population():
    population = []
    for i in range(individual_length):
        population.append([random.randint(0,1) for j in range(gene_length)])
    return population

def evaluate(pop):
    pop.sort(reverse=True)
    return pop

def two_point_crossover(parent1, parent2):
    r1 = random.randint(0, gene_length-1)
    r2 = random.randint(r1, gene_length-1)
    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]
    return child

def mutate(parent):
    r = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent)
    child[r] = 1 if child[r]==0 else 0
    return child

def fitness(pop):
    value = 0
    weoght = 0
    for i in range(N):
        if pop[i]:
            value += L[i][1]
            weoght += L[i][0]
    if weoght <= W:
        return value
    else:
        return 0

N,W = [int(zz) for zz in input().split()]
L = [[0,0] for _ in range(N)]

for i in range(N):
    p,q = [int(zz) for zz in input().split()]
    L[i][0] = p
    L[i][1] = q

gene_length = N # 遺伝子長
individual_length = 30 # 個体数
generation = 1000 # 世代数
mutate_rate = 0.05 # 突然変異の確率
elite_rate = 0.2 # エリート選択の割合

pop = evaluate([(fitness(p), p) for p in get_population()])

for i_episode in range(generation):

    eva = evaluate(pop)
    elites = eva[:int(len(pop)*elite_rate)]

    pop = elites
    while len(pop) < individual_length:
        if random.random() < mutate_rate:
            m = random.randint(0, len(elites)-1)
            child = mutate(elites[m][1])
        else:
            m1 = random.randint(0, len(elites)-1)
            m2 = random.randint(0, len(elites)-1)
            child = two_point_crossover(elites[m1][1], elites[m2][1])
        pop.append((fitness(child), child))

eva = evaluate(pop)
print(pop[0][0])

Submission status: Wrong Answer

Solution code:
import random
import copy

def get_population():
    population = []
    for i in range(individual_length):
        population.append([random.randint(0,1) for j in range(gene_length)])
    return population

def evaluate(pop):
    pop.sort(reverse=True)
    return pop

def two_point_crossover(parent1, parent2):
    r1 = random.randint(0, gene_length-1)
    r2 = random.randint(r1, gene_length-1)
    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]
    return child

def mutate(parent):
    r = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent)
    child[r] = 1 if child[r]==0 else 0
    return child

def fitness(pop):
    value = 0
    weoght = 0
    for i in range(N):
        if pop[i]:
            value += L[i][1]
            weoght += L[i][0]
    if weoght <= W:
        return value
    else:
        return 0

N,W = [int(zz) for zz in input().split()]
L = [[0,0] for _ in range(N)]

for i in range(N):
    p,q = [int(zz) for zz in input().split()]
    L[i][0] = p
    L[i][1] = q

gene_length = N # 遺伝子長
individual_length = 20 # 個体数
generation = 100 # 世代数
mutate_rate = 0.05 # 突然変異の確率
elite_rate = 0.2 # エリート選択の割合

pop = evaluate([(fitness(p), p) for p in get_population()])

for i_episode in range(generation):

    eva = evaluate(pop)
    elites = eva[:int(len(pop)*elite_rate)]

    pop = elites
    while len(pop) < individual_length:
        if random.random() < mutate_rate:
            m = random.randint(0, len(elites)-1)
            child = mutate(elites[m][1])
        else:
            m1 = random.randint(0, len(elites)-1)
            m2 = random.randint(0, len(elites)-1)
            child = two_point_crossover(elites[m1][1], elites[m2][1])
        pop.append((fitness(child), child))

eva = evaluate(pop)
print(pop[0][0])

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split()]
wvs = [(int(w), int(v)) for w,v in [input().split() for _ in range(N)]]
dp = [0]*(K+1)
for i, wv in enumerate(wvs):
  w,v = wv
  for j in range(i,K):
    if (j+w) <= (K):
      dp[j+w] = max(dp[j+w], dp[j] + v)
print(max(dp))

Submission status: Wrong Answer

Solution code:
N, W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for sum_w in range(1, W + 1):
        if sum_w-wv[i-1][0] >= 0:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(max(max(dp)))

Submission status: Wrong Answer

Solution code:
# DP
def main():
    from builtins import max

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

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


main()

Submission status: Wrong Answer

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

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


main()

Submission status: Wrong Answer

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

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


main()

Submission status: Wrong Answer

Solution code:
import sys
n, W = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[0 for _ in range(W+1)] for _ in range(n)]
for w in range(W+1):
    if w>=L[0][0]:
        dp[0][w] = L[0][1]

#print(dp)
for i in range(1, n):
    for w in range(W+1):
        if w <L[i][0]: #そもそも加えられないとき
            dp[i][w] = dp[i-1][w] #前回の状態を代入。
        else: #加えようとしたら入るとき
            dp[i][w] = max(dp[i-1][w-L[i][0]] + L[i][1], dp[i-1][w]) #max(加えた時の価値, 前回の状態)
            
print(dp)
print(max(dp[-1]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
knapsack = []
for _ in range(n):
    a, b = map(int, input().split())
    knapsack.append([a, b])
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0
for i in range(n):
    for j in range(w + 1):
        if dp[i][j] != 0:
            dp[i + 1][j] = dp[i][j]
        if knapsack[i][0] + j <= w:
            if j == 0:
                dp[i + 1][knapsack[i][0] + j] = max(dp[i][j] + knapsack[i][1],
                                                    dp[i][knapsack[i][0] + j])
            else:
                if dp[i][j] != 0:
                    dp[i + 1][knapsack[i][0] + j] = max(dp[i][j] + knapsack[i][1],
                                                        dp[i][knapsack[i][0] + j])
                
print(max(dp[-1]))

Submission status: Wrong Answer

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = maximum value using at most i weight and using elements 1,...,j

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

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(1,N+1):
        if weights[item-1] > weight: continue

        dp[weight][item] = max(dp[weight][item],
                               values[item-1] + dp[weight - weights[item-1]][item - 1])

        dp[weight][item] = max(dp[weight-1][item], dp[weight][item])
        
print(max(dp[-1]))

Submission status: Wrong Answer

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

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

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(1,N+1):
        if weights[item-1] > weight: continue

        # Case: include item
        dp[weight][item] = max(dp[weight][item],
                               values[item-1] + dp[weight - weights[item-1]][item - 1])

        dp[weight][item] = max(dp[weight-1][item], dp[weight][item])
        
        # Case: dont include item
        if item == 0: continue
        
        dp[weight][item] = max(dp[weight][item],
                               dp[weight][item - 1])

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

Submission status: Wrong Answer

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

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

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(1,N+1):
        if weights[item-1] > weight: continue

        # Case: include item
        dp[weight][item] = max(dp[weight][item],
                               values[item-1] + dp[weight - weights[item-1]][item - 1])

        # Case: dont include item
        if item == 0: continue
        
        dp[weight][item] = max(dp[weight][item],
                               dp[weight][item - 1])

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

Submission status: Wrong Answer

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

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

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(N):
        if weights[item] > weight: continue

        # Case: include item
        dp[weight][item] = max(dp[weight][item],
                               values[item] + dp[weight - weights[item]][item - 1])

        # Case: dont include item
        if item == 0: continue
        
        dp[weight][item] = max(dp[weight][item],
                               dp[weight][item - 1])
        

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

Submission status: Wrong Answer

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

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

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
    dp[w][i] = v
    
for weight in range(1,W+1):
    for item in range(N):
        if weight - weights[item] < 0: continue
        if item == 0:
            dp[weight][item] = max(dp[weight][item], dp[weight - 1][item])
            continue
        dp[weight][item] = max(dp[weight-1][item], dp[weight][item-1],
                               values[item] + dp[weight - weights[item]][item-1])

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

Submission status: Wrong Answer

Solution code:
import numpy as np

n, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for i in range(n)])

dp = np.zeros((n + 1, W + 1))


def chmax(a, b):
    if a > b:
        return a
    else:
        return b


for i in range(n):
    for sum_w in range(W + 1):
        if sum_w >= wv[i, 0]:
            dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w - wv[i, 0]] + wv[i, 1])
        else:
            dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w])

print(int(dp[n , W]))

Submission status: Wrong Answer

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

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

ans = max(dp)
print(ans)

Submission status: Wrong Answer

Solution code:
# Atcoder Knapsack 1
items, cap = map(int, input().strip().split())
weight = [0]*items
value = [0]*items
for i in range(items):
	weight[i], value[i] = map(int, input().strip().split())
zipped = zip(value,weight)
tup = [(x,y) for x,y in sorted(zipped, reverse=True)]
newvalue = [x for x,_ in tup]
newweight = [x for _,x in tup]
# print(newweight, newvalue)
total = 0
i=0
while i<items:
	if cap >=newweight[i]:
		cap-=newweight[i]
		total+=newvalue[i]
	i+=1
print(total)

Submission status: Wrong Answer

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

dp = [[float('-inf') for _ in range(W*100)] for _ in range(N+10)]
dp[0][0] = 0
for i, (item_weight, item_value) in enumerate(items):  # i番目の品
    for total_weight in range(W+10):                   # 重さの合計
        dp[i+1][total_weight] = max(dp[i][total_weight], dp[i+1][total_weight])
        dp[i+1][total_weight+item_weight] = max(dp[i][total_weight]+item_value, dp[i+1][total_weight+item_weight])
        
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W = map(int,input().split(' '))

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

for i in range(N):
    w,v = map(int,input().split(' '))
    
    for j in range(W+1):
        if w > j:
            current_list[j] = max_list[j]
        else:
            new =  v + max_list[j-w] 
            current_list[j] = new if new > max_list[j] else max_list[j]
            
    max_list = current_list

print(max_list[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W = map(int,input().split(' '))

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

for i in range(N):
    w,v = map(int,input().split(' '))  
    current_list[w:] = current_list[w:] + v + max_list[0:-w]
    current_list = np.full(W+1,0, dtype=np.int64)
print(max_list[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
N,W = map(int,input().split(' '))

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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


print(0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
wv_array = [[int(x) for x in input().split()] for y in range(n)]

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

index = 1
for ww, vv in wv_array:
    for capacity in range(1, w + 1):
        if ww <= capacity:
            dp[index][capacity] = dp[index - 1][capacity - ww] + vv
        else:
            dp[index][capacity] = dp[index - 1][capacity]
    index += 1
print(max(dp[n]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in range(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    f = [[0 for _ in range(limit+1)] for _ in range(n)]

    if weights[0] <= limit:
        for w in range(weights[0], limit):
            f[0][w] = values[0]

    for w in range(1, limit+1):
        for i in range(1, n):
            f[i][w] = max(f[i-1][w], f[i][w])
            if weights[i] <= w:
                f[i][w] = max(f[i][w], f[i-1][w-weights[i]] + values[i])

    return f[-1][-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
I = lambda : map(int,stdin.readline().split())

N,tw = I()

w,v = [],[]

for i in range(N):
	W,V = I()
	w.append(W)
	v.append(V)

# print w,v
mat = []
for i in range(N+1):
	mat.append([0]*(tw+1))

# print mat[1][1]
for i in range(1,N+1):
	for j in range(1,tw+1):
		print i,j
		no_curr = mat[i-1][j]
		yes_curr = 0
		weight_curr = w[i-1]
		if (j >= weight_curr):
			yes_curr = v[i-1] + mat[i-1][j - weight_curr]
		mat[i][j] = max(no_curr,yes_curr)
print mat[N][tw]

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
dp = [0] * (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[W])

Submission status: Wrong Answer

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

for _ in range(N-1):
    wi, vi = list(map(int, input().split()))
    tmp = [0] * W

    for w in range(W):
        if w-wi >= 0:
            tmp[w] = max(A[w-wi] + vi, A[w])

    A = tmp

print(max(A))

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N, W = map(int, input().split())
# dp=[[0]*(W+1) for _ in range(N+1)] 
dp = np.zeros((N+1, W+1), dtype='uint64')
 
for i in range(N):
  w, v = map(int, input().split()) 
  dp[i+1][:w] = dp[i][:w]
  dp[i+1][w:] = np.maximum(dp[i][w:], dp[i][:-w]+v)
print(np.max(dp[N]))
print(dp)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
x=[list(map(int,input().split())) for _ in range(n)]
import numpy as np
dp=[[0]*(w+1) for _ in range(n+1)]
ans=0
for i in range(1,n+1):
    for j in range(w+1):
        if j>x[i-1][0]:
            dp[i][j]=max(dp[i-1][j+1-x[i-1][0]]+x[i-1][1],dp[i][j-1])
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j])
print(np.max(dp))

Submission status: Wrong Answer

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

dp=[[0]*(w+1) for _ in range(n+1)]
ans=0
for i in range(1,n+1):
    for j in range(w+1):
        if j>x[i-1][0]:
            dp[i][j]=max(dp[i-1][j+1-x[i-1][0]]+x[i-1][1],dp[i][j-1])
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j])
        ans=max(ans,dp[i][j])        
print(ans)

Submission status: Wrong Answer

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

dp=[[0]*(w+1) for _ in range(n+1)]
ans=0
for i in range(1,n+1):
    for j in range(w+1):
        if j>x[i-1][0]:
            dp[i][j]=max(dp[i-1][j+1-x[i-1][0]]+x[i-1][1],dp[i][j-1])
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j])
    ans=max(ans,dp[i][j])        
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n,w = map(int, input().split())
wvList = [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 j - wvList[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-wvList[i][0]]+wvList[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[n][w])

Submission status: Wrong Answer

Solution code:
import numpy as np
n, w = list(map(int, input().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dp = np.zeros((n + 1,w + 1))
for i in range(n):
    for j in range(w+1):
        if data[i][0] > j:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - data[i][0]] + data[i][1])
print(dp)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

INF = 10 ** 10

N, W = map(int, sys.stdin.readline().rstrip().split(" "))
wvs = []
for _ in range(N):
    w, v = map(int, sys.stdin.readline().rstrip().split(" "))
    wvs.append((w, v))


def max_value(n_index, w):
    current_w, current_v = wvs[n_index]
    if w < 0:
        return -INF
    if n_index == -1:
        print(n_index, w, 0)
        return 0
    else:
        print(n_index, w, "->", n_index-1, w, "|", n_index, w-current_w)
        res = max(max_value(n_index - 1, w), max_value(n_index-1, w - current_w) + current_v)
        print(n_index, w, res)
        return res


ans = max_value(N-1, W)
print(ans)
exit(0)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
table = np.zeros(w+1, dtype=np.int64)

for i in range(n):
    l = table[:-wv[i][0]]
    r = table[wv[i][0]:]
    np.maximum(l + wv[i][1], r, out = r)

print(table[w-1])

Submission status: Wrong Answer

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

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

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

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

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

print(max(dp[N]))

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())

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

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

print(max(dp[N]))

Submission status: Wrong Answer

Solution code:
# dpD - Knapsack 1
import sys
input = sys.stdin.readline

def main():
    n, w = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    dp = [[0] * (w + 1) for i in range(n)]
    for i in range(n):
        for j in range(w, A[i][0] - 1, -1):
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - A[i][0]] + A[i][1])
    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      t[nw] = nv
        
print(max(t.values()))
print(t)

Submission status: Wrong Answer

Solution code:
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(t.keys())
  for j in keys:
    nw = j - d[i][0]
    if nw < 0:
      continue
    nv = t[j] + d[i][1]
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))