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: Accepted

Solution code:
def main():
    n, w = map(int, input().split(" "))
    items = []
    for _ in range(n):
        items.append(list(map(int, input().split(" "))))

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

    for i in range(n):
        val = items[i][0]
        wei = items[i][1]
        for j in range(w + 1):
            if i == 0:
                if j >= wei:
                    memo[i][j] = val
            else:
                if j >= wei:
                    memo[i][j] = max(
                        memo[i - 1][j],
                        memo[i - 1][j - wei] + val,
                    )
                else:
                    memo[i][j] = memo[i - 1][j]
    return memo[n - 1][w]


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

Submission status: Accepted

Solution code:
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態に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]

n,q = map(int,input().split()) 
li = [input().split() for i in range(n)]
w=[0]*n
v=[0]*n
for i in range(n):
  v[i]=int(li[i][0])
  w[i]=int(li[i][1])
print(knapsack(n,q,w,v))

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
VW  = [list(map(int, input().split())) for _ in range(N)]
VW  = sorted(VW, key=lambda x:x[1])
# print(VW)
# exit()

# dp = [0] * (W+1) # $B2ACM$N:GBgCM(B
dp = [ [0] * (W+1) for _ in range(N+1)]  # item, omosa

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

        dp[i+1][w] = max(dp[i+1][w] , dp[i][w])


# print( (dp[N]) )
print( max(dp[N]) )

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

t = [tuple(map(int, input().split())) for _ in range(n)]

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W=list(map(int, input().split()))
v=[list(map(int, input().split())) for i in range(N)]
v.sort(key=lambda x: x[1])
q=[[0 for i in range(W+1)] for j in range(N+1)]


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

Submission status: Accepted

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

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

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

res = -1
for i in range(W+1):
    for j in range(N+1):
        res = max(res, dp[j][i])

print(res)

Submission status: Accepted

Solution code:
def dump(dp, max_n, max_w):
    for n in range(max_n + 1):
        for i in range(max_w + 1):
            print('%3d' % dp[n][i], end='')
        print()
    print()

inf = 1 << 60
max_n, max_w = map(int, input().split())
v = [0] * (max_n + 1)
w = [0] * (max_n + 1)
for i in range(1, max_n + 1):
    v[i], w[i] = map(int, input().split())

dp = [[0] * (max_w + 1) for _ in range(max_n + 1)]

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

for n in range(1, max_n + 1):
    # if not selected
    for i in range(max_w + 1):
        dp[n][i] = max(dp[n][i], dp[n-1][i])
    # if selected
    for i in range(max_w + 1 - w[n]):
        dp[n][i+w[n]] = max(dp[n][i+w[n]], dp[n-1][i] + v[n])
    #dump(dp, max_n, max_w)

print(dp[max_n][max_w])

Submission status: Accepted

Solution code:
from typing import Callable


class DynamicProgramming(object):

    table: list
    obj_coef: list
    sbj_coef: list

    def __init__(self, item_n: int, border: int):
        self.item_n = item_n
        self.border = border

    def __str__(self):
        return "\n".join(list(map(lambda l:
                                  " ".join(list(map(str, l)))
                                  , self.table)))

    def __repr__(self):
        return "DynamicProgramming object:\n" + \
               "item_n: " + str(self.item_n) + ", border: " + str(self.border) + "\n" +\
               "table:\n" + self.__str__()

    def solve(self, obj_coef: list, sbj_coef: list, expr: Callable[[int, int], int], initializer=0) -> list:
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

        if len(obj_coef) == self.item_n:  # to 1-base
            obj_coef = [None] + obj_coef
        self.obj_coef = obj_coef

        if len(sbj_coef) == self.item_n:
            sbj_coef = [None] + sbj_coef
        self.sbj_coef = sbj_coef

        for weight_lim in range(1, self.border + 1):
            for item_idx in range(1, self.item_n + 1):
                self.table[weight_lim][item_idx] = expr(weight_lim, item_idx)

        return self.table

    def knapsack_expr(self, weight_lim: int, item_idx: int) -> int:
        res = self.table[weight_lim][item_idx - 1]
        if weight_lim - self.sbj_coef[item_idx] >= 0:
            res = max(res, self.table[weight_lim - self.sbj_coef[item_idx]][item_idx - 1] + self.obj_coef[item_idx])
        return res


