Problem:


0-1 Knapsack Problem

You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

The total value of the items is as large as possible.

The items have combined weight at most W, that is capacity of the knapsack.

Find the maximum total value of items in the knapsack.

Input

N W
v1 w1
v2 w2
:
vN wN

The first line consists of the integers N and W. In the following lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Constraints

 1 ≤ N ≤ 100
	

 1 ≤ vi ≤ 1000
	

 1 ≤ wi ≤ 1000
	

 1 ≤ W ≤ 10000
	

Sample Input 1

4 5
4 2
5 2
2 1
8 3

Sample Output 1

13

Sample Input 2

2 20
5 9
4 10

Sample Output 2

9



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


Sample output:
13

Submission status: Wrong Answer

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

n, max_w = [int(i) for i in input().split()]#print(n, max_w)

w = []
v = []
for j in range(n):
    weight,value=[int(i) for i in input().split()]
    w.append(weight)
    v.append(value)

dp = [[0 for i in range(max_w+1)] for j in range(n+1)]

for i in range(n):
    for cw in range(max_w+1):
        if cw >= w[i]:
            if cw == 8:
                print(i+1,cw,cw-w[i],i)
                print(dp[i+1][cw])
                print(dp[i][cw-w[i]])
                print(dp[i][cw])
            dp[i+1][cw] = max(dp[i][cw-w[i]]+v[i], dp[i][cw])
        else:
            dp[i+1][cw] = dp[i][cw]

Submission status: Wrong Answer

Solution code:
MAX_N = 100
MAX_W = 10000
dp =  list(list(-1 for j in range(MAX_W+1)) for i in range(MAX_N+1))

def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = (int(s) for s in input().split())
    vw = list(tuple(int(s) for s in input().split()) for i in range(n))
    print(str(rec(0, w)))

Submission status: Wrong Answer

Solution code:
def rec(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]
    if i == n:
        res = 0
    elif  j < vw[i][1]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1, j), rec(i+1, j-vw[i][1])+vw[i][0])
    dp[i][j] = res
    return res

def solve():
    n, w = tuple(int(s) for s in input().split())
    vw = list(tuple(int(s) for s in input().split()) for i in range(n))
    print("1")
#    print(str(rec(0, w)))

if __name__ == '__main__':
    MAX_N = 100
    MAX_W = 10000
    dp =  list(list(-1 for j in range(MAX_W+1)) for i in range(MAX_N+1))    
    solve()

Submission status: Wrong Answer

Solution code:
n, w = list(map(int,input().split()))
things=[]
for i in range(n):
    thing = list(map(int, input().split()))
    things.append(thing)

print(n, w)
print(things)
#n=6
#w=8
#things = [[2,3],[1,2],[3,6],[2,1],[1,3],[5,85]]

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

#for i in range(n+1):
#    for j in range(w+1):
#        dp[i][j]=0

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

print(dp[n][w])

Submission status: Wrong Answer

Solution code:
def cv(w, p, vi, wi):
    global value

    w0 = 0
    v0 = 0
    for i in range(len(vi)):
        w0 += wi[i]
        if w0 > w:
            if v0 <= value - p:
                return value
            break
        v0 += vi[i]
        
    if len(vi) == 1:
        value = max(value, p + vi[0] if wi[0] <= w else p)
        return value
    elif wi[0] <= w:
        value = max(value, p + vi[0])
        return max(cv(w - wi[0], p + vi[0], vi[1:], wi[1:]), cv(w, p, vi[1:], wi[1:]))
    else:
        return cv(w, p, vi[1:], wi[1:])

n, w = map(int, input().split())
c = []
for _ in range(n):
    c.append(tuple(map(int, input().split())))
c.sort(key = lambda x: x[0] / x[1], reverse = True)
vi, wi = zip(*c)
value = 0
print(cv(w, 0, vi, wi))

Submission status: Wrong Answer

Solution code:
import sys
def cv(w, p, vi, wi):
    global value

    w0 = 0
    v0 = 0
    for i in range(len(vi)):
        w0 += wi[i]
        if w0 >= w:
            if i == len(vi) -1 or v0 + vi[i + 1] <= value - p:
                return value
            value = max(value, p + v0)
            break
        v0 += vi[i]
        
    if len(vi) == 1:
        value = max(value, p + vi[0] if wi[0] <= w else p)
        return value
    elif wi[0] <= w:
        value = max(value, p + vi[0])
        return max(cv(w - wi[0], p + vi[0], vi[1:], wi[1:]), cv(w, p, vi[1:], wi[1:]))
    else:
        return cv(w, p, vi[1:], wi[1:])

