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())
VW = [list(map(int, input().split())) for i in range(N)]
# N番目までの品物からWを超えないように選んだ時の最大価値合計
dp = [[0] * (W+1) for i in range(N+1)]

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

print(dp[N][W])

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[i]:重さiを超えないように選んだ時の最大価値合計
dp = [0] * (W+1)

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

print(dp[W])

Submission status: Accepted

Solution code:
#!/usr/bin/env python


def knapsack(N,W,values,weights):
    dp = [[0 for j in range(W+1)] for i in range(N+1)]

    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]

    return dp[N][W]


tmp = [int(x) for x in input().split()]
N = tmp[0]
W = tmp[1]

values = []
weights = []
for i in range(N):
    tmp = [int(x) for x in input().split()]
    values.append(tmp[0])
    weights.append(tmp[1])

print(knapsack(N,W,values,weights))

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 = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if w[i] > j:
            dp[i+1][j] = 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:
# -*- coding: utf-8 -*-


if __name__ == '__main__':

    N, W = map(int, input().split())
    I = [None] + [list(map(int, input().split())) for _ in range(N)]
    C = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

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

    print(C[N][W])

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

print(dp[n][W])

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

print(dp[n][w])

Submission status: Accepted

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

value_weight = {}
value_list = []
weight_list = []
input_data = input().split()
N, W = map(int, input_data)
for i in range(int(N)): 
    input_data = input().split()
    v, w = map(int, input_data)
    value_list.append(v)
    weight_list.append(w)

value_weight = [[0 for i in range(10010)] for j in range(110)]

for i in range(N):
    for w in range(W + 1):
        if w >= weight_list[i]:
            value_weight[i + 1][w] = max(value_weight[i][w - weight_list[i]] + value_list[i], value_weight[i][w])
        else:
            value_weight[i + 1][w] = value_weight[i][w]
print(value_weight[N][W])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
#dp[何番目の品物][重さ]
dp = [[-1 for i in range(W+1)] for j in range(N+1)]

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

# i:i番目の荷物 empty:残り容量
def rec(i, empty):
  if dp[i][empty] != -1:
    return dp[i][empty]

  res = 0
  if i == N:
    pass
  elif empty < items[i][1]:
    res = rec(i+1, empty)
  else:
    res = max(rec(i+1, empty), rec(i+1, empty - items[i][1]) + items[i][0])

  dp[i][empty] = res
  return res

