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 dp_all(dp):
  length = len(dp)
  for i in range(length):
    print(dp[i])

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

v = []
w = []

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

dp = [[0 for _ in range(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())
vw = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #i番目までみたときの重さjでの価値の最大値
for i in range(N):
  v, w = vw[i]
  for j in range(W+1):
    if w <= j:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)
    else:
      dp[i+1][j] = dp[i][j]
print(dp[N][W])

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
VW = [list(map(int,input().split())) for _ in range(N)]
Val = [VW[i][0] for i in range(N)]
Wei = [VW[i][1] for i in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
#dp[i][j]:=i番目までの品物で重さjまででの価値の合計の最大値

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

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

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

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

Submission status: Accepted

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

dp = [[0]*(w+1) for i in range(n+1)]
for i in range(n):
    vi, wi = a[i]
    for j in range(w+1):
        if j + wi <= w:
            dp[i+1][j+wi] = max(dp[i][j]+vi, dp[i+1][j+wi])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])

print(max(dp[i+1]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

print (dp[N][W])

Submission status: Accepted

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

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

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

ans = dp[N][W]
print(ans)

Submission status: Accepted

Solution code:
# 入力
N, W = [int(_) for _ in input().split()]
vw = [[int(_) for _ in input().split()] for _ in range(N)]

# dp[i][j]:i番目までを採用したときに重さがjを超えない価値総和の最大値
dp = [[0 for i in range(W+1)] for j in range(N+1)]
# 0個採用なので価値は0 dp[0][w]=0
for i in range(W+1): dp[0][i] = 0

# dp計算
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(dp[N][W])

Submission status: Accepted

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

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

for i in range(0, N):
    d.append([])
    v_i, w_i = map(int, input().split())
    for k in range(0, W + 1):
        if k >= w_i:
            d[i + 1].append(max(d[i][k - w_i] + v_i, d[i][k]))
        else:
            d[i + 1].append(d[i][k])
            
print(max(d[N]))

Submission status: Accepted

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

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

for i in range(1,N+1):
	for j in range(1, W+1):
		if VW[i][1] > j:
			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[N][W])

Submission status: Accepted

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

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

# i: i 番目のアイテム
# sum_w: 総容量 sum_w の場合
for i in range(n):
    for sum_w in range(w + 1):
        if sum_w - item[i][1] >= 0:
            # i 番目のアイテムを選ぶ場合
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - item[i][1]] + item[i][0])
        # i 番目のアイテムを選ばない場合
        dp[i + 1][sum_w] = max((dp[i + 1][sum_w], dp[i][sum_w]))
print(dp[n][w])

Submission status: Accepted

Solution code:
from collections import namedtuple
from functools import lru_cache

Item = namedtuple('Item', ('v', 'w'))


class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    @lru_cache(maxsize=None)
    def dfs(self, w, index):
        item = items[index]
        if index == self.N - 1:
            if w + item.w <= self.W:
                return item.v
            else:
                return 0

        if w + item.w <= self.W:
            return max([
                # skip this item
                self.dfs(w, index + 1),
                # Store this item
                item.v + self.dfs(w+item.w, index + 1)
            ])
        else:
            # Skip this item
            return self.dfs(w, index + 1)

    def solve(self):
        # 重さゼロの状態でゼロ番目の品物から評価
        return self.dfs(0, 0)


if __name__ == "__main__":
    N, W = list(map(int, input().split()))
    items = []
    for _ in range(N):
        v, w = list(map(int, input().split()))
        items.append(Item(v=v, w=w))

    s = Solver(N, W, items)
    print(s.solve())

Submission status: Accepted

Solution code:
from collections import namedtuple

Item = namedtuple('Item', 'value, weight')