n, w = map(int, input().split())
c = []
for _ in range(n):
    c.append(tuple(map(int, input().split())))
c.sort(key = lambda x: x[1])
c.sort(key = lambda x: x[0] / x[1], reverse = True)
vi, wi = zip(*c)
value = 0
print(cv(w, 0, vi, wi))

Submission status: Wrong Answer

Solution code:
def cv(w, p, vi, wi):
    global value
#   print(value)
#   print("{} {} {} {}".format(w, p, vi, wi))

    w0 = 0
    v0 = 0
    for i in range(len(vi)):
        w0 += wi[i]
        if w0 > w:
            if i == len(vi) -1 or v0 + vi[i + 1] <= value - p:
                return max(p + v0, value)
            value = max(value, p + v0)
            break
        v0 += vi[i]
        
    if len(vi) == 1:
        value = max(value, p + vi[0] if wi[0] <= w else p)
        return value
    elif wi[0] <= w:
        value = max(value, p + vi[0])
        return max(cv(w - wi[0], p + vi[0], vi[1:], wi[1:]), cv(w, p, vi[1:], wi[1:]))
    else:
        return cv(w, p, vi[1:], wi[1:])

n, w = map(int, input().split())
c = []
for _ in range(n):
    c.append(tuple(map(int, input().split())))
c.sort(key = lambda x: x[1])
c.sort(key = lambda x: x[0] / x[1], reverse = True)
vi, wi = zip(*c)
value = 0
print(cv(w, 0, vi, wi))

Submission status: Wrong Answer

Solution code:
def cv(w, p, vi, wi):
    global value
#    print(value)
#    print("{} {} {} {}".format(w, p, vi, wi))

    w0 = 0
    v0 = 0
    if sum(wi) <= w:
        value = max(value, p + sum(vi))
        return value
    for i in range(len(vi) - 1):
        w0 += wi[i]
        if w0 > w:
            if v0 + vi[i + 1] <= value - p:
                return max(p + v0, value)
            if i < len(vi) - 1 and w0 + wi[i + 1] <= w:
                v0 += vi[i + 1]
            value = max(value, p + v0)
            break
        v0 += vi[i]
        
    if len(vi) == 1:
        value = max(value, p + vi[0] if wi[0] <= w else p)
        return value
    elif wi[0] <= w:
        value = max(value, p + vi[0])
        return max(cv(w - wi[0], p + vi[0], vi[1:], wi[1:]), cv(w, p, vi[1:], wi[1:]))
    else:
        return cv(w, p, vi[1:], wi[1:])

n, w = map(int, input().split())
c = []
for _ in range(n):
    c.append(tuple(map(int, input().split())))
c.sort(key = lambda x: x[1])
c.sort(key = lambda x: x[0] / x[1], reverse = True)
vi, wi = zip(*c)
value = 0
print(cv(w, 0, vi, wi))

Submission status: Wrong Answer

Solution code:
import copy
input = map(int,raw_input().split())
num = input[0]
capacity = input[1]
dp = {}
dp[0] = 0
for i in range(0,num):
	line = map(int,raw_input().split())
	weight = line[1]
	value = line[0]
	dpsub = copy.copy(dp)
	for s in dp.keys() :
		if  s + weight <= capacity :
			if s + weight in dp.keys() :
				if dpsub[s + weight] < dp[s] + value :
					dp[s + weight] = dpsub[s] + value
			else :
			 	 dp[s + weight] = dpsub[s] + value 

max = 0 
for s in dp.keys() :
	if dp[s] > max :
		max = dp[s]

print max

Submission status: Wrong Answer

Solution code:
#問題2
#https://qiita.com/drken/items/a5e6fe22863b7992efdb
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
n, w = map(int,input().split())
value = []
weight = []

for i in range(n):
    val,wei = map(int,input().split())
    value.append(val)
    weight.append(wei)
    
#dp i <= 110, w <= 1010
dp = []
for i in range(110):
    o = [0 for i in range(1010)]
    dp.append(o)

#i = 0 何も入れない状態を初期化する

for ww in range(w):
    dp[0][ww] = 0

