Problem:


Score : 400 points

Problem Statement

You have N items and a bag of strength W.
The i-th item has a weight of w_i and a value of v_i.

You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

Constraints

1 ≤ N ≤ 100

1 ≤ W ≤ 10^9

1 ≤ w_i ≤ 10^9

For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.

1 ≤ v_i ≤ 10^7

W, each w_i and v_i are integers.

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.



Sample input:
4 6
2 1
3 4
4 10
3 4


Sample output:
11

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
import numpy as np

N, MaxTotalWeight = map(int, raw_input().split())

def getWeightValuePair(W,Values,WeightValuePair):
    totalValue = 0
    WeightKeys = WeightValuePair.keys()
    for i in range(len(Values)):
        totalValue += Values[i]
        for totalWeight in WeightKeys:
            if (totalWeight + W * (i+1)) <= MaxTotalWeight:
                if (totalWeight + W * (i+1)) not in WeightValuePair:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePair[totalWeight] +  totalValue
                elif WeightValuePair[totalWeight] +  totalValue > WeightValuePair[totalWeight + W * (i+1)]:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePair[totalWeight] +  totalValue
    return WeightValuePair

Weights = []
WeightsValues = []

for i in xrange(N):
    tempData = map(int, raw_input().split())        
    if i == 0:
        Weights.append(tempData[0])
        Weights.append(tempData[0]+1)
        Weights.append(tempData[0]+2)
        Weights.append(tempData[0]+3)
        WeightsValues.append([tempData[1]])
        WeightsValues.append([])
        WeightsValues.append([])
        WeightsValues.append([])
    else:
        WeightsValues[tempData[0] - Weights[0]].append(tempData[1])

for data in WeightsValues:
    data.sort(reverse=True)

returnWeightValuePair = {0:0}
for i in range(4):
    returnWeightValuePair = getWeightValuePair(Weights[i],WeightsValues[i],returnWeightValuePair)

print long(max(returnWeightValuePair.values()))

Submission status: Wrong Answer

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


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

print(maxv)

Submission status: Wrong Answer

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


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

print(maxv)

Submission status: Wrong Answer

Solution code:
N, W = map(int,input().split())
DP = [[0 for _ in range(W+1)] for _ in range(N+1)] # 全て0、何も選ばない
selected = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

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

print(DP[N][W])

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
	
def f3():
	L.sort(key = (lambda x: - x[1]//x[0]))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 1000000:
	print(f1())
elif W > 10000000:
	print(f3())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
	
def f3():
	L.sort(key = (lambda x: - x[1]//x[0]))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 10000:
	print(f1())
elif W > 10000000:
	print(f3())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
	
def f3():
	L.sort(key = (lambda x: - x[1]//x[0]))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 10000:
	print(f1())
elif W > 1000:
	print(f3())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
	
def f3():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans
def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 100000:
	print(f1())
elif W > 1000:
	print(f3())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 100:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 4)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 1000000:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 7)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 100000:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 100000:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

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

for _ in range(N):
    item = list(map(int, input().split()))
    item_list.append(item)

item_list = sorted(item_list, key=lambda item: item[1], reverse=True)

max_sum_v = 0

for i in range(N):
    sum_w = 0
    sum_v = 0
    for j in range(i, N):
        if item_list[j][0] + sum_w <= W:
            sum_w += item_list[j][0]
            sum_v += item_list[j][1]

    max_sum_v = max(sum_v, max_sum_v)

print(max_sum_v)

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 400)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 10000:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 4)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 10000:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

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


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

print(maxv)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

class BagItem(object):
    def __init__(self, w, v):
        super(BagItem, self).__init__()
        self.w = w
        self.v = v

    def cost_performance(self):
        return self.v / self.w

n,w = [int(x) for x in input().rstrip().split(" ")]
items = []

for i in range(n):
    nn, ww = [int(x) for x in input().rstrip().split(" ")]
    items.append(BagItem(nn, ww))

items.sort(key=lambda BagItem:(BagItem.cost_performance()), reverse=True)

total_value = 0
total_weight = 0
for i in range(len(items)):
    if total_weight + items[i].w > w:
        continue
    total_value = total_value + items[i].v
    total_weight = total_weight + items[i].w

print(total_value)

Submission status: Wrong Answer

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

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

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

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

value = 0
weight = 0
maxvalue = 0

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

print(maxvalue)

Submission status: Wrong Answer

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

for _ in range(N):
    item = list(map(int, input().split()))
    item_list.append(item)

item_list = sorted(item_list, key=lambda item: item[1], reverse=True)

max_sum_v = 0

for i in range(N):
    sum_item_list = list()
    sum_w = 0
    sum_v = 0
    for j in range(i, N):
        if item_list[j][0] + sum_w <= W:
            sum_item_list.append(item_list[j])
            sum_w += item_list[j][0]
            sum_v += item_list[j][1]

        if sum_w == W:
            break
    max_sum_v = max(sum_v, max_sum_v)

print(max_sum_v)

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]/x[0]))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 10000:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

