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:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import accumulate

n,w = li()
wi,vi = li()
w0 = wi
v_list = [[0] for _ in range(4)]
v_list[0].append(vi)

for _ in range(n-1):
    wi,vi = li()
    v_list[wi-w0].append(vi)
    
for i in range(4):
    v_list[i].sort(reverse=True)
    v_list[i] = list(accumulate(v_list[i]))
    
ans = 0
res = w
for w1 in range(len(v_list[0])):
    
    if w - w0*(w1) < 0:
        pass
    else:
        res1 = w - w0*(w1)
        ans1 = v_list[0][w1]
        ans = max(ans, ans1)
    

    for w2 in range(len(v_list[1])):

        if res1 - (w0+1)*(w2) < 0:
            pass
        
        else:
            res2 = res1 - (w0+1)*(w2)
            ans2 = ans1 + v_list[1][w2]
            ans = max(ans, ans2)

        
        
        for w3 in range(len(v_list[2])):
            
            if res2 - (w0+2)*(w3) < 0:
                pass
            
            else:
                res3 = res2 - (w0+2)*(w3)
                ans3 = ans2 + v_list[2][w3]
                ans = max(ans, ans3)
                
            
            for w4 in range(len(v_list[3])):

                if res3 - (w0+3)*(w4) < 0:
                    pass
                
                else:
                    res4 = res3 - (w0+3)*(w4)
                    ans4 = ans3 + v_list[3][w4]
                    ans = max(ans, ans4)

                
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import accumulate

n,w = li()
wi,vi = li()
w0 = wi
v_list = [[0] for _ in range(4)]
v_list[0].append(vi)

for _ in range(n-1):
    wi,vi = li()
    v_list[wi-w0].append(vi)
    
for i in range(4):
    v_list[i].sort()
    v_list[i] = list(accumulate(v_list[i]))
    
ans = 0
res = w
for w1 in range(len(v_list[0])):
    
    if w - w0*(w1) < 0:
        pass
    else:
        res1 = w - w0*(w1)
        ans1 = v_list[0][w1]
        ans = max(ans, ans1)
    

    for w2 in range(len(v_list[1])):

        if res1 - (w0+1)*(w2) < 0:
            pass
        
        else:
            res2 = res1 - (w0+1)*(w2)
            ans2 = ans1 + v_list[1][w2]
            ans = max(ans, ans2)

        
        
        for w3 in range(len(v_list[2])):
            
            if res2 - (w0+2)*(w3) < 0:
                pass
            
            else:
                res3 = res2 - (w0+2)*(w3)
                ans3 = ans2 + v_list[2][w3]
                ans = max(ans, ans3)
                
            
            for w4 in range(len(v_list[3])):

                if res3 - (w0+3)*(w4) < 0:
                    pass
                
                else:
                    res4 = res3 - (w0+3)*(w4)
                    ans4 = ans3 + v_list[3][w4]
                    ans = max(ans, ans4)

                
print(ans)

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
x = []
for i in range(n):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
ti = x[0][0]
for i in range(n):
  x[i][0] -= ti
dp=[[[0,0] for i in range(n*3+1)] for j in range(n+1)]
for i in range(1,n+1):
  for j in range(n*3+1):
    if j- x[i-1][0]>=0:
      if dp[i-1][j][0] >= dp[i-1][j-x[i-1][0]][0]+x[i-1][1]:
        dp[i][j]  =[dp[i-1][j][0],dp[i-1][j][1]]
      else:
        dp[i][j] = [dp[i-1][j-x[i-1][0]][0]+x[i-1][1],dp[i-1][j-x[i-1][0]][1]+1]
    else:
      dp[i][j] = dp[i-1][j]
ans = 0
for i in dp:
  for j in range(n*3+1):
    omo = j + ti * i[j][1]
    if w >= omo:
      ans = max(ans,i[j][0])
