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:
#EDP-E
import sys
from collections import defaultdict
n, W = map(int, sys.stdin.readline().split())

dp = [defaultdict(int) for _ in range(n)]
w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    for vb, wb in dp[i-1].items():
        dp[i][vb] = min(wb, dp[i].get(vb, wb))
        tmp = min(wb + w, dp[i].get(vb+ v, wb + w))
        if tmp <=W:
            dp[i][v+ vb] = tmp
    dp[i][v] = min(dp[i].get(v, w), w)

#print(dp[-1].items())
print(max(dp[-1].keys()))

Submission status: Accepted

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

table = {i: [10**10]*(10**5+1) for i in range(N+1)}
table[0][0] = 0
def dp(N, V):
  for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(V+1):
      table[i][j] = min(table[i-1][j-v]+w, table[i-1][j])
  for k in range(V, 0, -1):
    if table[N][k] <= W:
      return k

print(dp(N, 10**5))

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
w, v = [], []
for i in range(n):
	a, b = map(int, input().split())
	w.append(a)
	v.append(b)
sum_v = sum(v)
dp = [float('inf')] * (sum_v + 1)
dp[0] = 0
for i in range(n):
	for j in range(sum_v - v[i], -1, -1):
		dp[j + v[i]] = min(dp[j] + w[i], dp[j + v[i]])
res = 0
for vi, wi in enumerate(dp):
	if wi <= W:
		res = vi
print(res)

Submission status: Accepted

Solution code:
#EDP-E
import sys
n, W = map(int, sys.stdin.readline().split())

dp = [dict() for _ in range(n)]
w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    dp[i][v] = min(w , dp[i].get(v, w))
    for vb, wb in dp[i-1].items():
        dp[i][vb] = min(dp[i].get(vb, wb), wb)
        tmp = min(wb + w, dp[i].get(vb+ v, wb+w))
        if tmp <=W:
            dp[i][v+ vb] = tmp
    #print(dp[i])

print(sorted(dp[-1].items())[-1][0])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
import numpy as np
inf = 10**13
V = 10**5
N, W = map(int, input().split())
dp = np.array([inf]*(V+1), 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(np.where(dp<=W)[0][-1])

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
stones=[None]*N
allv=0
for i in range(N):
  w,v=map(int,input().split())
  allv+=v
  stones[i]=[w,v]
  
import numpy as np
MAXW=10**9+1
dp=np.full(allv+1,MAXW,dtype=int)
dp[0]=0
for i in range(len(stones)):
  w=stones[i][0]
  v=stones[i][1]
  np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])
  
for i in range(len(dp)-1,-1,-1):
  if dp[i]<=W:
    print(i)
    break

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
wv=[tuple(map(int,input().split())) for _ in range(n)]
x=10**5
dp=[[float("inf")]*(x+1) for _ in range(n+1)]
for i in range(1,n+1):
    w,v=wv[i-1]
    dp[i][v]=min(dp[i-1][v],w)
    for j in range(x+1):
        if dp[i-1][j]==float("inf"):
            continue
        if j+v<=x:
            dp[i][j+v]=min(dp[i][j+v],dp[i-1][j]+w)
        dp[i][j]=min(dp[i-1][j],dp[i][j])

ans=0
for i in range(x+1):
    if dp[n][i]<=m:
        ans=i

print(ans)

Submission status: Accepted

Solution code:
#EDP-E
import sys
n,W = map(int, sys.stdin.readline().split())

dp = [[1000000001 for i in range(100001)] for _ in range(n)]


w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    for va in range(100001): #全ての価値を全探索
        if va < v: #上の結果を下に移す
            dp[i][va] = dp[i-1][va]
        else: #va >= v　の場合は va = v + (va-v)
            dp[i][va] = min(dp[i-1][va], dp[i-1][va-v] + w)
    dp[i][v] = min(dp[i][v], w)

ans =0
for v in range(100000,-1,-1): #価値の大きいほうから調べる
    #print(dp[-1][v])
    if dp[-1][v] <=W:
        #print(dp[-1][v], v)
        ans = v
        break
print(ans)

Submission status: Accepted