def make_knapsack_resolver(num_items, max_capacity):
    dp = [[0] * (max_capacity + 1) for _ in range(num_items + 1)]
    items = [Item(*[int(x) for x in input().split()]) for _ in range(num_items)]

    def resolve():
        calc_recurrence()
        return dp[0][max_capacity]

    def calc_recurrence():
        for idx_item in range(num_items - 1, 0 - 1, -1):
            for remaining_capacity in range(1, max_capacity + 1):
                if remaining_capacity < items[idx_item].weight:
                    dp[idx_item][remaining_capacity] = dp[idx_item + 1][remaining_capacity]
                else:
                    dp[idx_item][remaining_capacity] = max(
                        dp[idx_item + 1][remaining_capacity],
                        dp[idx_item + 1][remaining_capacity - items[idx_item].weight] + items[idx_item].value
                    )

    return resolve()


if __name__ == '__main__':
    N, W = list(map(int, input().split()))
    resolver = make_knapsack_resolver(N, W)
    print(resolver)

Submission status: Accepted

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

vw = []
for i in range(N):
    vw.append([int(i) for i in input().split(" ")])
value = [i[0] for i in vw]
weight = [i[1] for i in vw]

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

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

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
INF = 10**10
dp = [[-INF] * (W+1) for i in range(2)]
dp[0][0] = 0
for i in range(N):
    dp[(i+1)%2][:] = dp[i%2][:]
    v,w = map(int, input().split())
    for j in range(W+1):
        if dp[i%2][j] == -INF:continue
        if j+w <= W:
            dp[(i+1)%2][j+w] = max(dp[i%2][j+w],dp[i%2][j]+v)
    # print(dp[i+1])
