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

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

print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    N,W = map(int,input().split())
    item = [tuple(map(int,input().split())) for _ in range(N)]
    dp = [0] * (W + 1)
    for v,w in item:
        for j in range(W,w - 1,-1):
            dp[j] = max(dp[j],dp[j - w] + v)
    print(dp[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

C = [[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]
        if item[1] <= j:
            C[i][j] = max(C[i - 1][j], C[i - 1][j - item[1]] + item[0])
        else:
            C[i][j] = C[i - 1][j]

print(C[N][W])

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=ja
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,W,*vw = map(int, read().split())

    VW = []
    for v, w in zip(*[iter(vw)]*2):
        VW.append((v, w))

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

    for i in range(N):
        v_i, w_i = VW[i]
        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 - w_i] + v_i, dp[i][j])

    print(dp[N][W])    


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def solve():
    import sys

    N, W = list(map(int, sys.stdin.readline().split()))

    dp = [[0 for w in range(W+1)] for _ in range(N+1)]  # dp[i][w] := i個の品物を使って、重さの総和がw以下のときの価値の最大値

    for i in range(1, N+1):
        v, w = list(map(int, sys.stdin.readline().split()))
        for j in range(0, W+1):
            dp[i][j] = max(dp[i][j], dp[i-1][j])
            if j+w <= W:
                dp[i][j+w] = max(dp[i-1][j+w], dp[i-1][j]+v)

    print(dp[N][W])


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

dp = [[0] * (w + 1) for _ in range(n + 1)]
# (v, w)
weight = []
value = []
for _ in range(n):
    v, we = map(int, input().split())
    weight.append(we)
    value.append(v)

# dp[i+1][w] i番目までの品物の中から重さがWを超えないように選んだ時の価値の総和の最大値
#              weight[i]を引いた時の最大値
# dp[i+1][w] = dp[i][w-weight[i]]+value[i]
# 入れない時
# dp[i+1][w] = dp[i][w]

for i in range(n):
    for j in range(w+1):
        if j >= weight[i]:
            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)
# print(weight)
# print(value)
print(dp[n][w])

Submission status: Accepted

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

dp = [0]*(W+1)
L = []
for i in range(N):
    ta,tb = map(int,input().split())
    L.append([ta,tb])

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

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
V, W = [], []
for i in range(n):
    vi, wi = map(int, input().split())
    V.append(vi)
    W.append(wi)

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

for i in range(n):
    for sum_w in range(w + 1):
        # i番目の商品を選ぶ場合
        if sum_w - W[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - W[i]] + V[i])
        # i番目の商品を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[-1][-1])

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

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

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

Submission status: Accepted

Solution code:
N,W=list(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)]

def solve(p,w):
  if dp[p][w]:
    return dp[p][w]
  if p == N:
    dp[p][w]= 0
  elif w < VW[p][1]:
    dp[p][w] = solve(p+1,w)
  else:
    dp[p][w] = max(solve(p+1,w),solve(p+1,w-VW[p][1])+VW[p][0])
  return dp[p][w]

print(solve(0,W))

Submission status: Accepted

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

dp = [[0]*(W+1) for _ in range(N+1)] 
for i in range(0,N):
    for w in range(W+1):
        #print(i,w,dp[i][w],end = ' ')
        #print("v=", value[i] ,end = ' ')
        if w >= weight[i]:
            dp[i + 1][w] = max(dp[i][w-weight[i]] + value[i] ,dp[i][w])#iの品物が入る時、weight[i]分引いたnapzacの重さのときの価値の最大値にvalue[i]を足す
        else:
            dp[i + 1][w] = dp[i][w]

dpmax = 0
for i in range(len(dp)):
    for j in range(len(dp[0])):
        if dpmax < dp[i][j]:
            dpmax = dp[i][j]
print(dpmax)

Submission status: Accepted

Solution code:
# DP : 自力実装
#dp = [i=0 [w=0,...,w=W],
#      ...,
#      i=N-1 [w=0,...,w=W],
#      i=N [w=0,...,w=W] ]

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

# DP配列の初期化
dp = [[0 for w in range(W+5)] for i in range(N+5)] # 配列の各要素i番目の荷物(重さw)の状態での「value(の最大値)」

# DP遷移式
#for w=0,1,2,...,W :
# if w>=weight :  荷物i+1をのせて重さをwにすることができる
#  dp[i+1][w] = max(dp[i][w-weghit[i]], # 荷物i番目を乗せ終わった遷移のうち重さw-weight[i]の状態 + 荷物i+1をのせる
#                    dp[i][w]) 　　　　 # 荷物i+1をのせない
# elif w<weght : そもそも荷物i+1をのせることができない(重量がWを超えるので)
#  dp[i+1][w] = dp[i][w] # 荷物i+1をのせない
for i in range(N):
  for w in range(W+1): # w=0,...Wまで調べる必要があるので 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]

# アルゴリズムから必ず右下のvalueが最大となる        
print(dp[N][W])

Submission status: Accepted

