Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
weights=[[float("inf")]*(10**5+1) for i in range(n+1)]
for i in range(n):
    weights[i+1][wv[i][1]]=min(weights[i+1][wv[i][1]], wv[i][0])
    for j in range(10**5+1):
        if weights[i][j]!=0:
            weights[i+1][j]=min(weights[i+1][j], weights[i][j])
            if weights[i][j]+wv[i][0]<=w:
                weights[i+1][j+wv[i][1]]=min(weights[i+1][j+wv[i][1]], weights[i][j]+wv[i][0])

for i in range(10**5+1):
    if weights[-1][10**5-i]!=float("inf"):
        print(10**5-i)
        quit()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
V = max([wv[i][1] for i in range(N)]) * N

dp = [[float('inf')] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N) :
    for j in range(V+1) :
        if j >= wv[i][1] :
            dp[i+1][j] = min(dp[i][j-wv[i][1]] + wv[i][0], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]

for i in range(V, -1, -1) :
    if dp[N][i] <= W :
        print(i)
        break

Submission status: Accepted

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

def knapsack01(items, capW):
    dp = {0: 0}
    for wi, vi in sorted(items, key=lambda x: x[1]):
        for v, w in list(dp.items()):
            v2 = v + vi
            if w+wi <= capW:
                w2 = w + wi
                if v2 in dp:
                    if w2 < dp[v2]:
                        dp[v2] = w2
                else:
                    dp[v2] = w2
    return max(dp.keys())

print(knapsack01(items, capW))

Submission status: Accepted

Solution code:
INF = float('inf')

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

def knapsack01(items, capW, INF):
    sumV = sum([v for w, v in items])
    dp = [0] + [INF]*sumV
    accV = 0
    for wi, vi in sorted(items, key=lambda x: x[1]):
        accV += vi
        for v in reversed(range(vi, min(sumV, accV)+1)):
            w0 = dp[v-vi] + wi
            if w0 < dp[v]:
                dp[v] = w0
    for v in reversed(range(sumV+1)):
        if dp[v] <= capW:
            return v

print(knapsack01(items, capW, INF))

Submission status: Accepted

Solution code:
import numpy as np
n,a=map(int,input().split())
s=np.full(n*1000+1,a+1)
s[0]=0
for i in range(n):
    w,v=map(int,input().split())
    s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=a)))

Submission status: Accepted

Solution code:


# N個の荷物、ナップザックの容量はW
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

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

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする

# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = N*1000+1
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Accepted

Solution code:
n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

f = [float("inf") for i in xrange(100001)]
f[0] = 0

for _ in xrange(n):
    w, v = [int(i) for i in raw_input().split()]
    
    for x in range(100000-v, -1, -1):
        f[x+v] = min(f[x+v], f[x] + w)

# print f[:100]

a = max([i for i in xrange(100001) if f[i] <= s])
print a

Submission status: Accepted

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

vsum=sum([wv[k][1] for k in range(N)])

#dp[i個目までの品物][価値がv]→価値がvとなるような重さの最小値
dp=[[sys.maxsize]*(vsum+2) for _ in range(N+1)]
for k in range(N):
    dp[k][0]=0


for i in range(N):
    for v in range(vsum+1):
        if dp[i][v]+wv[i][0]<=W:
            dp[i+1][v+wv[i][1]]=min(dp[i+1][v+wv[i][1]],dp[i][v]+wv[i][0])
        dp[i+1][v]=min(dp[i+1][v],dp[i][v])


#dpがW以下となる最大のvを求める
for x in range(vsum,-1,-1):
    for y in range(N,-1,-1):
        if dp[y][x]<=W:
            print(x)
            break
    else:continue
    break

Submission status: Accepted

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

v_max = 10**3 * 10**2
memo = [float("inf") for _ in range(v_max+1)]
memo[0] = 0

for weight,value in wv_list:
    for v in range(v_max+1-value)[::-1]:
#         if memo[v]:
        memo[v+value] = min(memo[v]+weight, memo[v+value])

ans = 0

for i,m in enumerate(memo):
    if m <= W:
        ans = i

print(ans)

Submission status: Accepted

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



max_sum = sum([i[1] for i in A])

max_value=10**10
dp = [[max_value for i in range(max_sum+1) ] for j in range(N+1)]
dp[0][0]=0

for i in range(N):
    for v in range(max_sum+1):
        if v>=A[i][1]:
            dp[i+1][v] = min([dp[i][v-A[i][1]]+A[i][0], dp[i][v]])

        else:
            dp[i+1][v] = dp[i][v]

#ここでindexは価値と同値、複数あることを考慮して反転後indexで最も価値のある個所を取得
# try:
#     print(max_sum-dp[N][::-1].index(W))
# except:
#     print(max_sum-dp[N][::-1].index(W))
for i,w in enumerate(dp[N][::-1]):
    if w <=W:
        print(max_sum-i)
        break