print(max(dp[N%2]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,w = map(int ,input().split())
dp = [[0] * (w+1)  for _ in range(n)]
ll = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    for j in range(w+1):
        tmp_w = ll[i][1] + j
        if tmp_w <= w:
            dp[i][tmp_w] = max(dp[i][tmp_w], dp[i-1][j] + ll[i][0])
        dp[i][j] = max(dp[i][j], dp[i-1][j])
print(max(dp[n-1]))

Submission status: Accepted

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
N,W = [int(i) for i in input().split()]
data = [[int(i) for i in input().split()] for j in range(N)]


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 j >= data[i][1]:
            DP[i+1][j] = (max(DP[i][j-data[i][1]]+data[i][0],DP[i][j]))
        else:
            DP[i+1][j] = DP[i][j]
            
print(DP[-1][-1])

Submission status: Accepted

Solution code:
"""
DP
"""
N, W = list(map(int, input().split()))
V = []
WEI = []

for i in range(N):
    v, w = list(map(int, input().split()))
    V.append(v)
    WEI.append(w)

# DP[i][j]: i番目以降の品物を使い、重さj以下にする場合の価値の最大
DP = []
for i in range(N+1):
    a = [None] * (W+1)
    DP.append(a)

for i in range(W+1):
    # N番目以降の品物を選ぶことはできない（品物が存在しない）
    DP[N][i] = 0

# N-1 から 0 まで（品物の番号）
for i in range(N-1, -1, -1):
    # 0 から W まで（重さ）
    for j in range(W+1):
        if j < WEI[i]:  # 商品iが使えない場合
            DP[i][j] = DP[i+1][j]
        else:
            DP[i][j] = max(DP[i+1][j], DP[i+1][j-WEI[i]] + V[i])

print(DP[0][W])

Submission status: Accepted

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

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

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

print(DP[N][W])

Submission status: Accepted

Solution code:
from functools import lru_cache


@lru_cache(None)
def dp(i, cur):
    if cur > W:
        return float('-inf')
    elif i < 0:
        return 0
    else:
        v, w = VW[i]
        return max(dp(i - 1, cur), dp(i - 1, cur + w) + v)


N, W = map(int, input().split())
VW = [[int(x) for x in input().split()] for _ in range(N)]
print(dp(N - 1, 0))

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
L=[list(map(int,input().split())) for _ in range(n)]
# dp[i][w] := 品物1〜i　を総和w以下で選ぶときの最大価値
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    for w in range(W+1):
        # 品物i の価値がw以下ならば dp[i][w]より大きく出来る可能性がある.
        if L[i][1] <=  w:
            dp[i+1][w] = max(dp[i][w - L[i][1]]+L[i][0], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(max(dp[n]))

Submission status: Accepted

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

n, w = map(int, input().split())
items = {i: Item(*map(int, input().split())) for i in range(1, n+1)}
dp = [[i for i in range(w+1)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
for i in range(w+1):
    dp[0][i] = 0
for j in range(1, n+1):
    for k in range(1, w+1):
        if 0 <= k - items[j].w:
            dp[j][k] = max(dp[j-1][k], dp[j-1][k-items[j].w] + items[j].v)
        else:
            dp[j][k] = dp[j-1][k]
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)]

values = []
weights = []

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


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

print(dp[N][W])

Submission status: Accepted

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

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

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

print(dp[W])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
    n,wn=MI()
    vw=[LI() for _ in range(n)]
    dp=[0]*(wn+1)
    for v,w in vw:
        for i in range(wn,w-1,-1):
            dp[i]=max(dp[i],dp[i-w]+v)
    print(dp[-1])

main()

Submission status: Accepted

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

# dp[i][j] := i番目の品物までで重さjとなるように選んだときの価値の最大値
# dp[i][j] := max(dp[i - 1][j - w] + v, dp[i - 1][j])
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 w[i] > j:  # 今選ぼうとしている品物の重さが制限jを超える場合には当然選べない
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
print(dp[N][W])

Submission status: Accepted

Solution code:
from bisect import bisect_left as lower_bound
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    N, W = MI()
    v = [0] * N
    w = [0] * N
    dp = [0] * (W + 1)

    for i in range(N):
        v[i], w[i] = MI()

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

    print(dp[W])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ライブラリのインポート
#import re #正規表現
import sys
#import heapq
#import collections
#import math

def main():
    n, w = map(int, input().split())
    goods = [(0,0)]*n
    for i, inp in enumerate(sys.stdin):
        v, wtmp = map(int, inp.strip("\n").split())
        goods[i] = (v,wtmp)
    dp = [[0 for i in range(w+1)] for j in range(n)]
    for i in range(n):
        for c in range(w+1):
            if i < 0 or c <= 0: dp[0][0] = 0
            elif c - goods[i][1] < 0: dp[i][c] = dp[i-1][c]
            else: dp[i][c] = max(goods[i][0] + dp[i-1][c-goods[i][1]], dp[i-1][c])
    print(dp[n-1][w])



    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, W = iim()
    S = [iim() for i in range(N)]

    N1 = N + 1
    dp = [-1] * (W+1)
    dp[0] = 0

    for v, w in S:
        for i in range(W-w, -1, -1):
            if dp[i] == -1: continue
            j = i + w
            dp[j] = max(dp[j], dp[i] + v)

    print(max(*dp))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
length, weight = (int(n) for n in input().split(" ") )
dp = [0 for n in range(weight + 1)]
for l in range(length):
    v, w = (int(n) for n in input().split(" ") )
    temp = dp[:]
    for i, d in enumerate(dp):
        if d and i + w <= weight:
            temp[i + w] = max(d + v, dp[i + w])
    dp = temp
    dp[w] = max(v, dp[w])
    # print(dp)
print(max(dp))

Submission status: Accepted

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

values = [0] * N
weights = [0] * N

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
import operator
import functools


@functools.lru_cache(10**9)
def dynamic_planning(item_taken, target_weight):
    if item_taken == 0 or target_weight == 0:
        return 0
    value, weight = items[item_taken-1]
    if weight <= target_weight:
        ret = max(dynamic_planning(item_taken-1, target_weight-weight) + value, dynamic_planning(item_taken-1, target_weight))
    else:
        ret = dynamic_planning(item_taken-1, target_weight)
    return ret


N, W = map(int, input().split(" "))
items = list()
for _ in range(N):
    items.append(list(map(int, input().split(" "))))
items = sorted(items, key=operator.itemgetter(0))
print(dynamic_planning(N, W))

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 j in item:
	for i in range(1,w+2):
		if w+1-i+j[1] <=w:
			dp[w+1-i+j[1]] = max(dp[w+1-i+j[1]],dp[w+1-i]+j[0])
print(dp[w])

Submission status: Accepted

Solution code:

 
def rec1 (n,w): # 重さにフォーカスしたdp
    v = 0
 
    if dp[n][w] > 0:
        return dp[n][w]
 
    if n == N: # 最後の商品以降で重さがw以下になるように選ぶ→選べない→0
        v = 0
    elif items[n][1] > w: #n番目のitemが制限より重い→スキップ
        v = rec1(n + 1 ,w)
    else: #item nを選べるとき→選ぶか，選ばないか選択する
        c1 = rec1(n + 1, w ) #選ばないルート
        c2 = rec1(n + 1, w - items[n][1]) + items[n][0]
        v = max( c1,c2)
    dp[n][w] = v
    return v
 
 
 
 
#v,w
 
N, W = map(int, input().split())
items = [ tuple(map(int, input().split()) )for _ in range(N)]
maxW = maxV = -1
for item in items:
    v,w = item
    maxW = max(maxW,w)
    maxV = max(maxV,v)
# MAX_W = max([item[1] for item in  items])
# vのsum → 高々2 * 10e5
 
 
if maxW <= 1000:
    dp = [[-1] * 200001 for _ in range(N + 1)]
    rec1(0, W)
    print(dp[0][W])
elif maxV <= 1000:
    INF = 10 ** 18
    dp = [INF] * 200001
    dp[0] = 0
    for item in items:
        v, w = item
        for j in range(200000,v-1,-1):
            dp[j] = min( dp[j - v] + w ,dp[j])
    for j in range(200000, - 1, -1):
        if dp[j] <= W:
            print(j)
            break

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

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

v = [None] * N
w = [None] * N

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


solve()

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


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

dp = [-BIG_NUM]*(W+1)
dp[0] = 0

for _ in range(num_item):
    value,weight = map(int,input().split())
    for i in range(W,weight-1,-1):
        if dp[i-weight] == -BIG_NUM:
            continue
        dp[i] = max(dp[i],dp[i-weight]+value)

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

print("%d"%(ans))

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


  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])
  return dp[N][W]

if __name__ == '__main__':
    N,W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        va,we = map(int, input().split())
        weight.append(we)
        value.append(va)
    print(knapsack(N,W,weight,value))

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 j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])