for i in range(n):
    for ww in range(w):
        #dp[i+1]に最終状態が格納される
        if ww >= weight[i] :
            dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[n][w])

Submission status: Wrong Answer

Solution code:
#問題2
#https://qiita.com/drken/items/a5e6fe22863b7992efdb
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
n, w = map(int,input().split())
value = []
weight = []

for i in range(n):
    val,wei = map(int,input().split())
    value.append(val)
    weight.append(wei)
    
#dp i <= 110, w <= 1010
dp = []
for i in range(110):
    o = [0 for i in range(1010)]
    dp.append(o)

#i = 0 何も入れない状態を初期化する

for ww in range(w):
    dp[0][ww] = 0

for i in range(n):
    for ww in range(w):
        #dp[i+1]に最終状態が格納される
        if ww >= weight[i] :
            dp[i+1][ww] = max(dp[i][ww-weight[i]] + value[i], dp[i][ww])
        else:
            dp[i+1][ww] = dp[i][ww]
print(dp[n][w-1])

Submission status: Wrong Answer

Solution code:
N, W = list(map(int, input().split()))
baggage = []
for i in range(N):
    a, b = list(map(int, input().split()))
    baggage.append((a, b))
DP = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
    #print('i = ', i)
    for j in range(baggage[i - 1][1], W + 1):
        #print(' j = ', j)
        DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - baggage[i - 1][1]] + baggage[i - 1][0])
        #for l in DP:
        #    print(l)
ans = 0
for i in DP:
    for j in i:
        if j > ans:
            ans = j
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())    # n: 物の個数 w: 重さの限界

weight = [0]*110
value = [0]*110

dp = [[0]*10010]*110
for i in range(N):
    value[i], weight[i] = map(int, input().split())

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

print(dp[N][W])

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())    # n: 物の個数 w: 重さの限界

weight = [-1]*110
value = [-1]*110

dp = [[-1]*110]*110
for i in range(N):
    value[i], weight[i] = map(int, input().split())

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

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

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())    # n: 物の個数 w: 重さの限界

weight = [-1]*110
value = [-1]*110

dp = [[-1]*110]*110
for i in range(N):
    value[i], weight[i] = map(int, input().split())

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

print(dp[N][W])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
vws = [list(map(int, input().split())) for _ in range(N)]
dp = [-1]*(W+1)
dp[0] = 0
used = [False]*N
def f(used, dp):
    if (dp[W] != -1):
        print(max(dp))
        exit()
    for d in range(W+1):
        if dp[d] == -1:
            continue
        for n in range(N):
            if (used[n]):
                continue
            b_used = used[::1]
            v,w = vws[n]
            if d+w < W+1:
                dp[d+w] = max(dp[d+w], dp[d]+v)
                b_used[n] = True
                f(b_used, dp)
f(used, dp)

Submission status: Time Limit Exceeded

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

v = [0] * N
w = [0] * N

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


def rec(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])
    return res

print(rec(0, W))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# re = open("input")
# input = re.readline
num, max_weight = map(int, input().split())
items = []
for i in range(num):
    v, w = map(int, input().split())
    items.append([v, w])

all_length = 1 << num
result = [0 for x in range(all_length)]
resultv = [0 for x in range(all_length)]

for pattern in range(all_length):
    all_weight = 0
    all_value = 0
    # print("%04d" % int(bin(pattern)[2:]), end=" ")
    tmppattern = pattern
    for i in range(num):
        if pattern & 1:
            all_value += items[i][0]
            all_weight += items[i][1]
            if all_weight > max_weight:
                all_weight -= items[i][1]
                all_value -= items[i][0]
                break
        pattern >>= 1
    result[tmppattern] = all_weight
    resultv[tmppattern] = all_value
#     print(all_weight, all_value)
# print(result)
print(max(resultv))

Submission status: Time Limit Exceeded

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

def rec(i, weight):
    if i == N:
        return 0
    elif weight + w[i] <= W:
        return max(rec(i+1, weight), rec(i+1, weight + w[i]) + v[i])
    else:
        return rec(i+1, weight)
print(rec(0, 0))

Submission status: Time Limit Exceeded

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


@functools.lru_cache(maxsize=None)
def rec(i, weight):
    if i == N:
        return 0
    elif weight + w[i] <= W:
        return max(rec(i+1, weight), rec(i+1, weight + w[i]) + v[i])
    else:
        return rec(i+1, weight)
print(rec(0, 0))