if __name__ == '__main__':
    N, W = map(int, input().split())
    v, w = [], []
    for i in range(N):
        buff = [int(j) for j in input().split()]
        v.append(buff[0])
        w.append(buff[1])

    dp = DynamicProgramming(N, W)
    print(dp.solve(v, w, dp.knapsack_expr)[W][N])

Submission status: Accepted

Solution code:
class Item(object):
    def __init__(self, value, weight):
        self.v = value
        self.w = weight


n, W = map(int, input().split())
dp = [[-1] * (W + 1) for i in range(n + 1)]
items = [[int(x) for x in input().split()] for j in range(n)]


def rec_dp(i: int, w: int) -> int:
    if dp[i][w] != -1:
        return dp[i][w]

    result = 0
    if i < 0:
        pass
    else:
        item = Item(items[i][0], items[i][1])
        if w - item.w < 0:
            result = rec_dp(i - 1, w)
        else:
            result = max(
                rec_dp(i - 1, w),
                rec_dp(i - 1, w - item.w) + item.v
            )

    dp[i][w] = result
    return result


def main() -> None:
    print(rec_dp(n - 1, W))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import sys
from operator import itemgetter

# N, K = map(int, input().split())
# h = list(map(int, input().split()))
# S = [input() for _ in range(H)]
# X = [[0 for j in range(100)] for i in range(200)]


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

### solve
dp = [[0 for j in range(10001)] for i in range(101)]

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

print(dp[N][W])

Submission status: Accepted

Solution code:
N, W = [int(x) for x in input().split()]

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

for i in range(1, N + 1):
    v, w = [int(x) for x in input().split()]
    for j in range(W + 1):
        if j < w:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)

print(dp[N][W])

Submission status: Accepted

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

for i in range(N):
    for w in range(W+1):
        if weight[i]<=w:
            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: Accepted

Solution code:
#!/usr/bin/env python3
# DPL_1_B: Combinatorial - 0-1 Knapsack Problem

from operator import itemgetter


def max_value(total_weight, items):
    values = [0] * (total_weight+1)

    for v, w in sorted(items, key=itemgetter(1)):
        for i in reversed(range(w, total_weight+1)):
            values[i] = max(values[i], values[i-w] + v)

    return values[-1]


def run():
    n, t = [int(i) for i in input().split()]
    vs = []

    for _ in range(n):
        v, w = [int(i) for i in input().split()]
        vs.append((v, w))

    print(max_value(t, vs))


if __name__ == '__main__':
    run()

Submission status: Accepted

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

for i in range(n):
    items.append(list(map(int, input().split())))


def knapsack(n, w, items):
    c = [[0 for i in range(w + 1)] for j in range(n + 1)]
    g = [["TOP" for i in range(w + 1)] for j in range(n + 1)]

    for i in range(w + 1):
        c[0][i] = 0
        g[0][i] = "DIAGONAL"

    for i in range(n + 1):
        c[i][0] = 0

    for i in range(1, n + 1):
        for j in range(1, w + 1):
            c[i][j] = c[i - 1][j]
            g[i][j] = "TOP"
            item = items[i - 1]
            if item[1] > j:
                continue
            if item[0] + c[i - 1][j - item[1]] > c[i - 1][j]:
                c[i][j] = item[0] + c[i - 1][j - item[1]]
                g[i][j] = "DIAGONAL"

    max_value = c[n][w]
    routes = []
    for i in range(n, 0, -1):
        if g[i][w] == "DIAGONAL":
            routes.append(i)
            w -= items[i - 1][1]

    return max_value, routes