print(dp[N][W])

Submission status: Accepted

Solution code:


N,W  = 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 j in range(W+1):
        if vw[i][1] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-vw[i][1]] + vw[i][0])
        else:
            dp[i+1][j] = dp[i][j]

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

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_B
# 王道のナップサック問題
# 解説は螺旋本で十分わかりやすい

# 実装の都合上本とは少しだけ変えて実装する
# items (N,) ,i番目の品物の価値と重さが記録されているlist item[i]
# dp (N+1,W+1), [0,i)までのitemを考慮して大きさwのナップサックに入れる場合の価値の合計の最大値をdp[i][w]とする二次元list

# load data
N, W = list(map(int, input().split()))
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))


# dpテーブルの作成
# 今回は最大化が目的なのですべてのマスを-1で埋めることにする
dp = [[-1] * (W + 1) for _ in range(N + 1)]

# dpテーブルの初期化
# dp[:][0]が0 ∵大きさ0のナップサックには何も入れられない
# dp[0][:]が0 ∵なにもitemを考慮しないときはナップサックに何も入らない。
for i in range(N + 1):
    dp[i][0] = 0
for w in range(W + 1):
    dp[0][w] = 0

# dpテーブルの更新
# i番目のitemが入らない場合→dp[i+1][w]=dp[i][w] ∵iを考慮しないときと価値は変わらない
# i番目のitemが入る場合→dp[i+1][w]=max(dp[i][w], dp[i][w-item[i]の重さ]+item[i]の価値)
# ∵iを入れる前の最善はdp[i][w-item[i]の重さ]にあり、それにitem[i]の価値を足すことで最善になる可能性がある。
# ただしちゃんと、iを入れないときのほうが良いかもしれないことに注意しなければいけない。
from itertools import product
for i, w in product(range(N), range(W + 1)):
    dp[i + 1][w] = dp[i][w]
    value, weight = items[i]
    if w - weight >= 0:
        dp[i + 1][w] = max(dp[i][w], dp[i][w - weight] + value)

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

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 i in range(N):
    value = vw[i][0]
    weight = vw[i][1]
    for w in range(W + 1):
        if w >= weight:
            dp[i + 1][w] = max(dp[i][w - weight] + value, dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def MAP(): return [int(s) for s in input().split()]

if sys.platform =='darwin':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

N, W = MAP()
v = [0] * N
w = [0] * N
for i in range(N):
	v[i], w[i] = MAP()

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

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

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline


def knapsack(N, weight):
    dp = [0] * (weight + 1)
    for _ in range(N):
        v, w = map(int, readline().split())
        ww = w
        dp_prev = dp[:]
        while ww <= weight:
            dp[ww] = max(dp_prev[ww], dp_prev[ww - w] + v)
            ww += 1
    return dp[-1]

if __name__ == "__main__":
    n_goods, weight = map(int, input().split())
    print(knapsack(n_goods, weight))

Submission status: Accepted

Solution code:




def knaspsack(V,W,n,w):
    V = [0] + V ; W = [0] + W
    dp = [[0]*(w+1) for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(w+1):
            if j < W[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]]+V[i])
    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(knaspsack(V,W,n,w))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