Solution code:
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])
    UV = np.sum(WV[:, 1])
    UW = np.sum(WV[:, 0])

    dp = np.full([UV+1], UW*2, np.int64)
    dp[0] = 0

    for w, v in WV:
        p_dp = dp.copy()
        np.minimum(dp[v:], p_dp[:-v] + w, out=dp[v:])

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


main()

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]
vMax = 10**5
dp = [[10**9+1 for i in range(vMax + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    wi, vi = wv[i-1]
    for j in range(vMax + 1):
        if vi > j:
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
        else:
            dp[i][j] = min(dp[i- 1][j], dp[i - 1][j - vi] + wi)
for i in range(vMax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, input().rstrip('\n').split()))
    dp = [10 ** 10] * (1000 * n + 1)
    dp[0] = 0
    mw = 0
    for _ in range(n):
        wv, vv = list(map(int, input().rstrip('\n').split()))
        for i in range(1000 * n - vv, -1, -1):
            dp[i+vv] = min(dp[i+vv], dp[i] + wv)
    mt = 0
    for i in range(len(dp)):
        if dp[i] <= w:
            mt = max(mt, i)
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

V = 10**3
dp = [[float('INF')]*(N*(V+1)) for _ in range(N+1)]  # Nとv≦10**3の制約から取りうるvの範囲
dp[0][0] = 0

for i in range(N):
    for v in range((i+1)*(V+1)):
        if v - WV[i][1] >= 0:  # 品物を追加できるとき
            dp[i+1][v] = min(dp[i+1][v], dp[i][v-WV[i][1]] + WV[i][0])
        # できないとき
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])

ans = 0
for i in range(N*(V+1)):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
INF = 2000000000
n,limit_w = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
#limit_w = int(input())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]

# ここからメイン
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1 ,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])

# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
for i in range(sum_v, -1, -1):
    if dp[i] <= limit_w:
	    print(i)
	    break

Submission status: Accepted

Solution code:
INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n,W = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [[INF for i in range(sum_v + 1)] for j in range(n + 1)]
# dp[i][j]には重さが入る.
# dp[i][j]=(i番目までの品物から価値がちょうどｊになるための重さの最小値)

# ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(sum_v + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])

# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
max_value = 0
for i in range(sum_v + 1):
    if dp[n][i] <= W:
        max_value = i
print(max_value)

Submission status: Accepted

Solution code:
INF = 2000000000
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v ,-1,-1):
    if dp[i] <= limit_w:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    dp = [10 ** 10] * (10 ** 3 * n + 1)
    dp[0] = 0
    max_v = 0
    for ww, vv in wv:
        for i in range(max_v, -1, -1):
            dp[i+vv] = min(dp[i+vv], dp[i] + ww)
            max_v = max(max_v, i+vv)
    mt = 0
    for i in range(len(dp)):
        if dp[i] <= w:
            mt = max(mt, i)
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(N)]

dp=np.full(10**5+10,10**18,int)
dp[0]=0
for w,v in WV:
  np.minimum(dp[v:], dp[:-v].copy()+w, out=dp[v:])
print(np.where(dp<=W)[0][-1])

Submission status: Accepted

Solution code:
N, W = [int(_) for _ in input().split()]
INF = 1e12
dp = [[INF] * (((10 ** 3) * N) + 10) for _ in range(N + 1)]

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

    for j in range(len(dp[i])):
        if j > sum_v: break
        # if dp[i-1][j] ==INF:continue
        if j < v:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)

    # print(dp[i][:20])
ans = 0
for i, v in enumerate(dp[N]):
    if v <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
WV=[]
for i in range(N):
    WV.append(list(map(int,input().split())))
dp=[[0 for i in range(10**5+1)] for j in range(N+1)]
dp[0][1:]=[10**18 for i in range(10**5)]
for i in range(N+1):
    for j in range(10**5+1):
        if i>0:
            if j-WV[i-1][1]>=0:
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-WV[i-1][1]]+WV[i-1][0])
            else: 
                dp[i][j]=dp[i-1][j]
for i in reversed(range(10**5+1)):
    if dp[N][i]<=W:
        print(i)
        break

Submission status: Accepted