result, _ = knapsack(n, w, items)
print(result)

Submission status: Accepted

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

N, W = [int(t) for t in input().split()]
item = [tuple(int(t) for t in input().split()) for _ in range(N)]

# value[u] = 品物 0〜i だけ, かつ容量 u での最大価値
value = {u: 0 for u in range(W + 1)}

# 品物の種類をだんだん増やす
for v, w in item:
    value = {u: (max(value[u - w] + v, value[u]) if u >= w else value[u])
             for u in range(W + 1)}

print(value[W])

Submission status: Accepted

Solution code:
n, w = map(int, input().split(" "))
value, weight = zip(*[list(map(int, input().split(" "))) for _ in range(n)])

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

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

# [print(dp_i) for dp_i in dp]
print(dp[n][w])

Submission status: Accepted

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

dp = {(N, j):0 for j in range(W + 1)}

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

print(dp[(0, W)])

Submission status: Accepted

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

Submission status: Accepted

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

value = []
weight = []

for _ in range(n):
  vi , wi = map(int,input().split())
  value.append(vi)
  weight.append(wi)

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

for i in range(n):
  for j in range(w, weight[i] - 1, -1):
    #前者は品物を選択しない、　後者は品物を選択する
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

print(dp[w])

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
val_i = [0]*(W+1)
for i in range(1,N+1):
    v,w = map(int, input().split())
    copy = val_i[:] ##i-1번째줄의 val_i
    for j in range(1,W+1):
        if (w <= j):
            val_i[j] = max((v + copy[j-w]), copy[j])
print(val_i[-1])

Submission status: Accepted

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

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


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

    for i in range(W+1):
        dp[N][i] = 0
    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])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight


def conpute(N, W, items):
    c = [[None] * (W + 1) for i in range(N + 1)]
    c[0] = [0] * (W + 1)
    for i in range(1, N + 1):
        c[i][0] = 0
    
    for i in range(1, N + 1):
        for w in range(1, W + 1):
            c[i][w] = c[i - 1][w]
            if items[i].weight > w:
                continue
            if items[i].value + c[i - 1][w - items[i].weight] > c[i - 1][w]:
                c[i][w] = items[i].value + c[i - 1][w - items[i].weight]

    maxValue = c[N][W]

    return maxValue

if __name__ == '__main__':
    N, W = [int(v) for v in input().split()]
    items = [Item(0, 1 << 30)]
    for i in range(N):
        v, w = [int(v) for v in input().split()]
        items.append(Item(v, w))
    print(conpute(N, W, items))

Submission status: Accepted

Solution code:
n, w = [int(i) for i in input().split()]
V, W = zip(*[[int(i) for i in input().split()] for j in range(n)])

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

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

print(dp[n][w])

Submission status: Accepted

Solution code:
N, W = map( int, input().split())
VS, WS = [], []
for _ in range(N):
    a, b = map( int, input().split())
    VS.append(a)
    WS.append(b)
dp = [ [ 0 for _ in range(10**5+1)] for _ in range(N+1) ]
for i in range(N):
    w = WS[i]
    v = VS[i]
    for j in range(W+1):
        if w <= j:
            dp[i+1][j] = max( dp[i][j-w] + v, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[N][W])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
vw = (map(int, input().split()) for _ in range(N))
values, weights = zip(*vw)
dp = [[0] * (W + 1) for _ 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:
N, W = map(int, input().split())
values = []
weights = []
for _ in range(N):
    vi, wi = map(int, input().split())
    values.append(vi)
    weights.append(wi)

dp = [0 for _ in range(W+1)]
for i in range(N):
    for w in range(W, 0, -1):
        if w - weights[i] >= 0:
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
print(dp[W])

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
vw = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n+1)]

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

print(dp[0][w])

Submission status: Accepted

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

value  = []
weight = []