Submission status: Time Limit Exceeded

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


@functools.lru_cache(maxsize=1 << 20)
def rec(i, weight):
    if i == N:
        return 0
    elif weight + w[i] <= W:
        return max(rec(i+1, weight), rec(i+1, weight + w[i]) + v[i])
    else:
        return rec(i+1, weight)
print(rec(0, 0))

Submission status: Time Limit Exceeded

Solution code:
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n:
		return(0)
	elif w-l[i][0]<0:
		return(solve(i+1,w))
	else:
		a=solve(i+1,w)
		b=l[i][1]+solve(i+1,w-l[i][0])
		if b>a:
			return(b)
		else:
			return(a)

print(solve(0,W))

Submission status: Time Limit Exceeded

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

def judge(now,weight,value):

    if now == N-1:
        if weight+w[now] <= W:
            return value+v[now]
        elif weight <= W:
            return value
        else:
            return 0
    else:
        return max(judge(now+1,weight+w[now],value+v[now]),judge(now+1,weight,value))


r=judge(0,0,0)
print(r)

Submission status: Time Limit Exceeded

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

def judge(now,weight,value):
    if weight > W:
        return 0
    if now == N-1:
        if weight+w[now] <= W:
            return value+v[now]
        elif weight <= W:
            return value
        
    else:
        return max(judge(now+1,weight+w[now],value+v[now]),judge(now+1,weight,value))


r=judge(0,0,0)
print(r)

Submission status: Time Limit Exceeded

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

def rec(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])
    return res

print(rec(0, W))

Submission status: Time Limit Exceeded

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

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

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

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])
    return res

print(rec(0, W))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

def rec(i,j,dp):
    res = 0
    if dp[i][j] > 0:
        return dp[i][j]
    if i<0:
        return 0
    elif j < w[i]:
        res = rec(i-1, j, dp)
    else:
        res = max(rec(i-1,j,dp),rec(i-1, j-w[i],dp)+v[i])

    return res
print(rec(N-1,W,dp))

Submission status: Time Limit Exceeded

Solution code:

N,W = map(int, input().split())
v = [0] * N
w = [0] * N
dp = [[-1]*(W+1)]*(N+1)

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

def rec(i,j,dp):
    res = 0
    if dp[i][j] != -1:
        return dp[i][j]
    if i<0:
        return 0
    elif j < w[i]:
        res = rec(i-1, j, dp)
    else:
        res = max(rec(i-1,j,dp),rec(i-1, j-w[i],dp)+v[i])

    return res
print(rec(N-1,W,dp))

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    [N,W]=input().split(" ")
    '''read from keyboard and put all the item to box'''
    N=int(N)
    W=int(W)
    box=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        box.append([float(vi),float(wi)])
        
    assemblebox=[]
    '''creat a set of full permutation of input. using recursion'''
    assemblebox=permutations(N,box,assemblebox,[])

    maximum=0
    '''optimization'''
    for i in range(len(assemblebox)):
        weight=0
        value=0
        for j in range(N):
            weight=weight+assemblebox[i][j][1]
            if(weight>W):
                break
            value=value+assemblebox[i][j][0]
        if(maximum<value):
            maximum=value
            
    print(int(maximum))
    '''output'''
        

    return 0

def permutations(N,box,assemblebox,record):
    for i in range(N):
        Np=N
        boxp=copy.deepcopy(box)
        recordp=copy.deepcopy(record)
        recordp.append(box[i])
        boxp.pop(i)
        Np=Np-1
        if(Np==0):
            assemblebox.append(recordp)
        else:
            result=permutations(Np,boxp,assemblebox,recordp)
    return assemblebox

main()

Submission status: Time Limit Exceeded

Solution code:
def cv(w, p, vi, wi):
    global value
    if len(vi) == 1 or w < min(wi):
        value = max(value, p + vi[0] if wi[0] <= w else p)
        return value
    elif p + sum(vi) <= value:
        return 0
    elif wi[0] <= w:
        value = max(value, p + vi[0])
        return max(cv(w - wi[0], p + vi[0], vi[1:], wi[1:]), cv(w, p, vi[1:], wi[1:]))
    else:
        return cv(w, p, vi[1:], wi[1:])

n, w = map(int, input().split())
c = []
for _ in range(n):
    c.append(tuple(map(int, input().split())))
c.sort(key = lambda x: x[0] / x[1], reverse = True)
vi, wi = zip(*c)
value = 0
print(cv(w, 0, vi, wi))

