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 knapsack(N, W, l):    
    dp = [[0]*(W+1) for _ in range(N+1)]
    for j in range(1, W+1):
        for i in range(1, N+1):
            v = l[i-1][0]
            w = l[i-1][1]
            if j-w < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
    return dp[N][W]

N, W = [int(_) for _ in input().split()]
l = [[0]* 2 for _ in range(N)]
for i in range(N):
    l[i][0],l[i][1] = [int(_) for _ in input().split()]
ans = knapsack(N, W, l)
print(ans)

Submission status: Accepted

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

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

Solution code:
def main():
    N, W = (int(i) for i in input().split())
    v = []
    w = []
    for i in range(N):
        a, b = (int(i) for i in input().split())
        v.append(a)
        w.append(b)
    done = [[False for i in range(W+1)] for j in range(N+1)]
    memo = [[0 for i in range(W+1)] for j in range(N+1)]

    def dp(i,u):
        if done[i][u]: 
            return memo[i][u]
        if i == N:
            return 0
        elif u < w[i]:
            return dp(i + 1, u)
        else:
            res1 = dp(i + 1, u)
            res2 = dp(i + 1, u - w[i]) + v[i]
            res = max(res1,res2)
            done[i][u] = True
            memo[i][u] = res
            return res

    print(dp(0,W))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