Solution code:
def Knapsack2(W,w,v): # n個の品物(重さw[i],価値v[i]) 総重量W以内での価値の最大化
    n=len(w)
    v_max=10**5+5
    # dp[i] : 価値iの組み合わせを達成する重量の最小値
    dp=[0]+[float('inf') for _ in range(v_max+1)]
    for i in range(n):
        for j in range(v_max,v[i]-1,-1):
            if j >= v[i]:
                dp[j]=min(dp[j],dp[j-v[i]]+w[i])
    ans=0
    for i in range(v_max+1):
        if dp[i]<=W:
            ans=i
    print(ans)

def main():
    n,W = map(int,input().split())
    w=[0 for _ in range(n)]
    v=[0 for _ in range(n)]
    for i in range(n):
        w[i],v[i] = map(int,input().split())
    Knapsack2(W,w,v)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

INF = 9999999999
MAXN = 110
MAXV = 100010
weights = [0]*(MAXN)
values = [0]*(MAXN)

dp = [[INF]*(MAXV) for i in range(MAXN)]
dp[0][0] = 0

for i in range(N):
    weights[i], values[i] = map(int, input().split())
    for sum_v in range(MAXV):
        if sum_v >= values[i]:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],
                                 dp[i][sum_v-values[i]]+weights[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v],
                             dp[i][sum_v])
ans = 0
for sum_v in range(MAXV):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Submission status: Accepted

Solution code:
INF = 2000000000
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])
for i in range(sum_v ,-1,-1):
    if dp[i] <= limit_w:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,W = map(int,readline().split())
m = map(int,read().split())
WV = zip(m,m)

# 価値 -> 最小重さ
INF = 10**18
dp = np.full(10**5+10,INF,np.int64)

dp[0] = 0
for w,v in WV:
    np.minimum(dp[v:], dp[:-v].copy()+w, out=dp[v:])

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

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    t = sum(v)
    l = [m + 1] * (t + 1)
    l[0] = 0
    for i in range(n):
        for j in range(t, v[i] - 1, -1):
            k = l[j - v[i]] + w[i]
            if k < l[j]:
                l[j] = k
    for i in range(t, 0, -1):
        if l[i] <= m:
            print(i)
            break
main()

Submission status: Accepted

Solution code:
def printdp(dp):
    return
    print({i:v for i, v in enumerate(dp) if v < 10000})

def main():
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for _ in range(N)]
    V = sum(v for _, v in wv)
    dp = [0] + [float('inf')] * V
    for wi, vi in wv:
        for i in range(V, vi - 1, -1):
            t = dp[i - vi] + wi
            if t < dp[i]:
                dp[i] = t
    for i in range(V, -1, -1):
        if dp[i] <= W:
            print(i)
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=limit_w<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [[INF for i in range(sum_v + 1)] for j in range(n + 1)] 
# dp[i][j]には重さが入る.
# dp[i][j]=(i番目までの品物から価値がちょうどｊになるための重さの最小値)

# ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(sum_v + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
            
# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
ans = 0
for i in range(sum_v + 1):
    if dp[n][i] <= limit_w:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def main():
    N, W = map(int, readline().split())
    wv = map(int, read().split())
    dp = np.full(10 ** 5 + 1, W + 1, np.int64)
    dp[0] = 0

    for w, v in zip(wv, wv):
        np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
WV = np.array([list(map(int, input().split())) for _ in range(N)])
max_v = np.sum(WV[:, 1])
# dp[i]: 価値iを達成するのに必要な重さの最小値
dp = np.full(max_v+1, W+1, dtype="int64") # 1D
dp[0] = 0

for w, v in WV:
  # 価値i(0 <= i <= max_value-v)の時の重さの最小値に対し
  # 次の荷物を入れて、価値i+vの時の重さの最小値を更新
  np.minimum(dp[:-v]+w, dp[v:], out=dp[v:])

# np.where: 条件にあったindexを出力
print(np.max(np.where(dp<=W))) #

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
#dp=[[0,0] for i in range(w+1)]
dp=[]
for i in range((10**5)+1):
    dp.append([0,float("inf")])
dp[0][0]=1
dp[0][1]=0
it=[]
val=[]
for i in range(n):
    a,b=input().split()
    it.append(int(a))
    val.append(int(b))