print(ans)

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    items = defaultdict(list)
    for w, v in WV:
        items[w].append(v)

    for w in items:
        items[w].sort(reverse=True)

    for i in range(4-len(items)):
        items[-i] = []
    ws = list(items.keys())

    @lru_cache(maxsize=None)
    def f(rw, i, j, k, l):
        ret = 0
        if ws[0] <= rw and i < len(items[ws[0]]):
            ret = max(ret, f(rw - ws[0], i+1, j, k, l) + items[ws[0]][i])
        if ws[1] <= rw and j < len(items[ws[1]]):
            ret = max(ret, f(rw - ws[1], i, j+1, k, l) + items[ws[1]][j])
        if ws[2] <= rw and k < len(items[ws[2]]):
            ret = max(ret, f(rw - ws[2], i, j, k+1, l) + items[ws[2]][k])
        if ws[3] <= rw and k < len(items[ws[3]]):
            ret = max(ret, f(rw - ws[3], i, j, k, l+1) + items[ws[3]][k])

        return ret

    return f(W, 0, 0, 0, 0)


def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]

    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    items = defaultdict(list)
    for w, v in WV:
        items[w].append(v)

    for w in items:
        items[w].sort(reverse=True)

    for i in range(4-len(items)):
        items[-i] = []
    ws = list(items.keys())

    @lru_cache(maxsize=None)
    def f(rw, i, j, k, l):
        ret = 0
        if ws[0] <= rw and i < len(items[ws[0]]):
            ret = max(ret, f(rw - ws[0], i+1, j, k, l) + items[ws[0]][i])
        if ws[1] <= rw and j < len(items[ws[1]]):
            ret = max(ret, f(rw - ws[1], i, j+1, k, l) + items[ws[1]][j])
        if ws[2] <= rw and k < len(items[ws[2]]):
            ret = max(ret, f(rw - ws[2], i, j, k+1, l) + items[ws[2]][k])
        if ws[3] <= rw and k < len(items[ws[3]]):
            ret = max(ret, f(rw - ws[3], i, j, k+1, l) + items[ws[3]][k])

        return ret

    return f(W, 0, 0, 0, 0)


def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]

    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    items = defaultdict(list)
    for w, v in WV:
        items[w].append(v)

    for w in items:
        items[w].sort(reverse=True)

    for i in range(3-len(items)):
        items[-i] = []
    ws = list(items.keys())

    @lru_cache(maxsize=None)
    def f(rw, i, j, k):
        if rw <= 0:
            return 0
        ret = 0
        if i < len(items[ws[0]]):
            ret = max(ret, f(rw - ws[0], i+1, j, k) + items[ws[0]][i])
        if j < len(items[ws[1]]):
            ret = max(ret, f(rw - ws[1], i, j+1, k) + items[ws[1]][j])
        if k < len(items[ws[2]]):
            ret = max(ret, f(rw - ws[2], i, j, k+1) + items[ws[2]][k])

        return ret

    return f(W, 0, 0, 0)


def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]

    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, W, WV):
    items = defaultdict(list)
    for w, v in WV:
        items[w].append(v)

    for w in items:
        items[w].sort(reverse=True)

    for i in range(3-len(items)):
        items[-i] = []
    ws = list(items.keys())

    @lru_cache(maxsize=None)
    def f(rw, i, j, k):
        ret = 0
        if ws[0] <= rw and i < len(items[ws[0]]):
            ret = max(ret, f(rw - ws[0], i+1, j, k) + items[ws[0]][i])
        if ws[1] <= rw and j < len(items[ws[1]]):
            ret = max(ret, f(rw - ws[1], i, j+1, k) + items[ws[1]][j])
        if ws[2] <= rw and k < len(items[ws[2]]):
            ret = max(ret, f(rw - ws[2], i, j, k+1) + items[ws[2]][k])

        return ret

    return f(W, 0, 0, 0)


def main():
    N, W = read_int_n()
    WV = [read_int_n() for _ in range(N)]

    print(slv(N, W, WV))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