Submission status: Memory Limit Exceeded

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

all_length = 1 << num
results = list(range(all_length))
results[0] = (0, 0)

now_digit = 1
calc_digit = 0
digit_count = -1
for pattern in range(1, all_length):
    if pattern & now_digit:
        calc_digit = now_digit - 1
        now_digit <<= 1
        digit_count += 1

    results[pattern] = \
            items[digit_count][0] + results[pattern & calc_digit][0], \
            items[digit_count][1] + results[pattern & calc_digit][1]
print(max([x[0] for x in results if x[1] <= max_weight]))

Submission status: Memory Limit Exceeded

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

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

Submission status: Accepted

Solution code:

N,MaxW = list(map(int,input().split()))

V = []
W = []

for i in range(N):
    v,w = list(map(int,input().split()))
    V.append(v)
    W.append(w)
    
dp = [[0]*(MaxW+1) for i in range(N+1)]

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


print(dp[N][MaxW])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

val_wei = [list(map(int, input().split())) for i in range(N)]

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

for n in range(N):
    for w in range(W+1):
        if w >= val_wei[n][1]:
            dp[n+1][w] = max(dp[n][w-val_wei[n][1]] + val_wei[n][0], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]

print(dp[N][W])

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
# dp=[[0 for i in range(N)] for j in range(W)]
dp =[[0 for j in range(W+1)]for i in range(N+1)]
v = []
w = []
for i in range(N):
    temp_v,temp_w = map(int,input().split())
    v.append(temp_v)
    w.append(temp_w)
    # if temp_w<=W:#一回配ってみる
    #     dp[temp_w] = temp_v
# print(dp[4][1])
ans = 0
for i in range(1,N+1):
    for j in range(1,W+1):
        if (j-w[i-1])<0:
            dp[i][j] = dp[i-1][j] 
        else:
            # print("i,j={},{}".format(i,j))
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
            # print("dp[i-1][j] = {}".format(dp[i-1][j]))
            # print("dp[i-1][j-w[i-1]] = {}".format(dp[i-1][j-w[i-1]]+v[i-1]))
            ans = max(ans,dp[i][j])
print(ans)

Submission status: Accepted

Solution code:
n, W = tuple(map(int, input().split()))
vw = [tuple(map(int, input().split())) for _ in range(n)]

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

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

print(max([max(e) for e in dp]))

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
#item =[]
# for i in range[n]:
#     item = list(map(int, input().split()))
value =[]
weight = []
dp = [[0 for i in range(W + 1)]for j in range(n + 1)]

for el in range(n):
    x, y = map(int, input().split())
    value.append(x)
    weight.append(y)

for w in range(W):
    dp[0][w] = 0

for i in range(n):
    for w in range(W + 1):
        if w >= weight[i]:
            #dp[i + 1][w]はi番目の品物の中から重さがwを超えないように選んだ時の、価値の総和の最大値
            dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i] , dp[i][w])
            #その品物を選ぶか選ばないか判定する前のその重さの時の価値の最大値が既に分かっているので、判定するものの重量を差し引いた時の価値の最大値と判定しているものの価値を足し合わせて、
            #判定する前のその時点(w)での元からある価値の最大値（dp[i][w]と比べている
            #DP表には価値の最大値が書いてあり、組み合わせを記述するわけではない
        else:
            dp[i + 1][w] = dp[i][w]

print(dp[n][W])

Submission status: Accepted

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

for i in range(N):
    n , m = map(int,input().split())
    for j in range(W,m-1,-1):
        x = n + dp[j-m]
        if x >= dp[j]:
            dp[j] = x
            
print(dp[W])

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    value = []
    weight = []
    for i in range(N):
        a, b = map(int, input().split())
        value.append(a)
        weight.append(b)
    dp = [[-float("inf") for i in range(W+1)] for j in range(N+1)]
    for w in range(W+1):
        dp[0][w] = 0

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

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def get_max_value(n, W, v, w):
	dp = [[0 for x in range(W+1)] for x in range(n+1)]
	for i in range(1, n+1):
		wt = w[i-1]
		vl = v[i-1]
		for j in range(W+1):
			if wt > j:
				dp[i][j]=dp[i-1][j]
			else:
				dp[i][j]=max(dp[i-1][j], dp[i-1][j-wt]+vl)
	return dp[n][W]

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())
print(get_max_value(n, W, v, w))

