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: Runtime Error

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]/(w1 - x[0] + 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 > 10000:
	print(f1())
else:
	print(f2())

Submission status: Runtime Error

Solution code:
def d():
    n, w = map(int, input().split())
    shop = []
    for i in range(n):
        shop.append( list(map(int, input().split())) )
    # s = sorted(shop, key= lambda item: item[1]/item[0], reverse=True)
    # print(n, w, s)
    best = 0
    k = 0
    while k <= n:
        bag = [0, 0]
        i = 0
        while i < k:
            item = s[i]
            i += 1
            if bag[0]+item[0] <= w:
                bag[0] += item[0]
                bag[1] += item[1]
            else:
                continue
        best = max(best, bag[1])
        k += 1
    print(best)

d()

Submission status: Runtime Error

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]/(w1-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: Runtime Error

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

    w = []
    v = []
    for n in range(N):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)

    if w[0] <= 400:  # napsack
        dp = [[-1 for y in range(401)] for x in range(N+1)]
        for i in range(N+1):
            for j in range(W+1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                else:
                    if j - w[i-1] >= 0:
                        dp[i][j] = max(dp[i-1][max(j-w[i-1], 0)] + v[i-1], dp[i-1][j])
                    else:
                        dp[i][j] = dp[i-1][j]
        print(dp[N][W])

    else:  # by cospa sort
        pass

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

ar = np.array([0] * (N+1) * (W+1)).reshape(N+1,W+1)
ar_c = np.array([None] * (N+1) * (W+1)).reshape(N+1,W+1)
for i in range(1,N+1):
    for w in range(1,W+1):
        if lw[i] <= w:
            if lv[i] + ar[i-1, w- lw[i]] > ar[i-1, w]:
                ar[i,w] = lv[i] + ar[i-1, w - lw[i]]
                ar_c[i,w] = 'D'
            else:
                ar[i, w] = ar[i-1,w]
                ar_c[i,w] = 'T'
        else:
            ar[i,w] = ar[i-1,w]
            ar_c[i,w] = 'T'
print(np.max(ar))

Submission status: Runtime Error

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

w = []
v = []
for i in range(N):
    temp0, temp1 = map(int, raw_input().split())
    w.append(temp0)
    v.append(temp1)

table = []

def searchTable(item, weight):
    for i in range(len(table)):
        if table[i][0] == item and table[i][1] == weight:
            return True, table[i][2]
    return False, -1

def function(item, weight):
    flag, data = searchTable(item, weight)
    if flag:
        return data
    if item == N:
        result = 0
    elif weight < w[item]:
        result = function(item + 1, weight)
    else:
        result = max(function(item + 1, weight - w[item]) + v[item], function(item + 1, weight))
(item + 1, weight - w[item]) + v[item])

    table.append([item, weight, result])
    return result

print(function(0, W))

Submission status: Runtime Error

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.w, 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: Runtime Error

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), 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: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

n,weight = map(int, raw_input().split())

v = [0]*n
w = [0]*n
    
for i in range(n):
    w[i],v[i] = map(int, raw_input().split())

dp = np.zeros((n+1,weight+1),dtype='int32')

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


print(dp[n][weight])

Submission status: Runtime Error

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

w = []
v = []
for i in range(N):
    temp0, temp1 = map(int, raw_input().split())
    w.append(temp0)
    v.append(temp1)

table = [[-1] * max(W + 1, (sum(w)))] * (N + 1)

def function(item, weight):
    if table[item][weight] != -1:
        return table[item][weight]
    if item == N:
        result = 0
    elif weight < w[item]:
        result = function(item + 1, weight)
    else:
        result = max(function(item + 1, weight - w[item]) + v[item], function(item + 1, weight))

    table[item][weight] = result
    return result

print(function(0, W))

Submission status: Runtime Error

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

w = []
v = []
for i in range(N):
    temp0, temp1 = map(int, raw_input().split())
    w.append(temp0)
    v.append(temp1)

table = [[-1] * max(W + 1, (sum(w)))] * (N + 1)

def function(item, weight):
    if table[item][weight] != -1:
        return table[item][weight]
    if item == N:
        print("item == N", item, weight)
        result = 0
    elif weight < w[item]:
        print("weight < w[item]", item, weight)
        result = function(item + 1, weight)
    else:
        print("check", item, weight)
        result = max(function(item + 1, weight - w[item]) + v[item], function(item + 1, weight))

    table[item][weight] = result
    return result

print(function(0, W))

Submission status: Runtime Error

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

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

WeightValueMatrix = np.zeros((W+1, N))
data = []
for i in range(N):
    data.append(map(int, raw_input().split()))

for i in range(N):
    if i == 0:
        for j in range(W+1):
            if j < data[i][0]:
                WeightValueMatrix[j][i] = 0
            else:
                WeightValueMatrix[j][i] = data[i][1]
    else:
        for j in range(W+1):
            if j < data[i][0]:
                WeightValueMatrix[j][i] = WeightValueMatrix[j][i-1]
            else:
                if WeightValueMatrix[j-data[i][0]][i-1] + data[i][1] > WeightValueMatrix[j][i-1]:
                    WeightValueMatrix[j][i] = WeightValueMatrix[j-data[i][0]][i-1] + data[i][1]
                else:
                    WeightValueMatrix[j][i] = WeightValueMatrix[j][i-1]

print long(WeightValueMatrix[W][N-1])

Submission status: Runtime Error

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

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

WeightValueMatrix = np.zeros((W+1, N))
data = []
for i in range(N):
    data.append(map(int, raw_input().split()))

for i in range(N):
    if i == 0:
        for j in range(W+1):
            if j < data[i][0]:
                WeightValueMatrix[j][i] = 0
            else:
                WeightValueMatrix[j][i] = data[i][1]
    else:
        for j in range(W+1):
            if j < data[i][0]:
                WeightValueMatrix[j][i] = WeightValueMatrix[j][i-1]
            else:
                if WeightValueMatrix[j-data[i][0]][i-1] + data[i][1] > WeightValueMatrix[j][i-1]:
                    WeightValueMatrix[j][i] = WeightValueMatrix[j-data[i][0]][i-1] + data[i][1]
                else:
                    WeightValueMatrix[j][i] = WeightValueMatrix[j][i-1]

print int(WeightValueMatrix[W][N-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:

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

w=[]
v=[]
for _ in range(N):
    t_w,t_v=map(int,raw_input().split(' '))
    w.append(t_w)
    v.append(t_v)

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

print dp[0][W]

Submission status: Runtime Error

Solution code:

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

w=[]
v=[]
for _ in range(N):
    t_w,t_v=map(int,raw_input().split(' '))
    w.append(t_w)
    v.append(t_v)

def rec(i,j):
    if dp[i][j]>=0:
        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 dp[i][j]


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

Submission status: Runtime Error

Solution code:
def rren(): return list(map(int, input().split()))

N, Wei = rren()
w = []
v = []
for _ in range(N):
    tempW , tempV = rren()
    w.append(tempW)
    v.append(tempV)

dp = [[-1 for x in range(N+10)] for y in range(Wei+10)]

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(rec(0,Wei))