N,W = map(int, input().split())
WV = []
for i in range(N):
    WV.append(list(map(int, input().split())))
    
    
w1 = WV[0][0]
w1p0 = [0]
w1p1 = [0]
w1p2 = [0]
w1p3 = [0]
for w, v in WV:
    if w == w1:
        w1p0.append(v)
    elif w == w1+1:
        w1p1.append(v)
    elif w == w1+2:
        w1p2.append(v)
    else:
        w1p3.append(v)
        
w1p0.sort()
w1p1.sort()
w1p2.sort()
w1p3.sort()

w1p0sum = list(accumulate(w1p0))
w1p1sum = list(accumulate(w1p1))
w1p2sum = list(accumulate(w1p2))
w1p3sum = list(accumulate(w1p3))

ans_cand = [0]
for p0 in range(len(w1p0sum)-1,-1,-1):
    if p0*w1 > W:
        continue
    
    for p1 in range(len(w1p1sum)-1,-1,-1):
        if p0*w1+p1+1*(w1+1) > W:
            continue
        
        for p2 in range(len(w1p2sum)-1,-1,-1):
            if p0*w1+p1*(w1+1)+p2*(w1+2) > W:
                continue
            
            for p3 in range(len(w1p3sum)-1,-1,-1):
                if p0*w1+p1*(w1+1)+p2*(w1+2)+p3*(w1+3) > W:
                    continue
                
                ans_cand.append(w1p0sum[p0]+w1p1sum[p1]\
                                +w1p2sum[p2]+w1p3sum[p3])
                
print(max(ans_cand))

Submission status: Wrong Answer

Solution code:
n,m=input().split()
N = int(n)
M = int(m)
w_list = []
v_list = []
w1_values = []
w2_values = []
w3_values = []
w4_values = []
sum_w1_values = []
sum_w2_values = []
sum_w3_values = []
sum_w4_values = []
sum_v1 = 0
sum_v2 = 0
sum_v3 = 0
sum_v4 = 0

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

w1 = w_list[0]
for j in range(N):
	if(w_list[j] == w1):
		w1_values.append(v_list[j])
		sum_v1 += v_list[j]
		sum_w1_values.append(sum_v1)

	elif(w_list[j] == w1+1):
		w2_values.append(v_list[j])
		sum_v2 += v_list[j]
		sum_w2_values.append(sum_v2)

	elif(w_list[j] == w1+2):
		w3_values.append(v_list[j])
		sum_v3 += v_list[j]
		sum_w3_values.append(sum_v3)

	elif(w_list[j] == w1+3):
		w4_values.append(v_list[j])
		sum_v4 += v_list[j]
		sum_w4_values.append(sum_v4)

w1_values.sort()
w1_values.reverse()
w2_values.sort()
w2_values.reverse()
w3_values.sort()
w3_values.reverse()
w4_values.sort()
w4_values.reverse()

for p in range(len(w1_values)):
	sum_v1 += w1_values[p]
	sum_w1_values.append(sum_v1)

for q in range(len(w2_values)):
	sum_v2 += w2_values[q]
	sum_w2_values.append(sum_v2)

for r in range(len(w3_values)):
	sum_v3 += w3_values[r]
	sum_w3_values.append(sum_v3)

for s in range(len(w4_values)):
	sum_v4 += w4_values[s]
	sum_w4_values.append(sum_v4)


sum_w1_values.insert(0,0)
sum_w2_values.insert(0,0)
sum_w3_values.insert(0,0)
sum_w4_values.insert(0,0)

max_value = 0
count = 0
for w in range(len(sum_w4_values)):
	for x in range(len(sum_w3_values)):
		for y in range(len(sum_w2_values)):
			for z in range(len(sum_w1_values)):
				count = w+x+y+z
				weight = (w1)*z + (w1+1)*y +(w1+2)*x + (w1+3)*w
				if(count<=N and weight<=M and max_value<(sum_w1_values[z] + sum_w2_values[y] + sum_w3_values[x] + sum_w4_values[w])):
					max_value = sum_w1_values[z] + sum_w2_values[y] + sum_w3_values[x] + sum_w4_values[w]