class BagItem(object):
    def __init__(self, w, v):
        super(BagItem, self).__init__()
        self.w = w
        self.v = v

    def cost_performance(self):
        return self.v / self.w

n,w = [int(x) for x in input().rstrip().split(" ")]
items = []

for i in range(n):
    nn, ww = [int(x) for x in input().rstrip().split(" ")]
    items.append(BagItem(nn, ww))

items.sort(key=lambda BagItem:(BagItem.v, BagItem.cost_performance(), -BagItem.w), reverse=True)

total_value = 0
total_weight = 0
for i in range(len(items)):
    if total_weight + items[i].w > w:
        continue
    total_value = total_value + items[i].v
    total_weight = total_weight + items[i].w

print(total_value)

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 100000:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 1000:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
A = list(map(int,input().split(" ")))
B = list()
W = list(map(int,"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0".split(" ")))
V = list(map(int,"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0".split(" ")))

X = list(map(str,"0".split(" ")))
X.append(list(map(str,"0 1".split(" "))))
X.append(list(map(str,"0 1 2".split(" "))))
X.append(list(map(str,"0 1 2 3".split(" "))))
X.append(list(map(str,"1".split(" "))))
X.append(list(map(str,"1 2".split(" "))))
X.append(list(map(str,"1 2 3".split(" "))))
X.append(list(map(str,"2".split(" "))))
X.append(list(map(str,"2 3".split(" "))))
X.append(list(map(str,"3".split(" "))))
X.append(list(map(str,"0 1 3".split(" "))))
X.append(list(map(str,"0 2".split(" "))))
X.append(list(map(str,"0 2 3".split(" "))))
X.append(list(map(str,"0 3".split(" "))))
X.append(list(map(str,"1 3".split(" "))))


for i in range(A[0]):
    B.append(list(map(int,input().split(" "))))
    B[i].append(B[i][1]/B[i][0])

C = sorted(B, key=lambda x: x[2],reverse=True)

for ii in range(15):
    for i in range(A[0]):
        if str(C[i][0] - B[0][0]) in X[ii]:
            if A[1] >= W[ii] + C[i][0]:
                W[ii] = W[ii] + C[i][0]
                V[ii] = V[ii] + C[i][1]
                if A[1] == W[ii]:
                    break

print(V)

Submission status: Wrong Answer

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	return ans


def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 100:
	print(f1())
else:
	print(f2())

Submission status: Wrong Answer

Solution code:
A = list(map(int,input().split(" ")))
B = list()
W = list(map(int,"0 0 0 0".split(" ")))
V = list(map(int,"0 0 0 0".split(" ")))
 
for i in range(A[0]):
    B.append(list(map(int,input().split(" "))))
    B[i].append(B[i][1]/B[i][0])
 
C = sorted(B, key=lambda x: x[2],reverse=True)
 
for ii in range(4):
    for i in range(A[0]):
        if C[i][0] <= ii + B[0][0]:
            if A[1] >= W[ii] + C[i][0]:
                W[ii] = W[ii] + C[i][0]
                V[ii] = V[ii] + C[i][1]
                if A[1] == W[ii]:
                    break
 
print(max(V))

Submission status: Wrong Answer

Solution code:
data = input().split()
N = int(data[0])
W = int(data[1])

list = []
for i in range(N):
	data = input().split()
	list.append((int(data[1]), int(data[0])))
list.sort(reverse=True)

w = 0
v = 0

i = 0
while(i < len(list)):
	if((w + list[i][1]) <= W):
		w += list[i][1]
		v += list[i][0]
	i += 1
print(v)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

class BagItem(object):
    def __init__(self, w, v):
        super(BagItem, self).__init__()
        self.w = w
        self.v = v

n,w = [int(x) for x in input().rstrip().split(" ")]
items = []

for i in range(n):
    nn, ww = [int(x) for x in input().rstrip().split(" ")]
    items.append(BagItem(nn, ww))

items.sort(key=lambda BagItem:(BagItem.v, -BagItem.w), reverse=True)

total_value = 0
total_weight = 0
for i in range(len(items)):
    if total_weight + items[i].w > w:
        continue
    total_value = total_value + items[i].v
    total_weight = total_weight + items[i].w