for i in range(N):
	x,y = map(int,raw_input().split())
	value.append(x)
	weight.append(y)
	
dp = [[0 for i in range(W_max+1)] for j in range(N+1)]


for i in range(0,N):
	for w in range(W_max+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_max]

Submission status: Accepted

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


'''
dp[i+1][ww]: i番目までの品物から容量がwを超えないように入れた時の価値の合計の最大値
0 <= ww <= W
0 <= i <= N
'''
# dp table
# (N+1)*(W+1)
dp = [[0]*(W+1)] # dp[0][ww]

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
import numpy as np

n, W = map(int, input().split())
value = np.empty(110)
weight = np.empty(110)

dp = np.empty(110,10010)

for el in range(n):
    value[el], weight[el] = map(int, input().split())

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

Solution code:
import numpy as np

n, W = map(int, input().split())
value = np.empty(110, dtype = 'int8')
weight = np.empty(110, dtype = 'int8')

dp = np.empty((110,10010), dtype = 'int8')

for el in range(n):
    value[el], weight[el] = map(int, input().split())

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

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

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

print(dp[W])

Submission status: Runtime Error

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

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

print(dp[W])

Submission status: Runtime Error

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

for i in range(N):
    n , m = map(input())
    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: Runtime Error

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

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

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

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

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

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

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

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

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

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][sgn(c-lst[i-1][1])]+lst[i-1][0]*heav(c-lst[i-1][1]))
print(table[N][W])

Submission status: Runtime Error

Solution code:
#引数が非負ならそのまま、負なら0を返す
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(" "))) #[v,w]の順で格納
    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][sgn(c-lst[i-1][1])]+lst[i-1][0]*heav(c-lst[i-1][1]))
print(table[N][W])

Submission status: Runtime Error

Solution code:
def weight(n, p, c):
    global count
    global m
    
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(weight(n - c[0], p + 1, c), weight(n, p, c[1:]))
    else:
        return weight(n, p, c[1:])

N, W = map(int, input().split())
lisv = []
lisw = []

for i in range(n):
    v, w = map(int, input().split())
    lisv.append(v)
    lisw.append(w)

for j in range(n):
    pass
print(weight(N, 0, lisw))

#print(coin(n, 0, mon))

Submission status: Runtime Error

Solution code:
def weight(n, p, c):
    global count
    global m
    
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(weight(n - c[0], p + 1, c), weight(n, p, c[1:]))
    else:
        return weight(n, p, c[1:])

N, W = map(int, input().split())
lisv = []
lisw = []

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

for j in range(N):
    pass
print(weight(N, 0, lisw))

#print(coin(n, 0, mon))

Submission status: Runtime Error

Solution code:
def weight(n, p, c):
    global count
    global m
    
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(weight(n - c[0], p + 1, c), weight(n, p, c[1:]))
    else:
        return weight(n, p, c[1:])

N, W = map(int, input().split())
lisv = []
lisw = []

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

for j in range(N):
    pass

count = N
print(weight(N, 0, lisw))

#print(coin(n, 0, mon))
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

Submission status: Runtime Error

Solution code:
'''
def weight(n, p, c):
    global count
    global m
    
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(weight(n - c[0], p + 1, c), weight(n, p, c[1:]))
    else:
        return weight(n, p, c[1:])

N, W = map(int, input().split())
lisv = []
lisw = []

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

for j in range(N):
    pass

count = N
print(weight(N, 0, lisw))

#print(coin(n, 0, mon))
'''
def x(x):
    return(x(x))
print(x(1))

Submission status: Runtime Error

Solution code:
'''
def weight(n, p, c):
    global count
    global m
    
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(weight(n - c[0], p + 1, c), weight(n, p, c[1:]))
    else:
        return weight(n, p, c[1:])

N, W = map(int, input().split())
lisv = []
lisw = []

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

for j in range(N):
    pass

count = N
print(weight(N, 0, lisw))

#print(coin(n, 0, mon))
'''
def x(x):
    return(x(x))