print(max_value)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, W = map(int, input().split())
dd = defaultdict(int)
dd[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    ddOld = dd.copy()
    for dk, dv in ddOld.items():
        dd[dk+w] = max(dd[dk+w], dd[dk]+v)
ans = 0
for dk, dv in dd.items():
    if dk <= W:
        ans = max(ans, dv)
print(ans)

Submission status: Wrong Answer

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

w, v = map(int,input().split())
w0 = w
V[0].append(v)

for _ in range(N-1):
    w, v = map(int,input().split())
    V[w-w0].append(v)
for i in range(4):
    V[i].sort(reverse=True)
    for j in range(1,len(V[i])):
        V[i][j] = V[i][j-1]+V[i][j]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,W=map(int,raw_input().split())
wv=[]

for i in range(N):
	w,v=map(int,raw_input().split())
	wv.append((w,v))


dp=defaultdict(lambda: -1)	# Weight:Value
dp[0]=0

for w1,v1 in wv:
	for w,v in dp.items():
		dp[w+w1]=max( dp[w+w1], dp[w]+v1 )


l1=filter(lambda x:x[0]<=W , dp.items())
print sorted(l1, key=lambda x: x[1],reverse=True)[0][1]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,W=map(int,raw_input().split())
wv=[]

for i in range(N):
	w,v=map(int,raw_input().split())
	wv.append((w,v))


dp=defaultdict(lambda: 0)	# Weight:Value
dp[0]=0

for w1,v1 in wv:
	for w,v in dp.items():
		dp[w+w1]=max( dp[w+w1], dp[w]+v1 )



l1=filter(lambda x:x[0]<=W , dp.items())
print sorted(l1, key=lambda x: x[1],reverse=True)[0][1]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,W=map(int,raw_input().split())
wv=[]

for i in range(N):
	w,v=map(int,raw_input().split())
	wv.append((w,v))


dp=defaultdict(lambda: 0)	# Weight:Value
dp[0]=0

for w1,v1 in wv:
	for w,v in dp.items():
		dp[w1]=max( dp[w1], v1 )
		dp[w+w1]=max( dp[w+w1], dp[w]+v1 )



l1=filter(lambda x:x[0]<=W , dp.items())
print sorted(l1, key=lambda x: x[1],reverse=True)[0][1]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,W=map(int,raw_input().split())
wv=[]

for i in range(N):
	w,v=map(int,raw_input().split())
	wv.append((w,v))


dp=defaultdict(lambda: 0)	# Weight:Value
for w1,v1 in wv:

	if len(dp)==0:
		dp[w1]=v1
	else:
		for w,v in dp.items():
			dp[w1]=max( dp[w1], v1 )
			dp[w+w1]=max( dp[w+w1], dp[w]+v1 )


l1=filter(lambda x:x[0]<=W , dp.items())
if len(l1)==0:
	print 0
else:
	print sorted(l1, key=lambda x: x[1],reverse=True)[0][1]

Submission status: Wrong Answer

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

w0 = items[0][0]
memo = [{} for i in range(N + 1)]

memo[0] = {0: 0}
for i, (wi, vi) in enumerate(items):
    for w, v in memo[i].items():

        if w + wi <= W:
            memo[i + 1][w + wi] = v + vi

        memo[i + 1][w] = max(memo[i + 1].get(w, 0), memo[i][w])

print(max(memo[N].values()))

Submission status: Wrong Answer

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


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


for i in range(1, W+1):
  for good_num, (w, v) in enumerate(goods):
    if w <= i and good_num not in dp[i-w][1] and dp[i][0] <= dp[i-w][0]+v:
      dp[i] = (dp[i-w][0]+v, dp[i-w][1].union( set([good_num])))

print(dp[W][0])

Submission status: Wrong Answer

Solution code:
import copy
N,W = [int(i) for i in input().split()]
w = [[0]*2]*N
k = [0]*N
k2 = [0]*N
G = 0
V=0
V_ans = 0
for i in range(N):
    w[i] = [int(n) for n in input().split()]
    k[i] = copy.deepcopy(w[i][1]/w[i][0])
k2 = copy.deepcopy(k)
while max(k2) != 0:
    k = copy.deepcopy(k2)
    G = 0
    V = 0
    while max(k) != 0:
        num = k.index(max(k))
        if G + w[num][0] <= W:
            G += w[num][0]
            V += w[num][1]
        k[num] = 0
    num = k2.index(max(k2))
    k2[num] = 0
    if V_ans < V:
        V_ans = V
print(V_ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
    
memo = {}

def nap(i, j):
    if i == 0:
        return 1
    
    if (i, j) in memo:
        return memo[i, j]
    elif j < w[i]:
        temp = nap(i-1, j)
    else:
        temp = max(nap(i-1, j), nap(i-1, j-w[i]) + v[i])
    
    memo[i,j] = temp
    
    return memo[i,j]

print(nap(N-1, W))

Submission status: Wrong Answer

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

N, W = map(int, input().split())
wl = [0]*N
vl = [0]*N
for i in range(N):
  wl[i], vl[i] = map(int, input().split())

dp = {}
for i in range(N):
  w, v = wl[i], vl[i]

  newdp = {}
  
  for ew, ev in dp.items():
    if ew not in newdp:
      newdp[ew] = ev
    else:
      newdp[ew] = max(dp[ew], ev)

    if ew + w not in dp:
      newdp[ew+w] = ev+v
    else:
      newdp[ew+w] = max(dp[ew+w], ev + v)

  if w not in dp:
    newdp[w] = v
  else:
    newdp[w] = max(dp[w], v)
    
  dp = newdp

ans = 0
for w, v in dp.items():
  if w <= W:
    ans = max(ans, v)
print(ans)
#print(sorted(list(dp.items())))

Submission status: Wrong Answer

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

dp = {}
for i in range(N):
  w, v = wl[i], vl[i]

  newdp = {}
  if w not in dp:
    newdp[w] = v
  else:
    newdp[w] = max(dp[w], v)

  
  for ew, ev in dp.items():
    if ew not in newdp:
      newdp[ew] = ev
    else:
      newdp[ew] = max(dp[ew], ev)
    
    if ew + w not in newdp:
      newdp[ew+w] = ev+v
    else:
      newdp[ew+w] = max(dp[ew+w], ev + v)
  dp = newdp

ans = 0
for w, v in dp.items():
  if w <= W:
    ans = max(ans, v)
print(ans)
print(dp)

Submission status: Wrong Answer

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

memo={}
def calc(p,w,v):
    if p==N:
        memo[(w,v)]=v
    else:
        if w+arr[p][0]>W:
            if (w,v) not in memo:
                memo[(w,v)]=calc(p+1,w,v)
        else:
            if (w,v) not in memo:
                memo[(w,v)]=max(calc(p+1,w,v),calc(p+1,w+arr[p][0],v+arr[p][1]))
    return memo[(w,v)]

print(calc(0,0,0))

Submission status: Wrong Answer

Solution code:

# input
NW = [int(x) for x in input().split(" ")]
N = NW[0]
W = NW[1]

wvs = []

for _ in range(N):
	wvs.append([int(x) for x in input().split(" ")])


# calc value par weight
for wv in wvs:
	wv.append(wv[1] / wv[0])

# sort with value par weight
wvs.sort(key=lambda x:x[2] * -1)

# add items into napsack greedy
w = 0
v = 0
for wv in wvs:
	if w + wv[0] > W:
		continue
	w += wv[0]
	v += wv[1]

print(v)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W0 = map(int, raw_input().split())
items = [map(int, raw_input().split()) for i in range(N)]
w0, _ = items[0]
dp = np.full((N, N*4), -1)
def dfs(i, W):
    if i < 0:
        return 0
    if W-N*w0 < 0:
        return 0
    if dp[i][W-N*w0] != -1:
        return dp[i][W-N*w0]
    w, v = items[i]
    res = dfs(i-1, W)
    if W >= w:
        res = max(res, dfs(i-1, W-w) + v)
    dp[i][W-N*w0] = res
    return res
print dfs(N-1, W0)

Submission status: Wrong Answer

Solution code:
class Data:
    def __init__(self):
        self.weight = 0
        self.value = 0


n, w = list(map(int, input().split(' ')))

value_list = []
for i in range(n):
    data = Data()
    data_w, data_v = map(int, input().split(' '))
    data.weight = data_w
    data.value = data_v
    value_list.append(data)
datalist = []
for i in range(2**n):
    data = Data()
    bit_str = bin(i)[2:]
    for j in range(len(bit_str)):
        if bit_str[j] == "1":
            data.weight += value_list[j].weight
            data.value += value_list[j].value
            if data.weight > w:
                break
    datalist.append(data)

oklist = [x for x in datalist if x.weight <= w]
print(max([x.value for x in oklist])) if len(oklist) != 0 else print(0)

Submission status: Wrong Answer

Solution code:
class Data:
    def __init__(self):
        self.weight = 0
        self.value = 0


n, w = list(map(int, input().split(' ')))

value_list = []
for i in range(n):
    data = Data()
    data_w, data_v = map(int, input().split(' '))
    data.weight = data_w
    data.value = data_v
    value_list.append(data)
datalist = []
for i in range(2**n):
    data = Data()
    bit_str = bin(i)[2:]
    for j in range(len(bit_str)):
        if bit_str[j] == "1":
            data.weight += value_list[j].weight
            data.value += value_list[j].value
    datalist.append(data)

oklist = [x for x in datalist if x.weight <= w]
print(max([x.value for x in oklist])) if len(oklist) != 0 else print(0)

Submission status: Wrong Answer

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

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

C = sorted(B, key=lambda x: x[0:1],reverse=True)
C0 = list()
C1 = list()
C2 = list()
C3 = list()

for i in range(A[0]):
    if C[i][0] == B[0][0]:
        C0.append(C[i])
    elif C[i][0] == B[0][0] + 1:
        C1.append(C[i])
    elif C[i][0] == B[0][0] + 2:
        C2.append(C[i])
    elif C[i][0] == B[0][0] + 3:
        C3.append(C[i])

N = min(100,round(A[1]/B[0][0]))

res = 0
L3 = min(len(C3),N) + 1
for i3 in range(L3):
    L2 = min(len(C2),N - i3) + 1
    for i2 in range(L2):
        L1 = min(len(C1),N - i3 - i2) + 1
        for i1 in range(L1):
            L0 = min(len(C0),N - i3 - i2 - i1) + 1
            for i0 in range(L0):
                
                V = 0
                W = 0
                for x3 in range(i3):
                    if A[1] >= W + C3[x3][0] and len(C3) >= x3:
                        W = W + C3[x3][0]
                        V = V + C3[x3][1]
                    else:
                        break
                for x2 in range(i2):
                    if A[1] >= W + C2[x2][0] and len(C2) >= x2:
                        W = W + C2[x2][0]
                        V = V + C2[x2][1]
                    else:
                        break
                for x1 in range(i1):
                    if A[1] >= W + C1[x1][0] and len(C1) >= x1:
                        W = W + C1[x1][0]
                        V = V + C1[x1][1]
                    else:
                        break
                for x0 in range(i0):
                    if A[1] >= W + C0[x0][0] and len(C0) >= x0:
                        W = W + C0[x0][0]
                        V = V + C0[x0][1]
                    else:
                        break
                res = max(res,V)

print(res)

Submission status: Wrong Answer

Solution code:
N, W = list(map(int, input().split()))
w0, v0 = list(map(int, input().split()))
w_dict = dict()
w_dict[w0] = [v0]
w_dict[w0+1] = list()
w_dict[w0+2] = list()
w_dict[w0+3] = list()

for _ in range(1, N):
    w, v = list(map(int, input().split()))
    w_dict[w].append(v)

w_dict[w0]   = sorted(w_dict[w0],   reverse=True)
w_dict[w0+1] = sorted(w_dict[w0+1], reverse=True)
w_dict[w0+2] = sorted(w_dict[w0+2], reverse=True)
w_dict[w0+3] = sorted(w_dict[w0+3], reverse=True)

max_sum_v = 0
for i_0 in range(len(w_dict[w0])):
    for i_1 in range(len(w_dict[w0+1])):
        for i_2 in range(len(w_dict[w0+2])):
            for i_3 in range(len(w_dict[w0+3])):
                sum_w = w0 * i_0 + (w0 + 1) * i_1 + (w0 + 2) * i_2 + (w0 + 3) * i_3
                if sum_w > W:
                    continue
                sum_v = sum(w_dict[w0][:i_0])   + \
                        sum(w_dict[w0+1][:i_1]) + \
                        sum(w_dict[w0+2][:i_2]) + \
                        sum(w_dict[w0+3][:i_3])
                max_sum_v = max(sum_v, max_sum_v)

print(max_sum_v)

Submission status: Wrong Answer

Solution code:
N, W = list(map(int, input().split()))
w0, v0 = list(map(int, input().split()))
w_dict = dict()
w_dict[w0] = [v0]
w_dict[w0+1] = list()
w_dict[w0+2] = list()
w_dict[w0+3] = list()

for _ in range(1, N):
    w, v = list(map(int, input().split()))
    w_dict[w].append(v)

w_dict[w0]   = sorted(w_dict[w0],   reverse=True)
w_dict[w0+1] = sorted(w_dict[w0+1], reverse=True)
w_dict[w0+2] = sorted(w_dict[w0+2], reverse=True)
w_dict[w0+3] = sorted(w_dict[w0+3], reverse=True)

max_sum_v = 0
for i_0 in range(len(w_dict[w0])):
    for i_1 in range(len(w_dict[w0+1])):
        for i_2 in range(len(w_dict[w0+2])):
            for i_3 in range(len(w_dict[w0+3])):
                sum_w = w0 * i_0 + (w0 + 1) * i_1 + (w0 + 2) * i_2 + (w0 + 3) * i_3
                if sum_w > W:
                    continue
                sum_v = sum(w_dict[w0][:i_0]) + \
                        sum(w_dict[w0+1][:i_1]) + \
                        sum(w_dict[w0+2][:i_2]) + \
                        sum(w_dict[w0+3][:i_3])
                max_sum_v = max(sum_v, max_sum_v)

print(max_sum_v)

Submission status: Wrong Answer

Solution code:

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

w = [0]
v = [0]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

#品物、重み→1〜N番目for i in range(N):
print(N,W)
for i in range(N):
	a,b = map(int, input().split())
	w.append(a)
	v.append(b)

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときは価値は0
    if i == 0:
        return 0
    #制約0のときも価値は0
    if W == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    if Wsum[i] <= W2:
        return Vsum[i]
        
    #i番目の品物をナップサックに入れるか入れないか
    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))

Submission status: Wrong Answer

Solution code:

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

wv = [[0 for i in range(2)] for j in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

wv.sort(reverse=True)

for i in range(N):
    Wsum[i+1] = Wsum[i] + wv[i+1][0]
    Vsum[i+1] = Vsum[i] + wv[i+1][1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときは価値は0
    if i == 0:
        return 0
    #制約が0のときも価値は0
    if W2 == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は入れられない
    if W2 < wv[i][0]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-wv[i][0])+wv[i][1] , nap(i-1,W2) )
    
            
print(nap(N,W))