item: ２次元配列 item[i] = [weight, value]
bounds: size of knapsack
"""
def knapsack(item, bounds):
    n = len(item)
    dp_table = [[0] * (bounds+1) for i in range(n)]
    for w in range(1,bounds+1):
        if item[0][0] > w:
            continue
        dp_table[0][w] = item[0][1]

    for i in range(1,n):
        for w in range(W+1):
            if item[i][0] > w:
                dp_table[i][w] = dp_table[i-1][w]
            else:
                dp_table[i][w] = max(dp_table[i-1][w], dp_table[i-1][w-item[i][0]] + item[i][1])
    return dp_table[n-1][bounds]


N, W = map(int, input().strip().split())
item = []
for i in range(N):
    value, weight = map(int, input().strip().split())
    item.append([weight, value])

print(knapsack(item, W))

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
    vi,wi=map(int,input().split())
    for j in range(w+1):
        if(j >= wi):
            dp[i+1][j] =max(dp[i][j-wi]+vi,dp[i][j])
        else:
            dp[i+1][j] =dp[i][j]
#    print(dp[i+1])
print(dp[n][w])

Submission status: Accepted

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

v = []
w = []

for i in range(N):
    vv, mm = map(int, input().split())
    v.append(vv); w.append(mm)

"""
つまり、
dp[i][vv][ww] = {max(dp[i+1][vv+v[i]][ww-w[i]] | dp[i+1][vv][ww]}
となる？
価値を保存するから vv が消えると
dp[i][ww] = {max(dp[i+1][ww-w[i]]+v[i] | dp[i+1][ww]}
となる。
これは、実質、価値であるから
"""

def rec(i, vv, ww):
    if i == N:
        return vv
    ans = 0
    # 入れるパターン
    if ww >= w[i]:
        ans = rec(i+1, vv+v[i], ww-w[i])
    # 入れないパターン
    ans = max(ans, rec(i+1, vv, ww))
    return ans

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
v = []
w = []
for i in range(N):
    vv, ww = map(int, input().split())
    v.append(vv)
    w.append(ww)
# テーブルは一つ多く作っておく
dp = [['.' for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):  # 境界条件
    dp[N][i] = 0

for i in range(N - 1, -1, -1):
    for u in range(0, W+1):
        if u < w[i]:    # uが小さいため入れられない
            dp[i][u] = dp[i + 1][u]
        else:  # 入る時の価値を計算
            dp[i][u] = max(dp[i + 1][u], dp[i + 1][u - w[i]] + v[i])

print(dp[0][W])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
num ,endu = map(int,input().split())

arr = [[0]*(endu+1) for i in range(num+1)]

value = [0]
weight = [0]
for i in range(num):
    val, wei = map(int,input().split())
    value.append(val)
    weight.append(wei)

for i in range(1,num+1):
    
    for j in range(1,endu+1):
        if j >= weight[i]:
            arr[i][j] = max(arr[i-1][j-weight[i]]+value[i],arr[i-1][j])
        else:
            arr[i][j] = arr[i-1][j]

print(arr[num][endu])

Submission status: Accepted

Solution code:
_,W,*L=map(int,open(0).read().split())
l=[0]*(W+1)
for v,w in zip(*[iter(L)]*2):
	for i in range(W,w-1,-1):
		x=l[i-w]+v
		if x>l[i]:l[i]=x
print(l[W])

Submission status: Accepted

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

N, W = map(int, input().split())
A = [Item(*list(map(int, input().split()))) for i in range(N)]
A = [Item(0, 0)] + A
dp = [[0 for i in range(W+1)] for j in range(N+1)]

maximum = 0
for i in range(1, N+1):
  item = A[i]
  for w in range(W+1):
    if w - item.w < 0:
      dp[i][w] = dp[i-1][w]
    else:
      dp[i][w] = max(dp[i-1][w], dp[i-1][w-item.w] + item.v)
    maximum = max(maximum, dp[i][w])

print(maximum)

Submission status: Accepted

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

def knapsack(i , j):
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    def solve(i , j):
        if dp[i][j] != -1:
            return dp[i][j]
        if i == N:
            retval = 0
        elif j < weight[i]:
            retval = solve(i + 1 , j)
        else:
            retval = max(solve(i + 1 , j) , solve(i + 1 , j - weight[i]) + value[i])
        dp[i][j] = retval
        return retval
    ans = solve(0,W)
    return ans

if __name__ == "__main__":
    print(knapsack(0 , W))

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
vw=[list(map(int,input().split())) for _ in [0]*n]
memo=[0]*(W+1)
for i in range(n):
    v,w=vw[i]
    for j,k in enumerate(memo[W-w::-1]):
        memo[W-j]=max(v+k,memo[W-j])
print(max(memo))

Submission status: Accepted

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

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

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

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

#print(dp)

for i in range(2,N+2):#i(row) derection:-2
    for j in range(W+1):
        if j<w[i-2]:
            dp[i][j]=dp[i-1][j]
        else:
            x1=dp[i-1][j]
            x2=dp[i-1][j-w[i-2]]+v[i-2]
            dp[i][j]=max([x1,x2])

#print(dp)
print(dp[N+1][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)]

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for n in range(N):
  v, w = L[n]
  for i in range(1, W+1):
    if i >= w:
      dp[n+1][i] = max(dp[n][i], dp[n][i-w]+v)
    else:
      dp[n+1][i] = dp[n][i]
ans = 0
for i in dp:
  ans = max(ans, max(i))
print(ans)

Submission status: Accepted

Solution code:
import time,sys
sys.setrecursionlimit(1000000000)

#jが残り
def search(i,j):

    if(memo[i][j]>=0):
        return memo[i][j]

    if i==N :
        res=0
    elif j<items[i][1]:
        #いれない。
        res = search(i+1,j)
    else:
        #            いれなかった場合       いれた場合、重さを引いて価値を追加
        res = max( search(i+1,j), search(i+1,j-items[i][1])+items[i][0] )
    memo[i][j] =res
    return res

N,W = map(int,input().split())
res=0
items=[]
for i in range(N) :
    array =list(map(int,input().split()))
    items.append(array)
# memo = np.arange(N*W).reshape(N,W)
memo=[[-1 for i in range(W+1)] for j in range(N+1)]
# print(*memo,sep="\n")

knapsack=0
print(search(0,W))

Submission status: Accepted

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

weight_value = []

for i in range(N):
    value, weight = map(int, input().split())
    weight_value.append([value, weight])
 
# dpの初期値（i + 1に入れていくので、ひとつ多く準備する）
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

# 動的計画法で最大値を求める
# 選ぶ個数のループ
for i in range(N):
    value = weight_value[i][0]
    weight = weight_value[i][1]
    
    # 各重さのループ
    for j in range(W + 1):
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        
        next_weight = j + weight
        next_value = dp[i][j] + value
        
        if (next_weight <= W and next_value > dp[i+1][next_weight]):
            dp[i+1][next_weight] = next_value

            
# 結果出力
print(dp[N][W])

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
### メモ化による方法
n, w = map(int, input().split())
zaq = [tuple(map(int, input().split())) for _ in range(n)]
memo = [[-1] * n for _ in range(w+1)]

def dfs(i, w):
    if i == n:
        return 0
    elif memo[w][i] >= 0:
        return memo[w][i]
    elif w < zaq[i][1]:
        return dfs(i+1, w)
    else:
        res1 = dfs(i+1, w)
        res2 = dfs(i+1, w - zaq[i][1]) + zaq[i][0]
        res = max(res1, res2)
        memo[w][i] = res
        return res
print(dfs(i=0, w=w))

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, W = map(lambda x: int(x), input().split())
    items = [(0, 0)] * N
    for i in range(N):
        v, w = map(lambda x: int(x), input().split())
        items[i] = (v, w)
    dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

    for i in range(N):
        value, weight = items[i]
        for j in range(W + 1):
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
            next_weight = j + weight
            next_value = dp[i][j] + value
            if (next_weight <= W and next_value > dp[i + 1][next_weight]):
                dp[i + 1][next_weight] = next_value

    print(max(dp[N]))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(W + 1)]

for a in A:
  for j in range(W, a[1] - 1, -1):
    dp[j] = max(dp[j], dp[j - a[1]] + a[0])
print(max(dp))

Submission status: Accepted

Solution code:
n,w=map(int,input().split( ))
V = []
W = []
#大文字小文字は紛らわしいか

for i in range(n):
    v,t = map(int, input().split( ))
    V.append(v)
    W.append(t)
#####W取得前にwmax求めてどうする


Pos = [[0 for w2 in range(w+1)] for j in range(n)]
Able = []

for i in range(n):
     for w1 in range(w+1):#w含まないと
         if w1 >= W[i]:
             Pos[i][w1] = max(Pos[i-1][w1-W[i]] + V[i], Pos[i-1][w1])
             #print(i,V[i],Pos[i-1][w1-W[i]], Pos[i-1][w1])
         else:
             Pos[i][w1] = Pos[i-1][w1]
         if Pos[i][w1] > 0:
            Able.append(Pos[i][w1])
#print(*Pos)
#print(*Able)

print(Able[-1])

Submission status: Accepted

Solution code:
from typing import List, NamedTuple
import pprint

pp = pprint.PrettyPrinter()


class Baggage(NamedTuple):
    value: int
    weight: int


def knapsack(
    total_weight: int, n_baggages: int, baggages: List[Baggage]
) -> int:

    T: List[List[int]] = [
        [0] * (n_baggages + 1) for _ in range(total_weight + 1)
    ]

    for n in range(1, n_baggages + 1):
        for t in range(1, total_weight + 1):
            v = T[t][n - 1]
            b = baggages[n - 1]
            if t >= b.weight:
                v_use = T[t - b.weight][n - 1] + b.value
                v = max(v, v_use)
            T[t][n] = v
        # pp.pprint(T)

    return T[total_weight][n_baggages]


def main() -> None:
    N, W = [int(x) for x in input().split()]

    B: List[Baggage] = []
    for _ in range(N):
        v, w = (int(x) for x in input().split())
        B.append(Baggage(v, w))

    print(knapsack(W, N, B))


main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# DPL 1 B

def solve():
    INF = 1e+9
    n, w = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0] * (w+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, w+1):
            item = items[i-1]
            # max(dp[i-1][j], dp[i][j-item[1]] + item[0])
            if j - item[1] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-item[1]] + item[0])

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N,M = map(int, raw_input().split())
V,W = [],[]
for i in range(N):
    v,w = map(int, raw_input().split())
    V.append(v)
    W.append(w)

dp = [[-1]*(M+1) for _ in range(N+1)]
def rec(i,j):
    if dp[i][j] != -1:
        return dp[i][j]

    if i == N:
        res = 0
    elif j < W[i]:
        res = rec(i+1, j)
    else:
        res = max(rec(i+1,j), rec(i+1,j-W[i]) + V[i])

    dp[i][j] = res
    return res

print rec(0, M)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
goods = []
for i in range(N):
    goods.append(list(map(int, input().split())))
from collections import defaultdict
dp = defaultdict(lambda: defaultdict(int))
for i, g in enumerate(goods):
    for w in range(1, W+1):
        if w>=g[1]:
            dp[(i+1)%2][w]=max(dp[i%2][w-g[1]]+g[0],dp[i%2][w])
        else:
            dp[(i+1)%2][w]=dp[i%2][w]
print(dp[(len(goods))%2][W])

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
items=[[0,0]]
for i in range(n):
  items.append(list(map(int,input().split())))
c=[[0 for i in range(w+1)]for j in range(n+1)]
for i in range(1,n+1):
  for j in range(1,w+1):
    if items[i][1]<=j:
      if items[i][0]+c[i-1][j-items[i][1]]>c[i-1][j]: 
        c[i][j]=items[i][0]+c[i-1][j-items[i][1]]
      else:
        c[i][j]=c[i-1][j]
    else:
      c[i][j]=c[i-1][j]
print(c[n][w])

Submission status: Accepted

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

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

for i in range(N):
    for sum_w in range(W+1):
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
        if sum_w + w[i] > W:
            continue
        dp[i+1][sum_w+w[i]] = max(dp[i+1][sum_w+w[i]], dp[i][sum_w] + v[i])

print(max(dp[N]))

Submission status: Accepted

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

dp = [[0 for _ in range(N)] for _ in range(W+1)]
# 重さwまで品物nまででで最大になる価値

for n in range(N): # 品物nまでの世界で決めていく
    for w in range(W+1):
        vn, wn = K[n]
        if wn > w: # カバンに入りきらないなら入れられない
            dp[w][n] = dp[w][n-1]
        else: #カバンに入れられる可能性があるなら
            dp[w][n] = max(dp[w][n-1], vn+dp[w-wn][n-1]) #　入れた場合と入れなかった場合で価値の高い方を選ぶ

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

Submission status: Accepted

Solution code:
N,W=map(int, input().split())
x=[list(map(int, input().split())) for i in range(N)]
#DPテーブルを作成
dp=[[0]*(W+1) for i in range(N)]
for i in range(N):
    for j in range(W+1):
        cnt=0
        if x[i][1]<=j:
            cnt=max(dp[i-1][j-x[i][1]]+x[i][0],dp[i-1][j])
        else:
            cnt=dp[i-1][j]
        dp[i][j]=cnt
print(dp[N-1][W])

Submission status: Accepted

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

    products = []
    for i in range(N):
        products.append([int(num) for num in input().split()])

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

    for i in range(N+1):
        if i == 0:
            continue
        for w in range(W+1):
            if w < products[i-1][1]:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max(dp[i-1][w-products[i-1][1]] + products[i-1][0], dp[i-1][w])

    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    N, W = readi(2)
    vs, ws = zip(*readi(N, 2))
    dp = arr(N + 1, W + 1)
    for i in range(N):
        for j in range(W + 1):
            if j - ws[i] >= 0:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - ws[i]] + vs[i])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

    print(dp[N][W])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(n):
#    v1, v2 = map(int, input().split())
    v2, v1 = map(int, input().split())
    w.append(v1)
    v.append(v2)

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))

Submission status: Accepted

Solution code:
dp = {}

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

value = []
weight = []

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

for i in range(n):
    s = list(map(int, input().split()))

    value.append(s[0])
    weight.append(s[1])

for i in range(n):
    for w in range(0, 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: Accepted

Solution code:
# 一つの種類は一つまでのナップサック
# メモ化再帰で解く

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

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

memo = [[-1] * (W + 1) for _ in range(N+1)]

# i番目の品物から重さの総和がj以下となるように選ぶ
def rec(i, j):

    if memo[i][j] >= 0:
        return memo[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])
    
    memo[i][j] = res
    return res

print(rec(0, W))

Submission status: Accepted

Solution code:
# 2019/07/03

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

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

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
def larger(x, y):
	if x > y: return x
	return y

N, W = map(int, input().split())
dp = []
for i in range(0, N+1):
	lst = []
	for j in range(0, W+1):
		lst.append(-1)
	dp.append(lst)
dp[0][W] = 0
for i in range(0, N):
	v, w = map(int, input().split())
	for j in range(0, W+1):
		if dp[i][j] != -1:
			dp[i+1][j] = larger(dp[i][j], dp[i+1][j])
			if j - w >= 0:
				dp[i+1][j-w] = larger(dp[i][j]+v, dp[i+1][j-w])
max = 0
for i in range(0, W+1):
	if max < dp[N][i]: max = dp[N][i]
print(max)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import functools


def memorized(f):
    table = {}
    @functools.wraps(f)
    def wrapper(*args):
        if args in table:
            return table[args]
        rvalue = f(*args)
        table[args] = rvalue
        return rvalue
    return wrapper


N, W = map(int, input().split())
v, w = [], []
for _ in range(N):
    vi, wi = map(int, input().split())
    v.append(vi)
    w.append(wi)

@memorized
def knapsack(i, r):
    if i == N:
        return 0
    if r < w[i]:
        return knapsack(i + 1, r)
    return max(knapsack(i + 1, r), v[i] + knapsack(i + 1, r - w[i]))

print(knapsack(0, W))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N,W = list(map(int,input().split()))
vw = [list(map(int,input().split())) for i in range(N)]
value = [i[0] for i in vw]
weight = [i[1] for i in vw]

inf=float("inf")
dp = [[-inf for _ in range(W+1)] for _ in range(N+1)]

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

Submission status: Accepted

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

# dp[i][j] := i番目までの品物の中から重さがjを超えないように選んだときの、価値の総和の最大値
dp = [[0]*(w+1) for i in range(n+1)]

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

Submission status: Accepted

Solution code:
def knapsack_weight(W, items):
    '''
        W (int): the capacity of a knapsack
        items (list of tuples): i-th element is a tuple (weight, value)
    '''
    N = len(items)
    # dp[n][w] = the maximum value when the capacity is w and only items 1, 2, ..., n are used.
    dp = [[0 for j in range(W+1)] for i in range(N+1)]
    for i in range(1, N+1):
        w, v = items[i-1]
        for j in range(W+1):
            if j - w >= 0:
                dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[N][W]

N, W = map(int, input().split())
items = []
for _ in range(N):
    v, w = map(int, input().split())
    items.append((w, v))
print(knapsack_weight(W, items))

Submission status: Accepted

Solution code:
##knapsackProblem
n, w = map(int, input().split())
vw = [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 + 1):
    for j in range(w + 1):
        if j == 0:
            dp[i][j] = 0
        elif i == 0:
            dp[i][j] = 0
        else:
            if j - vw[i - 1][1] >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][1]] + vw[i - 1][0])
            else:
                dp[i][j] = dp[i - 1][j]

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

print(ans)

Submission status: Accepted

Solution code:
items = []
dp = []

def knapsack(n, e):
    for i in range(0, n + 1):
        res = 0
        for j in range(0, e):
            v, w = items[j]
            if i >= w:
                dp[j + 1][i] = max(dp[j][i - w] + v, dp[j][i])
            else:
                dp[j + 1][i] = dp[j][i]
    return

line = input()
E, W = list(map(int, line.split()))
for _ in range(0, E):
    line = input()
    v, w1 = list(map(int, line.split()))
    items += [[v, w1]]
dp = [[0] * (W + 1) for _ in range(0, E + 1)]
knapsack(W, E)
print(dp[E][W])

Submission status: Accepted

Solution code:
N,W=(int(x) for x in input().split())
value=[]
weight=[]
for n in range(N):
    a,b=(int(x) for x in input().split())
    value.append(a)
    weight.append(b)
def knap(N,W,value,weight):
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N+1):
        for w in range(W+1):
            if i>0:
                if weight[i-1]<=w:
                    dp[i][w]=max(dp[i-1][w],dp[i-1][w-weight[i-1]]+value[i-1])
                else:
                    dp[i][w]=dp[i-1][w]
    return dp[N][W]
print(knap(N,W,value,weight))

Submission status: Accepted

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

dp=[[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
    for m in range(1,W+1):
        if VW[n-1][1]>m:
            dp[n][m]=dp[n-1][m]
        else:
            dp[n][m]=max(dp[n-1][m],dp[n-1][m-VW[n-1][1]]+VW[n-1][0])
print(dp[-1][-1])

Submission status: Accepted

Solution code:
N, W = [int(x)for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))
dp = [0]*(W+1)
for i in range(N):
    v, w = items[i]
    for j in reversed(range(w,W+1)):
        dp[j] = max(dp[j],dp[j-w]+v)

print(dp[-1])

Submission status: Accepted

Solution code:

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

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

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

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

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
L = []
for i in range(n):
  L.append(list(map(int,input().split())))
dp = []
for i in range(n+1):
    T = [0]*(w+1)
    dp.append(T)
for i in range(n-1,-1,-1):
    for j in range(w+1):
        if j < L[i][1]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-L[i][1]]+L[i][0])
print(dp[0][w])

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
s = []
check = [[0 for b in range(w+1)] for a in range(n)]
for i in range(n):
  s.append(list(map(int,input().split())))

for j in range(n): 
  for k in range(1,w+1):
    if k < s[j][1]: #現在チェック中の重量がkを超えるなら
      check[j][k] = check[j-1][k] #iの宝石を入れない場合の最大
    else:
      check[j][k] = max(check[j-1][k],check[j-1][k-s[j][1]]+s[j][0])   
print(max(check[n-1]))

Submission status: Accepted

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

lst = []
for i in range(N):
    a = list(map(int, input().split()))
    lst += [a]

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

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



print (dp[0][W])

Submission status: Accepted

Solution code:
def larger(x, y):
	if x > y: return x
	else: return y

N, W = map(int, raw_input().split())
dp = []
for i in range(0, N+1):
	lst = []
	for j in range(0, W+1):
		lst.append(0)
	dp.append(lst)
items = []
for i in range(0, N):
	items.append(map(int, raw_input().split()))
weight = W
for i in range(0, N):
	for w in range(0, W+1):
		if items[i][1] <= w:
			dp[i+1][w] = larger(dp[i][w-items[i][1]]+items[i][0], dp[i][w])
		else: dp[i+1][w] = dp[i][w]

print dp[N][W]

Submission status: Accepted

Solution code:
from collections import*
N,W=map(int,input().split())
d=defaultdict(int)
d[0]=0
for i in range(N):
    v,w=map(int,input().split())
    for p,q in d.copy().items():
        if p+w<=W:
            d[p+w]=max(d[p+w],v+q)
#    print(d)
print(max(d.values()))

Submission status: Accepted

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

# dp[i+1][w]: 重さwを超えないようにi番目まで選んだときの価値の合計の最大値
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    for w in range(W+1):
        dp[i+1][w] = max(dp[i][w-items[i][1]] + items[i][0], dp[i][w]) if w >= items[i][1] else dp[i][w]
print(dp[N][W])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
vw = [[0, 0]]+[list(map(int, input().split())) for _ in range(N)]
'''
ナップザック問題
i番目までの品物で作れる価値の最大値を求めていく
'''
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):
        v = dp[i-1][j]
        if j >= vw[i][1]:
            t = dp[i-1][j-vw[i][1]] + vw[i][0]
            if t > v:
                v = t
        dp[i][j] = v
print(dp[N][W])