#     print(int(dp[N][W]))

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
wv = [[int(x) for x in input().split()] for i in range(N)]
MAX_V = 1000*100 + 1
dp = [[0 if j==0 else 10**12 for j in range(MAX_V+1)] for i in range(N+1)]
for i in range(N):
    for sum_v in range(MAX_V+1):
        if wv[i][1] + sum_v < MAX_V+1 and dp[i+1][wv[i][1]+sum_v] > dp[i][sum_v] + wv[i][0]:
            dp[i+1][wv[i][1]+sum_v] = dp[i][sum_v] + wv[i][0]
        if dp[i+1][sum_v] > dp[i][sum_v]:
            dp[i+1][sum_v] = dp[i][sum_v]
result=0
for i in range(MAX_V+1):
    if dp[N][i] < W+1:
        result = i
print(result)

Submission status: Accepted

Solution code:
def p_e():
    N, W = map(int, input().split())
    max_value = 10 ** 3 * N + 1
    dp = [W + 1] * max_value
    dp[0] = 0
    for _ in range(1, N + 1):
        w, v = map(int, input().split())
        NEXT = [W + 1] * max_value
        NEXT[0] = 0
        for i in range(1, max_value):
            if i - v >= 0:
                NEXT[i] = min(dp[i - v] + w, dp[i])
            else:
                NEXT[i] = dp[i]
        dp = NEXT

    ans = 0
    for i, w in enumerate(dp):
        if w <= W:
            ans = i
    print(ans)


if __name__ == '__main__':
    p_e()

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int,input().split())
#N,W = [3,8]
wvlist = [list(map(int,input().split())) for _ in range(N)]
INF = 10**15
ans = INF

#初期条件
#dp = [[INF for _ in range(N*1000+1)] for i in range(N+1)]
dp = np.full((N+1,N*1000+1),INF)
dp[0][0] = 0

for i in range(N):
    dp[i+1][:wvlist[i][1]] = dp[i][:wvlist[i][1]]
    dp[i+1][wvlist[i][1]:] = np.minimum(dp[i][wvlist[i][1]:],dp[i][:-wvlist[i][1]]+wvlist[i][0])
        
for i in range(N*1000+1):
    if W >= dp[N][i]:
        ans = i
        
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import numpy as np




def main():
    num, lim_weight = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    dp = np.full(10 ** 5 + 1, np.inf)

    for i in range(num):
        weight, value = data[i]
        prev = dp.copy()
        dp[:value] = np.minimum(prev[:value], weight)
        dp[value:] = np.minimum(prev[value:], prev[:-value] + weight)

        # print(dp[:100])
    ans = np.max(np.where(dp <= lim_weight)) + 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