Submission status: Accepted

Solution code:
def get_max_value(n, W, v, w):
	dp = [[0 for x in range(W+1)] for x in range(n+1)]
	for i in range(1,n+1):
		wt = w[i-1]
		vl = v[i-1]
		for j in range(1,W+1):
			if wt > j:
				dp[i][j]=dp[i-1][j]
			else:
				dp[i][j]=max(dp[i-1][j], dp[i-1][j-wt]+vl)
	return dp[n][W]

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())
print(get_max_value(n, W, v, w))

Submission status: Accepted

Solution code:
N, W = (int(i) for i in input().split())
bagage = [[int(i) for i in input().split()] for _ in range(N)]
weight = []
value = []
for b in bagage:
    value.append(b[0])
    weight.append(b[1])

dp = [[0]*10010 for i in range(110)]

for j in range(W):
    dp[N][j] = 0

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

print(dp[0][W])

Submission status: Accepted

Solution code:
def ramp(t):
    if t >= 0:
        return t
    else:
        return 0
def heav(t):
    if t >= 0:
        return(1)
    else:
        return(0)
N,W = map(int,input().strip().split(" "))
lst = []
for i in range(N):
    l = list(map(int,input().strip().split(" ")))
    lst.append(l)
table = [[0 for c in range(W+1)] for i in range(N+1)]
for i in range(1,N+1):
    for c in range(1,W+1):
        table[i][c] = max(table[i-1][c],table[i-1][ramp(c-lst[i-1][1])]+lst[i-1][0]*heav(c-lst[i-1][1]))
print(table[N][W])

Submission status: Accepted

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

    
for i in range(N):
    v=goods[i][0]
    w=goods[i][1]
    for j in range(W+1):
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        next_w=j+w
        next_v=dp[i][j]+v
        if(next_w<=W and next_v>dp[i+1][next_w]):
            dp[i+1][next_w]=next_v

ans=0
for i in range(W+1):
    ans=max(ans,dp[N][i])
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
item = [list(map(int, input().split())) for i in range(N)]
dp = [0 for i in range(W+2)]
for v in item:
  for i in range(1, W+2):
    if W + 1 - i + v[1] <= W:
      dp[W + 1 - i + v[1]] = max(dp[W + 1 - i + v[1]] , dp[W + 1 - i] + v[0])
print(dp[W])

Submission status: Accepted

Solution code:
def Knapsack(N, W, vs, ws):
    dp = [[0 for n in range(W+1)] for w in range(N+1)]

    for n in range(N):
        for w in range(W+1):
            if (w >= ws[n]):
                dp[n+1][w] = max(dp[n][w-ws[n]] + vs[n], dp[n][w])
            else:
                dp[n+1][w] = dp[n][w]

    return dp[N][W]

N, W = map(int, input().split(' '))
vs, ws = [0] * N, [0] * N
for n in range(N):
    vs[n], ws[n] = map(int, input().split(' '))

ans = Knapsack(N, W, vs, ws)
print(ans)

Submission status: Accepted

Solution code:
#AOJ
N,W=map(int,input().split())
data=[]
for i in range(N):
    v,w=map(int,input().split())
    data.append((v,w))
ans={0:0}
for i in data:
    ans1=ans.copy()
    for v in ans:
        if i[1]+v in ans.keys():
            ans1[i[1]+v]=max(ans[i[1]+v],ans[v]+i[0])
        else:
            ans1[i[1]+v]=ans[v]+i[0]
    ans=ans1
maxv=0
for i in ans:
    if i<=W and ans[i]>maxv:
        maxv=ans[i]
print(maxv)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())

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

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

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

print(dp[n][w])

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B
def dp(i, j):
    if dp_list[i][j] != 0:
        return dp_list[i][j]
    if i == len(lists):
        return 0
    if j < lists[i][1]:
        dp_list[i][j] = dp(i + 1, j)
        return dp_list[i][j]
    else:
        dp_list[i][j] = max(dp(i + 1, j), dp(i + 1, j - lists[i][1]) + lists[i][0])
        return dp_list[i][j]


N, W = (int(x) for x in input().split())
# value, weightの順で並んでいる
lists = []
for i in range(N):
    lists.append(list(map(lambda x: int(x), input().split())))
dp_list = [[0 for i in range(W + 1)] for j in range(N + 1)]
print(dp(0, W))