Data = []
for _ in range(N):
    v,w = map(int,input().split())
    Data.append([v,w])
Data.sort(key=lambda x:x[1])
DP = [[0]*(W+1) for _ in range(N+1)]

for n in range(1,N+1):
    for w in range(1,W+1):
        tv,tw = Data[n-1]
        if tw <= w:
            DP[n][w] = max(DP[n][w],DP[n-1][w-tw]+tv)
        DP[n][w] = max(DP[n][w],DP[n-1][w])
print(DP[N][W])

Submission status: Accepted

Solution code:
from collections import defaultdict
N, W = list(map(int, input().split()))

v, w = list(), list()
for n in range(N):
    i, j = list(map(int, input().split()))
    v.append(i)
    w.append(j)

dp = dict()
# dp[n][w]: 0からn-1thを考慮した時，　重さがwを超えない価値の最大値
for i in range(N+1):
    dp[i] = dict()
    for j in range(W+1):
        if i == 0:
            dp[i][j] = 0
            continue
        if w[i-1] <= j:
            dp[i][j] = max(dp[i-1][j-w[i-1]]+v[i-1], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
            
print(dp[N][W])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    n_max, w_max = map(int, input().split())

    v_list = []
    w_list = []
    for i in range(n_max):
        v, w = map(int, input().split())
        v_list.append(v)
        w_list.append(w)

    dp = [[0] * (w_max + 1) for _ in range(n_max + 1)]
    # i : 対象とする品物
    for i in range(n_max-1, -1, -1):
        # j : 残りの重さ
        for j in range(w_max + 1):
            if j < w_list[i]:
                dp[i][j] = dp[i+1][j]
            else:
                temp0 = dp[i+1][j]
                temp1 = dp[i+1][j - w_list[i]] + v_list[i]
                dp[i][j] = max(temp0, temp1)

    print(dp[0][w_max])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][1] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][1]]+li[i][0])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))