for i in range(n):
    x=val[i]
   # dp2=dp[:]
    ac=[]
    for j in range(len(dp)-x,-1,-1):
        if dp[j][0]==1:
            if it[i]+dp[j][1]<=w:
                dp[j+x][1]=min(dp[j+x][1],it[i]+dp[j][1])
                ac.append(j+x)
   # print(dp)
    for i in ac:
        dp[i][0]=1
  #  print(dp,dp2)
print(max([j for j,i in enumerate(dp) if i[0]==1]))

Submission status: Accepted

Solution code:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF = 2000000000
n, W = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
V = sum(v)
dp = [[INF for i in range(V + 1)] for j in range(n + 1)]

#ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(V + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
ans = 0
for i in range(V + 1):
    if dp[n][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF=float('inf')
n ,W= map(int, input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i] = map(int, input().split())
V=sum(v)
dp = [[INF for i in range(V+1)] for j in range(n+1)]

#ここからメイン
dp[0][0]=0
for i in range(n):
    for j in range(V+1):
        if j<v[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
ans=0
for i in range(V+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

Submission status: Accepted

Solution code:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF=2*10**9
n,W = map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i] = map(int, input().split())
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]

#ここからメイン
dp[0][0]=0
for i in range(n):
    for j in range(n*max_v+1):
        if j<v[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
ans=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = float("inf")

def main():
    N, W = map(int, input().split())
    weight = [0]*N
    value = [0]*N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())
    
    V = 100010
    dp = [[INF]*V for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(V):
            if j - value[i] >= 0:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    ans = 0
    for j in range(V):
        if dp[N][j] <= W:
            ans = j
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N,W=map(int,input().split())

l=[10**10]*(10**5+1)
l[0]=0
dp=l[:]

#indexが価値　itemが重さ
for i in range(N):
    w,v=map(int,input().split())
    for index,item in enumerate(l):
        if item!=10**10 and item+w<=W:
            dp[index+v]=min(l[index+v],item+w)
    l=dp[:]

ans=0
for index, item in enumerate(l):
    if item!=10**10:
        ans=index
    else:
        continue
print(ans)

Submission status: Accepted

Solution code:
#dpテーブルのみでの解法(順方向)
n,w=map(int,input().split())
a=[]
dp=[]
res=0
for c in range(n):
   a.append(list(map(int,input().split())))
for v in range(n):
    tmp=a[v][0]
    a[v][0]=a[v][1]
    a[v][1]=tmp
b=max(a)[0]
for k in range(n+1):
  dp.append([])
  for l in range(n*b+1):
      if l==0 and k==0:
          dp[k].append(0)
      else:
          dp[k].append(10000000000)
for i in range(n):
   for j in range(b*n+1):
       if j>=a[i][0]:
           dp[i+1][j]=min(dp[i+1][j],dp[i][j-a[i][0]]+a[i][1],dp[i][j])
       else:
           dp[i+1][j]=min(dp[i+1][j],dp[i][j])
for s in range(n*b+1):
    if dp[n][s]<=w:
        res=s
print(res)

Submission status: Accepted

Solution code:
MAX_V = 100000
INF = 10 ** 10

n,w = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(n)]
dp = [[INF] * (MAX_V + 5) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	for j in range(MAX_V + 1):
		if j + wv[i][1] <= MAX_V:
			dp[i + 1][j + wv[i][1]] = min(dp[i + 1][j + wv[i][1]],dp[i][j] + wv[i][0])
		dp[i + 1][j] = min(dp[i + 1][j],dp[i][j])
ma = 0
for i in range(MAX_V + 1):
	if dp[n][i] <= w:
		ma = max(ma,i)
print(ma)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W  = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
MAX_VAL = 100100
MAX_WEIGHT = 10**10

dp = [[MAX_WEIGHT for _ in range(MAX_VAL+1)] for _ in range(N+1)]

dp[0][0] = 0
for i in range(N):
    value = wv[i][1]
    for v in range(MAX_VAL+1):
        dp[i+1][v] = dp[i][v]
        if v >= value:
            dp[i+1][v] = min(dp[i+1][v], dp[i][v-value]+wv[i][0])
max_v = 0
for i in range(MAX_VAL+1):
    if dp[N][i] <= W:
        max_v = i
print(max_v)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
import numpy as np
lst=np.array([list(map(int,input().split())) for _ in range(N)])
max_value=np.sum(lst[:,1])
#価値iを実現するのに必要な最低の重量のリストを作成
a=np.array([W+1]*(max_value+1))
#最後の<=Wに、実現不可能なものは引っかかってほしくないのでW+1とする
a[0]=0
for w,v in lst:
    #実際に代入していってしまえば実現可能性は考慮される
    a[v:]=np.minimum(a[:-v]+w,a[v:])
print(np.max(np.where(a<=W)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=map(int,input().split())
    w,v=[0]*n,[0]*n
    for i in range(n):
        w[i],v[i]=map(int,input().split())
    V=sum(v)
    dp=[INF]*(V+1)
    dp[0]=0
    for i in range(n):
        newdp=dp[:]
        for x in range(V+1):
            if(x+v[i]<V+1):
                newdp[x+v[i]]=min(newdp[x+v[i]],dp[x]+w[i])
        dp=newdp
    for i in range(V,-1,-1):
        if(dp[i]<=W):
            print(i)
            return
resolve()

Submission status: Accepted

Solution code:
n,W = map(int,input().split())
dp = [[10**12] * (10**5+1) for i in range(n+1)]
dp[0][0] = 0
ma = 0
for i in range(1,n+1):
  w,v = map(int,input().split())
  ma += v
  for j in range(v):
    dp[i][j] = dp[i-1][j]
  for j in range(v,ma+1):
    dp[i][j] = min(dp[i-1][j-v]+w,dp[i-1][j])
m = 0
for i in range(ma+1):
  if dp[-1][i] <= W:
    m = i
print(m)

Submission status: Accepted

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

INF = 10**9+1
M = 10**5+1
dp = [INF]*M #dp[i]:価値の総和がiになるときの重さの総和の最小値
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(M-1, v-1, -1):
        dp[i] = min(dp[i], dp[i-v]+w)
        
for i in range(M-1, -1, -1):
    if dp[i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [{ 0: 0 }]
for i in range(N):
  w, v = map(int, input().split())
  d = dp[i]
  d2 = {}
  for v0 in d:
    w0 = d[v0]
    d2[v0] = w0
  for v0 in d:
    w0 = d[v0]
    if v0+v not in d:
      d2[v0+v] = w0+w
    else:
      d2[v0+v] = min(d2[v0+v], w0+w)
  dp.append(d2)
r = max([v for v in dp[N] if dp[N][v] <= W])
print(r)

Submission status: Accepted

Solution code:
import numpy as np

MAX_VALUE = 100100
INF_WEIGHT = 1 << 30


def main(n, w, items):
    dp = np.full(
        shape=(n + 1, MAX_VALUE),
        fill_value=INF_WEIGHT,
        dtype=int,
    )
    dp[0][0] = 0
    for i in range(0, n):
        weight, value = items[i]
        dp[i + 1][:value] = np.minimum(dp[i][:value], dp[i + 1][:value])
        dp[i + 1][value:] = np.minimum(dp[i][value:], dp[i][:MAX_VALUE - value] + weight)

    return np.max(np.where(dp[-1] <= w))


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))

Submission status: Accepted

Solution code:
import numpy as np


def main(n, w, items):
    MAX_VALUE = 100100
    dp = np.ones((n + 1, MAX_VALUE), dtype=int)
    dp = dp * (1 << 30)
    dp[0][0] = 0
    for i in range(0, n):
        weight, value = items[i]
        dp[i + 1][:value] = np.minimum(dp[i][:value], dp[i + 1][:value])
        dp[i + 1][value:] = np.minimum(dp[i][value:], dp[i][:MAX_VALUE - value] + weight)

    result = 0
    for v in range(MAX_VALUE):
        if dp[-1][v] <= w:
            result = v
    return result


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))

Submission status: Accepted

Solution code:


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

INF = float("inf")
"""
Wの最大が大きすぎるのでふつうのDPはできない
総重量W以下で、価値Vを得るときの最小重さをDPで求める感じ
"""

dp = [{} for _ in range(N+1)]
#何も選ばないときの価値が０で重さが０で初期化。忘れない
dp[0][0] = 0

for i,(w,v) in enumerate(wv):
    for v_sum,w_sum in dp[i].items():

        # i番目の品について考えるとき、i-1までに同じ価値の品があるなら軽いほうを選択、ないならi番目を選択
        if v_sum in dp[i+1]:
            dp[i+1][v_sum] = min(dp[i+1][v_sum], w_sum)
        else:
            dp[i+1][v_sum] = w_sum

        # i-1番目までで起こりえる組み合わせとi番目を選んだ場合に制限を超えるなら飛ばす
        if w + w_sum > W: continue

        # i-1番目までで起こりえる組み合わせとi番目を選んだ場合に、その価値の組み合わせがすでにあるなら軽いほうを、ないならその組み合わせの重さを保存
        if v + v_sum in dp[i+1]:
            dp[i+1][v+v_sum] = min(dp[i+1][v+v_sum], w + w_sum)
        else:
            dp[i+1][v+v_sum] = w + w_sum

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

Submission status: Accepted

Solution code:
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
 
V = 10**3+1
baggage = [0]*N
 
for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)
 