def main():
	N, W = map(int, input().split())
	dp = np.full(N * 1000 + 1, 10 ** 10, dtype=np.int64)
	dp[0] = 0
	for _ in range(N):
		w, v = map(int, input().split())
		np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
	print(((dp <= W) * np.arange(N * 1000 + 1)).max())

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N, W = map(int, input().split())
MV = N * 10**3 + 1
INF = float('inf')
dp = [[INF] * MV for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(MV):
        if v <= j:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
        else:
            dp[i+1][j] = dp[i][j]
dp = dp[N]
for i in range(0, MV)[::-1]:
    if dp[i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [float('inf')] * (10**5 + 1)
    dp[0] = 0

    for w, v in items:
        for value in range(10**5 + 1)[:: -1]:
            if value - v >= 0:
                dp[value] = min(dp[value], dp[value - v] + w)

    ans = 0
    for v in range(10**5 + 1)[:: -1]:
        if dp[v] <= W:
            ans = v
            break

    print(ans)


sol()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = map(int, readline().split())
  maxv = 10 ** 3 * n + 1
  t = [-1] * maxv
  t[0] = w
  cmaxv = 0
  for _ in range(n):
    nw, nv = map(int, readline().split())
    for i in range(cmaxv, -1, -1):
      ti = t[i]
      if ti == -1:
        continue
      if t[i + nv] < ti - nw:
        t[i + nv] = ti - nw
        if cmaxv < i + nv:
          cmaxv = i + nv
  print(cmaxv)
main()

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]+[float("inf")]*(10**5)#dp[k]:価値kにおける最小重さ
for i in range(n):#あるi番目の品物について
    for j in range(10**5,wv[i][1]-1, -1):#ある価値jについて
        dp[j] = min( dp[j], dp[j-wv[i][1]]+wv[i][0] )
        #重さwv[i][0]であるi番目の品物を使うほうが価値jでの最小重さdp[j]が小さい場合は値を更新

res = 0
for v,e in enumerate(dp):#インデックスv(=ある価値j)における最小重さeについて
    if e <= w:
        res = v#最小重さが重さ制限を超えないならres更新
print(res)

Submission status: Accepted

Solution code:
def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[0] = target
    max_ = 0

    for vi in range(len(V)):
        we, va = W[vi], V[vi]
        for i in range(max_, -1, -1):
            if i in P:
                piva = P.get(i + va, -1)
                if piva < P[i] - we:
                    P[i + va] = P[i] - we
                    if max_ < i + va:
                        max_ = i + va
    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Submission status: Accepted

Solution code:
import sys

# 商品の数，ナップサックの許容重量
n, c = list(map(int, input().split()))

# 制約より起こり得る商品価値の総和の最大値+余分
M = (10 ** 3) * n + 10

# n=1のときの例外処理
if n == 1:
    w, v = map(int, input().split())
    ans = v if c >= w else 0
    print(ans)
    sys.exit()

# DPリスト
dp = [[float("inf")] * M for i in range(n)]
dp[-1][0] = 0

for i in range(n):
    w, v = map(int, input().split())
    # 配るDP
    for j in reversed(range(M)):
        dp[i][j] = dp[i - 1][j]
        if j + v < M:
            dp[i][j + v] = min(dp[i - 1][j + v], dp[i - 1][j] + w)

ans = 0
for i in range(M):
    if dp[-1][i] <= c:
        ans = max(i, ans)

print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[0 for i in range(N+1)]
v=[0 for i in range(N+1)]
for i in range(1,N+1):
  w[i],v[i]=map(int,input().split())
N_max=max(v[i] for i in range(N+1))
INF=float('inf')
dp=[[INF for i in range(N*N_max+1)]for j in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  for j in range(N*N_max+1):
    if v[i]<=j:
      dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    else:
      dp[i][j]=dp[i-1][j]
ans=0
for i in range(1,N*N_max+1):
  if dp[N][i]<=W:
    ans=i
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

table = np.full(sum(v)+1, np.inf)
table[0] = 0

for i in range(n):
    l = table[:-v[i]]
    r = table[v[i]:]
    np.minimum(l + w[i], r, out = r)
    
print(np.max(np.where(table <= W)))

Submission status: Accepted

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

def main():
    N, W = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    lim = 10 ** 5
    dp = [0] + [float("inf")] * lim
    for i in range(N):
        for j in range(lim, A[i][1] - 1, -1):
            dp[j] = min(dp[j], dp[j - A[i][1]] + A[i][0])
    ans = [i for i, j in enumerate(dp) if j <= W]
    print(max(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# dpE - Knapsack 2
import sys
input = sys.stdin.readline

def heavy_knapsack(W: int, weight: "Array[int]", value: "Array[int]") -> int:
    lim = sum(value)
    dp = [0] + [float("inf")] * lim  # dp[i] := minimum weight of value i
    for w, v in zip(weight, value):
        for cur_v in range(lim, v - 1, -1):
            dp[cur_v] = min(dp[cur_v], dp[cur_v - v] + w)
    ret = max(v for v, w in enumerate(dp) if w <= W)
    return ret


def main():
    N, W = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    w, v = zip(*A)
    ans = heavy_knapsack(W, w, v)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

dp = [[10 ** 9 + 1] * V for _ in range(N + 1)]
dp[0][0] = 0

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

ans = 0
for v in range(V):
    if dp[N][v] <= W:
        ans = v
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
ndp = np.full(1000*100+1, 10**11, dtype=np.int64)
ndp[0] = 0

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

    np.minimum(ndp[:-v] + w, ndp[v:], out = ndp[v:])

print(np.max(np.where(ndp<=W)))

"""
https://atcoder.jp/contests/dp/submissions/6646897
から失敬

貪欲法はこの手の書き方で表現できるっぽい。
価値テープのなかで同価値のindexでは、より少ない重量の物品で済む方を残していく。
したがってテープの初期化は擬似infで行い、価値0の部分は重さも0で始める。

"""

Submission status: Accepted

Solution code:
n,W=map(int,raw_input().split())
w=[]
val=[]
for i in range(n):
    p=map(int,raw_input().split())
    w.append(p[0])
    val.append(p[1])
to = sum(val)    
dp = [float("inf")]*(to+1)
dp[0]=0
for i in range(n):
    for j in range(to,val[i]-1,-1):
        dp[j]=min(dp[j],dp[j-val[i]]+w[i])
for i in range(to,-1,-1):
    if(dp[i]<=W):
        print i
        exit()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

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

# v に対する min(w) を持つ
max_v = 0
INF = 10 ** 18
dp = np.full(1000 * N + 1, INF, dtype=np.int64)
dp[0] = 0
for _ in range(N):
    w,v = map(int,input().split())
    np.minimum(dp[v:max_v + v + 1], dp[:max_v + 1]+w, out = dp[v:max_v + v + 1])
    max_v += v

answer = np.where(dp <= W)[0].max()
print(answer)

Submission status: Accepted

Solution code:
N,W,*l = map(int,open(0).read().split())
wl = l[::2]
vl = l[1::2]
M = N*max(vl)
INF = float("inf")
dp = [[INF]*(M+1) for _ in range(N+1)]
dp[0][0] = 0

# minimum weight with value == j
for i in range(N):
	w,v = wl[i],vl[i]
	for j in range(M+1):
		if j >= v:
			dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
		else:
			dp[i+1][j] = dp[i][j]
		
# maximum value provided dp[N][value] <= W
ans=0
for val,wei in enumerate(dp[-1]):
	if wei <= W:
		ans = max(ans,val)
print(ans)