print(total_value)

Submission status: Wrong Answer

Solution code:
A = list(map(int,input().split(" ")))
B = list()
W = list(map(int,"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0".split(" ")))
V = list(map(int,"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0".split(" ")))

X = list(map(str,"0".split(" ")))
X.append(list(map(str,"0 1".split(" "))))
X.append(list(map(str,"0 1 2".split(" "))))
X.append(list(map(str,"0 1 2 3".split(" "))))
X.append(list(map(str,"1".split(" "))))
X.append(list(map(str,"1 2".split(" "))))
X.append(list(map(str,"1 2 3".split(" "))))
X.append(list(map(str,"2".split(" "))))
X.append(list(map(str,"2 3".split(" "))))
X.append(list(map(str,"3".split(" "))))
X.append(list(map(str,"0 1 3".split(" "))))
X.append(list(map(str,"0 2".split(" "))))
X.append(list(map(str,"0 2 3".split(" "))))
X.append(list(map(str,"0 3".split(" "))))
X.append(list(map(str,"1 3".split(" "))))


for i in range(A[0]):
    B.append(list(map(int,input().split(" "))))
    B[i].append(B[i][1]/B[i][0])

C = sorted(B, key=lambda x: x[2],reverse=True)

for ii in range(15):
    for i in range(A[0]):
        if str(C[i][0] - B[1][0]) in X[ii]:
            if A[1] >= W[ii] + C[i][0]:
                W[ii] = W[ii] + C[i][0]
                V[ii] = V[ii] + C[i][1]
                if A[1] == W[ii]:
                    break

print(max(V))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
 
class BagItem(object):
    def __init__(self, w, v):
        super(BagItem, self).__init__()
        self.w = w
        self.v = v
 
    def cost_performance(self):
        return self.w / self.v
 
n,w = [int(x) for x in input().rstrip().split(" ")]
items = []
 
for i in range(n):
    nn, ww = [int(x) for x in input().rstrip().split(" ")]
    items.append(BagItem(nn, ww))
 
items.sort(key=BagItem.cost_performance)
 
total_value = 0
total_weight = 0
for i in range(len(items)):
    if total_weight + items[i].w > w:
        continue
    total_value = total_value + items[i].v
    total_weight = total_weight + items[i].w
 
print(total_value)

Submission status: Wrong Answer

Solution code:
import numpy as np

def generate():
    newGen = np.zeros(n)
    for p in range(pop):
        gen = np.random.rand(n)
        for i in range(n):
            if gen[i] > 0.5:
                gen[i] = 1
            else:
                gen[i] = 0
        newGen = np.vstack([newGen,gen])
    newGen = np.vsplit(newGen,[1])[1]
    return newGen

def evaluate(gen):
    sum = np.zeros(pop)
    for p in range(pop):
        for i in range(n):
            sum[p] += v[i][1] * gen[p][i]
    sum = sum.reshape(pop, 1)
    gen = np.hstack([gen, sum])
    return gen

def best(gen):
    best0 = gen[0]
    for p in range(1,pop):
        if best0[-1] < gen[p][-1]:
            best0 = gen[p]
    return best0

def select(b,p):
    parents = np.zeros(b.shape[1])
    for i in range(p):
        p1 = b[np.random.randint(0, b.shape[0] - 1)]
        p2 = b[np.random.randint(0, b.shape[0] - 1)]
        if p1[-1] < p2[-1]:
            parents = np.vstack([parents, p2])
        else:
            parents = np.vstack([parents, p1])
    return np.vsplit(parents,[1])[1]

def crossover(parents):
    parents = np.hsplit(parents, [-1])[0]
    newGen = np.zeros(parents.shape[1])
    for i in range(parents.shape[0] / 2):
        l = np.random.randint(1, parents.shape[1] - 1)
        p1_0, p1_1 = np.hsplit(parents[i * 2], [l])
        p2_0, p2_1 = np.hsplit(parents[i * 2 + 1], [l])
        c1 = np.hstack([p1_0, p2_1])
        c2 = np.hstack([p1_1, p2_0])
        newGen = np.vstack([newGen, c1])
        newGen = np.vstack([newGen, c2])
    return np.vsplit(newGen, [1])[1]

def mutation(newGen):
    for p in range(pop):
        w_sum = 0
        for i in range(n):
            w_sum += newGen[p][i] * v[i][0]
        if w_sum > w:
            ran = np.random.permutation(np.arange(n))
            while(w_sum > w):
                ran, q = np.hsplit(ran,[-1])
                if newGen[p][q] == 1:
                    w_sum -= newGen[p][q] * v[q][0]
                    newGen[p][q] = 0
    return newGen