Solution code:
def main():
    n, w = map(int, input().split())
    v_list = []
    w_list = []
    for i in range(n):
        _v, _w = map(int, input().split())
        v_list.append(_v)
        w_list.append(_w)

    dp = [[0] * (w+1) for _ in range(n+1)]
    for i in range(n):
        for _w in range(1, w+1):
            # 入るなら入れる
            if w_list[i] <= _w:
                dp[i+1][_w] = max(dp[i][_w], dp[i][_w - w_list[i]] + v_list[i])
            # 無理なら入れない
            else:
                dp[i+1][_w] = dp[i][_w]

    print(dp[n][w])


main()

Submission status: Accepted

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

#weight[i], value[i] (i = 0, 1, 2, 3 ...N -1)

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
I = [[0, 0]]
I += [list(map(int,input().split())) for _ in range(N)]
dp = [[float('inf')]*(W+1) for _ in range(N+1)]
G = [['']*(W+1) for _ in range(N+1)]

def check():
    for w in range(W+1):
        dp[0][w] = 0
        G[0][w] = 'DIAGNOAL'
    for i in range(1, N+1):
        dp[i][0] = 0
    for i in range(1, N+1):
        for w in range(1, W+1):
            if I[i][1] <= w:
                if I[i][0]+dp[i-1][w-I[i][1]] > dp[i-1][w]:
                    dp[i][w] = dp[i-1][w-I[i][1]]+I[i][0]
                    G[i][w] = 'DIAGNOAL'
                else:
                    dp[i][w] = dp[i-1][w]
                    G[i][w] = 'TOP'
            else:
                dp[i][w] = dp[i-1][w]
                G[i][w] = 'TOP'
        max_value = max(dp[i])
    return max_value

print(check())

Submission status: Accepted

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

def main():
    N,W = map(int, readline().split())
    value = []; weight = []
    for _ in range(N):
        v, w = map(int, readline().split())
        value.append(v); weight.append(w)
    DP0 = [0] * (W+1)
    DP1 = [0] * (W+1)
    for i in range(N):
        for w in range(weight[i], W+1):
            DP1[w] = max(DP0[w], DP0[w-weight[i]]+value[i])
        DP0 = DP1.copy()
    print(max(DP0))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

item_list = [list(map(int, input().split())) for i 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 - item_list[i][1] >= 0:
            dp[i + 1][j] = max([dp[i][j], dp[i][j - item_list[i][1]] + item_list[i][0]])
        else:
            dp[i + 1][j] = dp[i][j]

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys

N, W = map(int, sys.stdin.readline().strip().split())

weights = []
for _ in range(N):
    v, w = map(int, sys.stdin.readline().strip().split())
    weights.append((v, w))

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

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

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
value = []
weight = []
for i in range(N):
    v, w = map(int, input().split())
    value.append(v)
    weight.append(w)
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    for max_w in range(W + 1):
        if max_w >= weight[i]:
            dp[i + 1][max_w] = max(dp[i][max_w],
                                   dp[i][max_w - weight[i]] + value[i])
        else:
            dp[i + 1][max_w] = dp[i][max_w]
print(dp[N][W])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,weight=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]*(weight+1) for i in range(n+1)]

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

Submission status: Accepted

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


def knapsack(N, W, weight, value):
    # initialize
    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 w >= weight[i]:
                dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
    return dp[N][W]


print(knapsack(N, W, ws, vs))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    #
    n, W_max = map(int, input().strip().split())
    lv = []
    lw = []
    for _ in range(n):
        a, b = map(int, input().strip().split())
        lv.append(a)
        lw.append(b)

    l_maxSumVal = [[-1 for _ in range(n+1)] for _ in range(W_max + 1) ]
    # function to return "max sum of values" (when picking up [i-th Elarger items] into [W-spaced bagage])
    def calc_maxSumVal(i, W):
        if i > n-1: # 
            return 0
        elif l_maxSumVal[W][i] != -1:
            return l_maxSumVal[W][i]
        elif W < lw[i]: #
            l_maxSumVal[W][i+1] = calc_maxSumVal(i + 1, W)
            return l_maxSumVal[W][i+1]
        else: # if [the free space of bagage] is << Elarger than [the weight] (of items now u r looking at) >>
            l_maxSumVal[W - lw[i]][i+1] = calc_maxSumVal(i + 1, W - lw[i]) # [value of the item now u r looking at] + [max sum of values when u picking up items from i-th Elarger ones and put them into bagage whose free space is W - l_w[i]]
            l_maxSumVal[W][i+1] = calc_maxSumVal(i+1, W)
            return max(lv[i] + l_maxSumVal[W - lw[i]][i+1], l_maxSumVal[W][i+1])
    
    #
    print(calc_maxSumVal(0,W_max))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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(1, N+1): # watasu=
    v, w = vw[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]
print(max(dp[N]))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

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

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

print(dp[N][-1])

Submission status: Accepted

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


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