print(x('1'))

Submission status: Runtime Error

Solution code:
'''
def weight(n, p, c):
    global count
    global m
    
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(weight(n - c[0], p + 1, c), weight(n, p, c[1:]))
    else:
        return weight(n, p, c[1:])

N, W = map(int, input().split())
lisv = []
lisw = []

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

for j in range(N):
    pass

count = N
print(weight(N, 0, lisw))

#print(coin(n, 0, mon))
'''
def x(x):
    return(x(x))
print(x(None))

Submission status: Runtime Error

Solution code:
'''
def weight(n, p, c):
    global count
    global m
    
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(weight(n - c[0], p + 1, c), weight(n, p, c[1:]))
    else:
        return weight(n, p, c[1:])

N, W = map(int, input().split())
lisv = []
lisw = []

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

for j in range(N):
    pass

count = N
print(weight(N, 0, lisw))

#print(coin(n, 0, mon))
'''
def x(x):
    return(x(x))
print(x(x))

Submission status: Runtime Error

Solution code:
'''
def weight(n, p, c):
    global count
    global m
    
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(weight(n - c[0], p + 1, c), weight(n, p, c[1:]))
    else:
        return weight(n, p, c[1:])

N, W = map(int, input().split())
lisv = []
lisw = []

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

for j in range(N):
    pass

count = N
print(weight(N, 0, lisw))

#print(coin(n, 0, mon))
'''
def J(x):
    return(J(x))
print(J(3))

Submission status: Runtime Error

Solution code:
from sys import *

def ans()
    W = int(input().split()[1])
    C = [0] *-~ W

    for e in stdin:
        v,w=map(int,e.split())

    for i in range(W, w-1, -1):
        t = v + C[i - w]

    if t > C[i]:
        C[i] = t

    print(C[W])

ans()

Submission status: Runtime Error

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

values = [0]
weights = [0]
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(len(values) + 1)]

for i in range(len(values)):
    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 + 1])

Submission status: Runtime Error

Solution code:
N,W=(int(x) for x in input().split())
t=0
weight=[0]*N
value=[0]*N
while t<N:
    v,w=(int(x) for x in input().split())
    value[t]=v
    weight[t]=w
    t=t+1
def kotae(N,W):
    dp=[[0 for i in range(110)] for j in range(110)]
    i=0
    while i<N:
        wei=0
        while wei<W+1:
            if wei>=weight[i]:
                dp[i+1][wei]=max(dp[i][wei],dp[i][wei-weight[i]]+value[i])
            else:
                dp[i+1][wei]=dp[i][wei]
            wei=wei+1
        i=i+1
    return dp[N][W]
print(kotae(N,W))

Submission status: Runtime Error

Solution code:



def dp(i, j):
    if dp_list[i][j] != -1:
        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 = 4
# W = 5
N, W = (int(x) for x in input().split())
# value, weightの順で並んでいる
lists = []
for i in N:
    lists += list(lambda x: int(x), input().split())
dp_list = [[-1] * (W + 1)] * (N + 1)

# lists = [[4, 2], [5, 2], [2, 1], [8, 3]]

print(dp(0, W))

Submission status: Runtime Error

Solution code:
#Nはアイテム数、Wはナップサックサイズ
N,W = map(int,input().split())
#dpテーブルを作成（初期値は0）
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

#print(dp)

#N個のアイテムのvalueとweightを入れるリストを用意する
value = []
weight = []
for i in range(N):
    v,w = map(int,input().split())
    value.append(v)
    weight.append(w)

#print(values)
#print(weights)

#アイテムは１個目からN個まで、重さのレンジは0からWまで
for i in range(1,N+1):
    for j in range(W+1):
        if j >= weight[i-1]: #iは1から始めているので、weightやvalueのリストを参照するときは添字を1つ下げる
            dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i-1][j-weight[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[N+1][W+1])