dp = [[10**9+1]*(N*V+1) for _ in range(N+1)]
dp[0][0] = 0  # 最初の要素が0でないと更新が開始しない
 
for i in range(N):
    for v in range(N*V+1):
        if v - baggage[i][1] >= 0:
            dp[i+1][v] = min(dp[i+1][v], baggage[i][0]+dp[i][v-baggage[i][1]])
 
        dp[i+1][v] = min(dp[i][v], dp[i+1][v])
ans = 0
for K in range(N*V+1):
    if dp[N][K] <= W:
        ans = max(ans, K)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]

V = 10**3+1
baggage = [0]*N

for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)

dp = [[10**9+1]*(N*V+1) for _ in range(N+1)]
dp[0][0] = 0  # 最初の要素が0でないと更新が開始しない

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

        else:
            dp[i+1][v] = min(dp[i][v], dp[i+1][v])
ans = 0
for K in range(N*V+1):
    if dp[N][K] <= W:
        ans = max(ans, K)
print(ans)

Submission status: Accepted

Solution code:
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
    left = v if v < 100001 else 100001
    right = left + ans + 1 if left + ans + 1 < 100001 else 100001
    for i in range(left, right)[::-1]:
        if bag[i-v] + w < bag[i] and bag[i-v] + w < W+1:
            bag[i] = bag[i-v] + w
            if i > ans:
                ans = i