pop = 10
n, w = map(int,raw_input().split())
v = []
N = 400
for i in range(n):
    v.append(map(int,raw_input().split()))

eval = evaluate(generate())
c = mutation(crossover(select(eval,pop)))
eval = evaluate(c)
be = best(eval)
for i in range(N):
    c = mutation(crossover(select(eval,pop)))
    eval = evaluate(c)
    if be[-1] < best(eval)[-1]:
        be = best(eval)
print int(be[-1])

Submission status: Wrong Answer

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

for _ in range(N):
    item = list(map(int, input().split()))
    item_list.append(item)

item_list = sorted(item_list, key=lambda item: item[1], reverse=True)

sum_item_list = list()
sum_w = 0
sum_v = 0

r_item_list = None
for i in range(N):
    if item_list[i][0] + sum_w <= W:
        sum_item_list.append(item_list[i])
        sum_w += item_list[i][0]
        sum_v += item_list[i][1]

    if sum_w == W:
        break

print(sum_v)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

class BagItem(object):
    def __init__(self, w, v):
        super(BagItem, self).__init__()
        self.w = w
        self.v = v

    def cost_performance(self):
        return self.w / self.v

n,w = [int(x) for x in input().rstrip().split(" ")]
items = []

for i in range(n):
    nn, ww = [int(x) for x in input().rstrip().split(" ")]
    items.append(BagItem(nn, ww))

items.sort(key=BagItem.cost_performance)

total_value = 0
total_weight = 0
for i in range(len(items)):
    if total_weight + items[i].w > w:
        continue
    total_value = total_value + items[i].v
    total_weight = total_weight + items[i].w

print(total_value)

for i in range(len(items)):
    print(items[i].w, items[i].v)

Submission status: Wrong Answer

Solution code:
import numpy as np

def generate():
    newGen = np.zeros(n)
    for p in range(pop):
        gen = np.random.rand(n)
        for i in range(n):
            if gen[i] > 0.5:
                gen[i] = 1
            else:
                gen[i] = 0
        newGen = np.vstack([newGen,gen])
    newGen = np.vsplit(newGen,[1])[1]
    return newGen

def evaluate(gen):
    sum = np.zeros(pop)
    for p in range(pop):
        for i in range(n):
            sum[p] += v[i][1] * gen[p][i]
    sum = sum.reshape(pop, 1)
    gen = np.hstack([gen, sum])
    return gen

def best(gen):
    best0 = gen[0]
    for p in range(1,pop):
        if best0[-1] < gen[p][-1]:
            best0 = gen[p]
    return best0

def select(b,p):
    parents = np.zeros(b.shape[1])
    for i in range(p):
        p1 = b[np.random.randint(0, b.shape[0] - 1)]
        p2 = b[np.random.randint(0, b.shape[0] - 1)]
        if p1[-1] < p2[-1]:
            parents = np.vstack([parents, p2])
        else:
            parents = np.vstack([parents, p1])
    return np.vsplit(parents,[1])[1]

def crossover(parents):
    parents = np.hsplit(parents, [-1])[0]
    newGen = np.zeros(parents.shape[1])
    for i in range(parents.shape[0] / 2):
        l = np.random.randint(1, parents.shape[1] - 1)
        p1_0, p1_1 = np.hsplit(parents[i * 2], [l])
        p2_0, p2_1 = np.hsplit(parents[i * 2 + 1], [l])
        c1 = np.hstack([p1_0, p2_1])
        c2 = np.hstack([p1_1, p2_0])
        newGen = np.vstack([newGen, c1])
        newGen = np.vstack([newGen, c2])
    return np.vsplit(newGen, [1])[1]

def mutation(newGen):
    for p in range(pop):
        w_sum = 0
        for i in range(n):
            w_sum += newGen[p][i] * v[i][0]
        if w_sum > w:
            ran = np.random.permutation(np.arange(n))
            while(w_sum > w):
                ran, q = np.hsplit(ran,[-1])
                if newGen[p][q] == 1:
                    w_sum -= newGen[p][q] * v[q][0]
                    newGen[p][q] = 0
    return newGen


pop = 10
n, w = map(int,raw_input().split())
v = []
N = 300
for i in range(n):
    v.append(map(int,raw_input().split()))

eval = evaluate(generate())
c = mutation(crossover(select(eval,pop)))
eval = evaluate(c)
be = best(eval)
for i in range(N):
    c = mutation(crossover(select(eval,pop)))
    eval = evaluate(c)
    if be[-1] < best(eval)[-1]:
        be = best(eval)
print int(be[-1])