# update
for i in range(1, n + 1):
    for j in range(w + 1):
        if j - item[i - 1][1] >= 0:
            dp[i][j] = max(dp[i - 1][j - item[i - 1][1]] + item[i - 1][0], dp[i - 1][j])
            pass
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[n][w])

Submission status: Accepted

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

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

print(DP[-1][-1])

Submission status: Accepted

Solution code:
n,m=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]*(m+1)
old=[0]*(m+1)
for i in range(n):
    for j in range(1,m+1):
        if j>=w[i]:
            dp[j]=max(old[j],old[j-w[i]]+v[i])
    old=dp.copy()
print(dp[m])

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 reversed(range(N)):
	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 = map(int, input().split())
V = []
for i in range(N):
    V.append(list(map(int, input().split())))
    
DP = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

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

Submission status: Accepted

Solution code:
from pprint import pprint

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):
    for j in range(W+1):
        v = vw[i][0]
        w = vw[i][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]
# pprint(dp)
print( dp[n][W] )

Submission status: Accepted

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

# dp[選択する要素の番号][この重さを超えないレベルで] = 価値の最大値となるような二次元配列
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    for w in range(W+1):
        value, weight = vw[i]
        # wを超えない重さであれば、前の要素番号まででこの重さを引いた数値の価値と今回の価値を足したものが上回れば今回の価値とする
        if w >= weight:
            dp[i+1][w] = max(dp[i][w], dp[i][w-weight] + value)
        # wを超えるのであれば選択できないので、前の要素番号までの価値と同じ価値
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
VW = [tuple(map(int, input().split())) for i in range(n)]
V = [v for v, w in VW]
W = [w for v, w in VW]
# n, m = 4, 5
# V = [4, 5, 2, 8]
# W = [2, 2, 1, 3]
# DP[i][j]=i個の品物で重さj以内で最大価値
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(m+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][m])

Submission status: Accepted

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

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

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

dps = [[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 >= weights[i]:
            dps[i][j] = max(dps[i - 1][j], dps[i - 1]
                            [j - weights[i]] + values[i])
        else:
            dps[i][j] = max(dps[i - 1][j], dps[i][j - 1])
# print(dps)
print(dps[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 for _ in range(W+1)]  for _ in range(N+1)]

for i in range(1,N+1): #品物番号
    for j in range(1,W+1): # ナップサック容量
        maxi=0
        if j-w[i-1]>=0:
            maxi = max(maxi, dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])
        else:
            maxi = max(maxi, dp[i-1][j])
        dp[i][j]=maxi
    
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, W = map(int, input().split())
    vw = [list(map(int, input().split())) for _ in range(N)]

    # i個目まで使って重さj以下の場合の最大価値
    dp = [[0]*(W+1) for _ in range(N+1)]

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

#knapsack
dp=[[0]*(w0+1) for _ in range(n+1)]
#print(dp)
for i in reversed(range(n)):
	for j in range(w0+1):
		if j-w[i]<0:
			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][w0])

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
if __name__ == '__main__':
	N, W = map(int, input().split())
	items = []
	for i in range(N):
		items.append(list(map(int, input().split())))

	dp = [0] * (W + 1)
	
	for item in items:
		v, w = item
		for i in reversed(range(W - w + 1)):
			if dp[i + w] < dp[i] + v:
				dp[i + w] = dp[i] + v
	print(max(dp))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import copy
n, w = map(int, input().split())
V = []
W = []
for i in range(n):
  vi, wi = map(int, input().split())
  V.append(vi)
  W.append(wi)
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):
    vi, wi = V[i], W[i]
    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)
print(dp[-1][-1])

Submission status: Accepted

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

values = []
weights = []

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

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):
        w = weights[i-1]
        v = values[i-1]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N,W=map(int,input().split())
    v,w=[0]*N,[0]*N
    for i in range(N):
        v[i],w[i]=map(int,input().split())
    dp=[[0]*2*10**5 for _ in range(N+1)]
    for i in range(N):
        for weight in range(W+1):
            dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight])
            if weight-w[i]>=0:
                dp[i+1][weight]=max(dp[i+1][weight],dp[i][weight-w[i]]+v[i])
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())  # N個の品物, 容量Wのナップサック
items = [list(map(int, input().split())) for _ in range(N)]  # v, w
dp = [[0]*(W+1) for _ in range(N+1)]  # i番目までの品物を使ったときに、重さWで実現できる最大の価値
dp[0][0] = 0  # 雰囲気だけで行う初期化
for i in range(N):  # N個の品物について
    for j in range(W+1):
        # 使わない場合
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        # 使う場合
        if j + items[i][1] > W:
            continue
        dp[i+1][j+items[i][1]] = max(dp[i+1][j+items[i][1]], dp[i][j]+items[i][0])

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

Submission status: Accepted

Solution code:
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())

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

# for i in range(N):
#  dp[i][0] = 0

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

# ナップザックDP
for i in range(N):
  for j in range(W+1):
    if j >= w[i]:
      dp[i+1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]
print(dp[N][W])