print(rec(0, W))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May  5 11:31:13 2018
Napsack problem
@author: maezawa
"""

n, wmax = list(map(int, input().split()))
v = []
w = []
for i in range(n):
    vi, wi = list(map(int, input().split()))
    v.append(vi)
    w.append(wi)

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

for i in range(n):
    for j in range(wmax+1):
        if j-w[i] < 0:
            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][wmax])

Submission status: Accepted

Solution code:
import math

N, W = map(int,input().split(' ') )
#print(N,W)
v=[]
w=[]

for i in range(N):
    v1,w1 =map(int,input().split(' ') )
    v.append(v1)
    w.append(w1)
    
inf = 0
# dp[i]: i番目以降の最大のvalue
dp = [ [ inf for j in range(W+1) ] for i in range(N+1) ]

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

print(dp[N][W])

Submission status: Accepted

Solution code:
import queue


def main():
    N, W = map(int, input().split())

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

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

    v = []
    w = []

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

    for i in range(N):
        for j in range(W + 1):

            dp[i + 1][j] = dp[i][j]

            if w[i] <= j:
                dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])

    print(dp[N][W])

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import namedtuple

if __name__ == '__main__':
    Item = namedtuple('Item', 'v w')
    N, W = map(int, input().split())
    lisItem = [Item(*map(int, input().split())) for _ in range(N)]
    #print(lisItem)
    dp = [[0 for _ in range(W + 1)] for __ in range(N + 1)]
    for i in range(0, N):
        for w in range(W + 1):
            if lisItem[i].w <= w:
                dp[i+1][w] = max(dp[i][w-lisItem[i].w] + lisItem[i].v, 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())
I=[[*map(int,input().split())]for _ in[0]*N]
I=[0]+I
C=[[0]*-~W for _ in[0]*-~N]
G=[[0]*-~W for _ in[0]*-~N]
for i in range(1,N+1):
 for w in range(1,W+1):
  C[i][w]=C[i-1][w]
  if I[i][1]>w:continue
  if I[i][0]+C[i-1][w-I[i][1]]>C[i-1][w]:
   C[i][w]=I[i][0]+C[i-1][w-I[i][1]]
   G[i][w]=1
m=C[N][W]
w=W
D=[]
for i in range(N,0,-1):
 if G[i][w]:
  D+=[i]
  w-=I[i][1]
print(C[N][W])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
I=[0]+[[*map(int,input().split())]for _ in[0]*N]
C=[[0]*-~W for _ in[0]*-~N]
for i in range(1,N+1):
 for w in range(1,W+1):
  C[i][w]=C[i-1][w]
  if I[i][1]>w:continue
  if I[i][0]+C[i-1][w-I[i][1]]>C[i-1][w]:
   C[i][w]=I[i][0]+C[i-1][w-I[i][1]]
print(C[N][W])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
I=[0]+[[*map(int,input().split())]for _ in[0]*N]
C=[[0]*-~W for _ in[0]*-~N]
for i in range(1,N+1):
 for w in range(1,W+1):
  C[i][w]=C[i-1][w]
  if w>=I[i][1]and I[i][0]+C[i-1][w-I[i][1]]>C[i-1][w]:
   C[i][w]=I[i][0]+C[i-1][w-I[i][1]]
print(C[N][W])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
I=[[*map(int,input().split())]for _ in[0]*N]
C=[0]*-~W
for i in range(1,N+1):
 v,w=I[~-i]
 for j in range(W,w-1,-1):
  t=v+C[j-w]
  if t>C[j]:C[j]=t
print(C[W])

Submission status: Accepted

Solution code:
import sys
W=int(input().split()[1])
C=[0]*-~W
for e in sys.stdin:
 v,w=map(int,e.split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[i]=t
print(C[W])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
C=[0]*-~W
for _ in[0]*N:
 v,w=map(int,input().split())
 for i in range(W,w-1,-1):
  t=v+C[i-w]
  if t>C[i]:C[i]=t
print(C[W])

Submission status: Accepted

Solution code:
import sys
def s():
 W=int(input().split()[1])
 C=[0]*-~W
 for e in sys.stdin:
  v,w=map(int,e.split())
  for i in range(W,w-1,-1):
   t=v+C[i-w]
   if t>C[i]:C[i]=t
 print(C[W])
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
import sys
def s():
 W=int(input().split()[1])
 C=[0]*-~W
 for e in sys.stdin:
  v,w=map(int,e.split())
  for i in range(W,w-1,-1):
   t=v+C[i-w]
   if t>C[i]:C[i]=t
 print(C[W])
s()

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

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

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
d=[0]*(m+1)
for i in range(n):
    v,w=map(int,input().split())
    for j in range(m+1-w):
        if d[m-j]<d[m-j-w]+v:
            d[m-j]=d[m-j-w]+v
print(max(d))

Submission status: Accepted

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

dp = [[-1 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 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:
# -*- coding: utf-8 -*-
"""
Created on Fri May 25 22:23:44 2018
Knapsack by memorized recursive call
@author: maezawa
"""

n, maxw = list(map(int, input().split()))
w = []
v = []
dp = [[None for _ in range(maxw+1)] for _ in range(n)]

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

def total_value(i, wi):
    if i == n:
        return 0
    if dp[i][wi] != None:
        return dp[i][wi]
    if wi < w[i]:
        dp[i][wi] = total_value(i+1,wi)
    else:
        dp[i][wi] = max(total_value(i+1,wi), total_value(i+1,wi-w[i])+v[i])
    return dp[i][wi]

print(total_value(0, maxw))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

for i in range(1, n+1):
    v_i, w_i = items[i-1]
    for j in range(1, w+1):
        if j - w_i < 0:
            table[i][j] = max(table[i][j-1], table[i-1][j])
        else:
            new_val = table[i-1][j-w_i] + v_i
            if new_val > table[i][j-1]:
                table[i][j] = max(new_val, table[i][j-1], table[i-1][j])
            else:
                table[i][j] = max(table[i][j-1], table[i-1][j])

print(table[-1][-1])

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
items = []
for i in range(N):
    v, w = map(int, input().split())
    items.append([v, w])
dp = [[0 for j in range(W+1)] for i in range(N+1)]
for i in range(1, N+1):
    iv = items[i-1][0]
    iw = items[i-1][1]
    for j in range(1, W+1):
        if iw <= j: dp[i][j] = max(dp[i-1][j-iw] + iv, dp[i-1][j])
        else: dp[i][j] = dp[i-1][j]
print(dp[N][W])

Submission status: Accepted

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

items=[]

for i in range(N):
    items.append(list(map(int,input().split())))
    
dp = [[0 for i in range(10001)] for j in range(110)]

for i in range(N):
    dp[i][0]=0
    
for i in range(N):
    for w in range(W+1):
        if w>=items[i][1]:
            dp[i+1][w]=max(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:
N, W = [int(i) for i in input().split(" ")]
VW = [[int(j) for j in 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 w in range(1, W + 1):
        if w < VW[i][1]:
            dp[i + 1][w] = dp[i][w]
        else:
            dp[i + 1][w] = max([dp[i][w], dp[i][w - VW[i][1]] + VW[i][0]])

print(max(dp[N]))

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

vMax = 0
wMax = 0
for i in range(n):
    vMax = max(vMax, a[i][0])
    wMax = max(wMax, a[i][1])

if n <= 30:
    val = []
    if a[0][1] <= w:
        val.append(a[0])

    for i in range(1, n):

        j = 0
        valTemp = val[:]
        while j < len(valTemp):
            k = 0
            if valTemp[j][1] + a[i][1] <= w:
                temp = [valTemp[j][0] + a[i][0], valTemp[j][1] + a[i][1]]
                while k < len(val):
                    if val[k][0] == temp[0]:
                        if temp[1] < val[k][1]:
                            val[k] = temp
                        break
                    elif val[k][0] > temp[0]:
                        if temp[1] < val[k][1]:
                            val.insert(k, temp)
                        break

                    k += 1
                else:
                    val.append(temp)
            j += 1

        if a[i][1] <= w:
            temp = a[i]
            j = 0
            while j < len(val):
                if val[j][0] == temp[0]:
                    if temp[1] < val[j][1]:
                        val[j] = temp
                    break
                elif val[j][0] > temp[0]:
                    if temp[1] < val[j][1]:
                        val.insert(j, temp)
                    break

                j += 1
            else:
                val.append(temp)
        
        j = len(val) - 2

        while j >= 0:
            if val[j][1] >= val[j + 1][1]:
                del val[j]
            j -= 1

    print(val[len(val) - 1][0])

elif wMax <= 1000:
    w = min(w, wMax * n)
    dp = [0 for _ in range(w + 1)]
    for i in range(n):
        for j in range(w, a[i - 1][1] - 1, -1):
            dp[j] = max(dp[j], dp[j - a[i - 1][1]] + a[i - 1][0])

    print(max(dp))
else:
    m = n + vMax
    dp = [0 for _ in range(m + 1)]
    for i in range(n):
        for j in range(m , a[i - 1][0] - 1, -1):
            dp[j] = min(dp[j], dp[j - a[i - 1][0]] + a[i - 1][1])

    ans = 0
    for i in range(n * vMax):
        if dp[n][i] != 0:
            ans = max(ans, i)
 
    print(ans)

Submission status: Accepted

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

value = []
weight = []

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

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

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

print(dp[w])

Submission status: Accepted

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

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
# AIZU 0-1 Knapsack Problem
reader = input().split(' ')
item_num = int(reader[0])
w_max = int(reader[1])

value = []
weight = []
for i in range(item_num):
    reader = input().split(' ')
    value.append(int(reader[0]))
    weight.append(int(reader[1]))

dp_table = [[0 for i in range(w_max+1)] for j in range(item_num+1)]

for i in range(item_num):
    for w in range(w_max+1):
        if w >= weight[i]:
            dp_table[i+1][w] = max([dp_table[i][w-weight[i]] + value[i], dp_table[i][w]])
        else:
            dp_table[i+1][w] = dp_table[i][w]

print(str(dp_table[item_num][w_max]))

Submission status: Accepted

Solution code:
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C[item_w:], C)):
            v1, v2 = vals
            v1 += item_v
            if v1 > v2:
                C[i] = v1
    print(C[0])

solve()

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
v=[0]*1010
w=[0]*1010
for i in range(1,N+1):
    x,y=map(int,input().split())
    v[i]=x
    w[i]=y
    
a=[[0 for i in range(W+1)]for j in range(N+1)]
a[0][W]=0
for i in range(1,N+1):
    for j in range(1,1+W):
        if w[i]<=j:
            a[i][j]=max(a[i-1][j-w[i]]+v[i],a[i-1][j])
        else:
            a[i][j]=a[i-1][j]
print(a[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 v in item:
    for i in range(1,w+2):
        if w+1-i+v[1] <= w:
            dp[w+1-i+v[1]] = max(dp[w+1-i+v[1]],dp[w+1-i]+v[0])
print(dp[w])

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
value = []
weight = []

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

#初期化
inf = float("inf")
dp = [[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0

#DP
for i in range(N):
    for w in range(W+1):
        if weight[i] <= w:
            dp[i+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_arr, w_arr = [], []
for _ in range(N):
    v, w = map(int, input().split())
    v_arr.append(v)
    w_arr.append(w)

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
dp[0][W] = 0
for i in range(N):
    for w in range(W+1):
        if w >= w_arr[i]:
            dp[i+1][w] = max(dp[i][w - w_arr[i]] + v_arr[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,raw_input().split())

weights = []
values = []

for i in range(n):
	val,wei = map(int,raw_input().split())
	values.append(val)
	weights.append(wei)

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

dp[0][0] = 0

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

print max(dp[n])

Submission status: Accepted

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

for i in range(N):
    shina.append(list(map(int, input().split())))


def memoize(f):
    table = {}

    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func


@memoize
def dp(n, w):
    if n == 0:
        return 0
    elif w - shina[n - 1][1] >= 0:
        return max(dp(n - 1, w), dp(n - 1, w - shina[n - 1][1]) + shina[n - 1][0])
    else:
        return dp(n - 1, w)


print(dp(N, W))

Submission status: Accepted

Solution code:
N, W = map(int, raw_input().split())
v = [0] * N
d = [0] * N
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
for i in range(N):
  v[i], d[i] = map(int, raw_input().split())
  for j in range(W + 1):
    if j < d[i]:
      dp[i + 1][j] = dp[i][j];
    else:
      dp[i + 1][j] = max(dp[i][j], dp[i][j - d[i]] + v[i])
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 i in range(N):
    value = v[i]; weight = w[i]
    for sum_w in range(W,0,-1):
        if sum_w - weight >= 0:
            DP[sum_w] = max(DP[sum_w], DP[sum_w - weight] + value)

print(DP[W])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readlines

lines = input()

n, W = list(map(int, lines[0].split()))

items = [None] * (n+1)

T = [[0] * (W+1) for i in range(n+1)]
G = [[0] * (W+1) for i in range(n+1)]


for i in range(n):
    items[i+1] = list(map(int, lines[i+1].split()))

for i in range(1, n+1):
    for w in range(1, W+1):
        k = items[i][1]
        if k > w:
            G[i][w] = "top"
            T[i][w] = T[i-1][w]
        else:
            a = T[i-1][w - k] + items[i][0]
            b = T[i-1][w]
            if a > b:
                G[i][w] = "diagonal"
                T[i][w] = a
            else:
                G[i][w] = "top"
                T[i][w] = b

print(T[n][W])

Submission status: Accepted

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

dp = [[0]*(w+10) for _ in range(n+10)]
weight = [0] * (n+10)
value = [0] * (n+10)

for i in range(n):
    value[i] = li[i][0]
    weight[i] = li[i][1]
    
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[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)]
items = [list(map(int, input().split())) for _ in range(N)]
for i in range(1, N+1):
    div = min([items[i-1][1], W+1])
    for j in range(0, div):
        dp[i][j] = dp[i-1][j]
    for j in range(div, W+1):
        dp[i][j] = max([dp[i-1][j], dp[i-1][j-items[i-1][1]] + items[i-1][0]])
print(dp[-1][-1])

Submission status: Accepted

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

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:
import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    vw = [None] * N
    for i in range(N):
        vw[i] = tuple(map(int, input().split()))

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

    ans = max(dp[-1])
    print(ans)


if __name__ == "__main__":
    main()

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 n_i in range(1, n+1):
  for w_i in range(w+1):
    if w_i-VW[n_i-1][1]>=0:
      DP[n_i][w_i] = max(DP[n_i-1][w_i], DP[n_i-1][w_i-VW[n_i-1][1]]+VW[n_i-1][0])
    else:
      DP[n_i][w_i] = DP[n_i-1][w_i]
      
print(max(DP[-1]))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N, W = MI()
    mylist = [LI() for i in range(N)]
    d = [[0 for i in range(W+1)] for j in range(1+N)]
    for i in range(N):
        v, w = mylist[i]
        for j in range(W+1):
            if w > j:
                d[i+1][j] = max(d[i][j], d[i+1][j])
            else:
                d[i+1][j] = max(d[i][j], d[i+1][j], d[i][j-w]+v)
    print(d[N][W])
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
dp=[[0]*(w+1) for _ in range(n+1)]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(w+1):
    if j>=b:dp[i+1][j]=max(dp[i][j],dp[i][j-b]+a)
    else:dp[i+1][j]=dp[i][j]
print(dp[n][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())
items = [None]*n
for i in range(n):
    v,w = map(int,input().split())
    items[i] = item(v,w)
    
dp = [[None]*(W+1) for _ in range(n+1)]
dp[0] = [0]*(W+1)

for i in range(1,n+1):
    for w in range(W+1):
        max_value = dp[i-1][w]
        if w-items[i-1].w>=0:
            max_value = max(max_value,dp[i-1][w-items[i-1].w]+items[i-1].v)
        dp[i][w] = max_value
        
print(dp[n][W])

Submission status: Accepted

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

w=[]
v=[]


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


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