print(ans)

Submission status: Accepted

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

vmax = N*(10**3)
# dp[i][j]:i番目までの品物で、価値がjとなる最小の重さ。
dp = [[W+1 for _ in range(vmax+1)] for _ in range(N+1)]
for i in range(N+1):
  dp[i][0] = 0
for i in range(1,N+1):
  for j in range(vmax+1):
    if j >= WV[i-1][1]:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-WV[i-1][1]] + WV[i-1][0])
    else:
      dp[i][j] = dp[i-1][j]
#print(dp)
ans = 0
for i in range(vmax+1):
  if dp[N][i] <= W:
    ans = i
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
v_max = 100010
INF = 1000000100
n, w = map(int, input().split())
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    weight[i], value[i] = map(int, input().split())

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max+1):
    if dp[n][j] <= w:
        result = j
print(result)

Submission status: Accepted

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

INF = 1e9+7
MAX_v = 100100
n,w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[INF]*MAX_v for _ in range(n+1)]
dp[0][0]= 0
for i in range(1, n+1):
    for sum_v in range(MAX_v):
        dp[i][sum_v] = dp[i-1][sum_v]
        if sum_v-wv[i-1][1]>=0:
            dp[i][sum_v]=min(dp[i][sum_v], dp[i-1][sum_v-wv[i-1][1]]+wv[i-1][0])

ans = 0
for i in range(MAX_v):
    if dp[n][i]<=w:
        ans = i
print(ans)

Submission status: Accepted

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

dp = [[float('inf')]*(10**5+1) for i in range(n+1)]
dp[0][0] = 0

for i in range(1,n+1):
    for j in range(10**5+1):
        if j >= item[i-1][1]:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-item[i-1][1]]+item[i-1][0])
        else:
            dp[i][j] = dp[i-1][j]
for j in range(10**5+1):
    if dp[n][j] <= w:
        ans = j

print(ans)