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:
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, W = [int(x) for x in stdin.readline().rstrip().split()]
wv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

max_weight = W+1
max_cost = sum([v for w, v in wv])

# cost時の最小の重さ
# dp[cost] = weight
# 計算量は最大でもN=100*vi=10^3の10^5
dp = [INF for _ in range(max_cost+10)]
dp[0] = 0

for w, v in wv:
    # 前からやると重複を許してしまうことになるので後ろから
    # max_cost~v
    for i in reversed(range(v, max_cost+1)):
        dp[i] = min(dp[i], dp[i-v]+w)

# max_cost~0
for i in reversed(range(max_cost+1)):
    if dp[i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
dp=[0]*(n*10**3+1)
c,p=map(int,input().split())
dp[p]=c
mpos=p
for _ in range(n-1):
  c,p=map(int,input().split())
  for i in range(mpos+p,0,-1):
    if dp[i-p]!=0:
      if dp[i]==0:
        dp[i]=dp[i-p]+c
      else:
        dp[i]=min(dp[i-p]+c,dp[i])
  if dp[p]==0:
    dp[p]=c
  else:
    dp[p]=min(dp[p],c)
  mpos=mpos+p
ans=0
for i in range(len(dp)):
  if dp[i]<=w and dp[i]!=0:
    ans=i
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
INF = 10 ** 12

N, W = map(int, input().split(" "))
wv = np.array([[int(i) for i in input().split(" ")] for _ in range(N)])

sumv = np.sum(wv[:,1])

dp = np.zeros((N + 1, sumv + 1), dtype=np.int64)
dp[0][1:] = INF

for i in range(N):
    dp[i+1][:wv[i][1]] = dp[i][:wv[i][1]]
    dp[i+1][wv[i][1]:] = np.minimum(dp[i][wv[i][1]:], dp[i][:-wv[i][1]]+wv[i][0])

ans = 0
for v, w in enumerate(dp[N]):
    if w <= W:
        ans = max(v, ans)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
INF = 10 ** 12

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

w = np.array(w, dtype=np.int64)
v = np.array(v, dtype=np.int64)
sumv = np.sum(v)

# 価値vの時の重さの最小値
dp = np.zeros((N + 1, sumv + 1), dtype=np.int64)
dp[0][1:] = INF

for i in range(N):
    dp[i+1][:v[i]] = dp[i][:v[i]]
    dp[i+1][v[i]:] = np.minimum(dp[i][v[i]:], dp[i][:-v[i]] + w[i])

ans = 0
for v, w in enumerate(dp[N]):
    if w <= W:
        ans = max(v, ans)

print(ans)

Submission status: Accepted

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

dp = [[float("inf")] * (N * 10 ** 3 + 1) for _ in range(2)]
dp[0][0], dp[1][0] = 0, 0
for i in range(N):
    index = i % 2
    w, v = map(int, input().split())
    for j in range(1, len(dp[0])):
        if j <= v:
            dp[index][j] = min(w, dp[index-1][j])
        else:
            dp[index][j] = min(w + dp[index-1][j-v], dp[index-1][j])

ans = 0
for i, w in enumerate(dp[N % 2 - 1]):
    if w <= W:
        ans = max(ans, i)
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_e

E - Knapsack 2

value scatters less than weight does
"""
MAX_VALUE_SUM = 100000
DEFAULT_WEIGHT = 100000000007

def solve(wv_pairs):
    dp = [DEFAULT_WEIGHT] * (MAX_VALUE_SUM + 1)
    dp[0] = 0
    for i in range(N):
        w_i, v_i = wv_pairs[i]
        for vv in reversed(range(v_i, MAX_VALUE_SUM + 1)):
            dp[vv] = min(dp[vv], dp[vv - v_i] + w_i)
    return next(vv for vv in reversed(range(MAX_VALUE_SUM + 1)) if dp[vv] <= W)


N, W = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
dp = [float('inf')]*(10**5+5)
dp[0] = 0 
for _ in range(N):
    w,v=map(int,input().split())
    for i in range(10**5+4,v-1,-1):
        dp[i]=min(dp[i],dp[i-v]+w)
ans=0
for v,w in enumerate(dp):
    if w <= W:
        ans = v
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int, input().split())
INF =  10**10
V_max = 100001
N_max = 101
# dp = np.ones((N_max,V_max), dtype=np.int64)*INF
dp = np.ones(V_max,dtype=np.int64)*INF
dp[0] = 0
for i in range(N):
    a = np.ones(V_max)*INF
    w,v = map(int,input().split())
    # np.minimum(dp[i][:-v]+w,dp[i][v:],out=dp[i+1][v:])
    np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])
ans = 0
for i,d in enumerate(dp):
    if d<=W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
wv = []
sumv = 10
for i in range(N):
    wv.append(list(map(int,input().split())))
    sumv += wv[i][1]

dp = [[ 10**100 for i in range(sumv+1)] for j in range(N+1)]

dp[0][0] = 0

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

ans = 0
for i in range(sumv):
    if dp[N][i] <= W:
        ans = max(ans , i)
print(ans)

Submission status: Accepted

Solution code:
MAX_INT = int(10e10)

N,W = list(map(int,input().split()))
w = [0]
v = [0]

for i in range(N):
  a,b = list(map(int,input().split()))
  w.append(a)
  v.append(b)
V_MAX = max(v)

# dp[i][v] = w
dp = [[MAX_INT]*(N*V_MAX+1) for i in range(N+1)]

for i in range(N+1):
  dp[i][v[i]] = w[i]
for i in range(1,N+1):
  for j in range(1,N*V_MAX+1):
    if j < v[i]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]]+w[i],dp[i][j])  # max(iの品を使わない時, iの品を使う時)
for j in range(N*V_MAX,0,-1):
  for i in range(1,N+1):
    if dp[i][j] <= W:
      print(j)
      exit()

Submission status: Accepted

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

max_weight = W + 1
max_cost = sum([v for w,v in WV])
dp = [max_weight for _ in range(max_cost + 1)]
# dp[cost] weight
dp[0] = 0

for w,v in WV:
    for index in reversed(range(len(dp))):
        if dp[index] == max_weight:
            continue

        dp[index + v] = min(dp[index + v], dp[index] + w)


for cost in reversed(range(max_cost + 1)):
    if dp[cost]<=W:
        print(cost)
        break

Submission status: Accepted

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

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
weight = []
value = []
INF = 10 ** 9
#dp[x][y] = x-1番目までの品物から価値がyを達成するように
#           選んだときの重さの最小値
ans = 0

for i in range(n):
    x, y = map(int, input().split())
    weight.append(x)
    value.append(y)

dp = [[ INF for i in range(sum(value) + 1)] for j in range(n + 1)]
dp[0][0] = 0

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

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


for i in sorted(range(sum(value) + 1), reverse = True):
        tmp = dp[n][i]
        if tmp <= w:
            print(i)
            exit()

Submission status: Accepted

Solution code:
import numpy as np

n, ww = map(int, input().split())

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

dp = np.full(n*10**3+1, np.inf)
dp[0] = 0

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

for i in range(n*10**3+1)[::-1]:
    if dp[i] <= ww:
        print(i)
        exit()

Submission status: Accepted

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

wv = [list(map(int, input().split())) for i in range(n)]
wv.sort(key=lambda x:x[1])
dp = {0:0}
for w, v in wv:
    dp_next = dp.copy()
    for key in dp:
        dp_next[key+v] = min(dp[key]+ w, dp.get(key+v, float("inf")))
    dp = dp_next
for key in sorted(dp.keys(), reverse=True):
    if dp[key] <= ww:
        print(key)
        exit()

Submission status: Accepted

Solution code:
import sys

n, w = map(int, sys.stdin.readline().split())
weight = []
value = []
sum_value = 0
for i in range(n):
    wi, vi = map(int, sys.stdin.readline().split())
    weight.append(wi)
    value.append(vi)
    sum_value += vi

#val = [0] * (sum_value + 1)
wght = [1<<64] * (sum_value + 1)
wght[0] = 0
for i in range(n):
    for j in range(sum_value - value[i], -1, -1):
        wght[j + value[i]] = min(wght[j + value[i]], wght[j] + weight[i])
            #val[j + value[i]] = max(val[j + value[i]], val[j] + value[i])
            #wght[j + value[i]] = wght[j] + weight[i]


max_val = 0

for i in range(sum_value, -1, -1):
    if wght[i] <= w:
        #max_val = max(max_val, val[i])
        max_val = max(max_val, i)

print(max_val)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import numpy as np

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

    dp = np.full((N+1, N * (10**3) +1), np.inf)
    dp[0][0] = 0

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

        dp[i+1][:value] = dp[i][:value]
        dp[i+1][value:] = np.minimum(dp[i][value:], dp[i][:-value] + weight)


    res = 0
    for i, weight in enumerate(dp[N]):
        if weight <= W: res = i

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# sum_vの取りうる上限値
MAX_V = (10**3) * N +1

def knapsack(n, w):
    # dp[i][j] : i番目の品物で価値jの重さの最小値
    dp = np.full([N+1, MAX_V], np.inf)
    dp[0][0] = 0
    for i in range(n):
        w, v = map(int, input().split())
        dp[i+1] = dp[i]
        dp[i+1][v:] = np.minimum(dp[i][v:], dp[i][:-v] + w)
    print(np.max(np.where(dp <= W)))

knapsack(N, W)

Submission status: Accepted

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# sum_vの取りうる上限値
MAX_V = (10**3) * N +1
# 最小値を求めるので無限大の値
f_inf = float('inf')

def knapsack(n, w):
    # dpの初期化　dp[sum_v]は重さの総和の最小値
    dp = [f_inf] * MAX_V
    # 初期条件
    dp[0] = 0
    sum_v = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(MAX_V, v-1, -1):
            new_weight = dp[j - v] + w
            if new_weight > W:
                continue
            if dp[j] > new_weight:
                dp[j] = new_weight

    ans = 0
    for sum_v in range(MAX_V):
        if dp[sum_v] <= W:
            ans = sum_v
    print(ans)

knapsack(N, W)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w,v = [],[]
dp = [[10**10]*100100 for _ in range(101)]
dp[0][0] = 0
for i in range(N):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
for i in range(N):
    for sum_v in range(100100):
        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])
ans = 0
for i in range(100100):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
def solve():
  N, W = map(int, input().split())
  INF = 1e9 + 5
  dp = [INF]  * (100001)
  dp[0] = 0
  items = []
  for i in range(N):
    w, v = map(int, input().split())
    items.append((w, v))

  sum_v = 0
  for w, v in items:
    sum_v += v
    temp_dp = list(dp) 
    for i in range(v, sum_v + 1):
      if temp_dp[i - v] != INF:
        dp[i] = min(temp_dp[i], temp_dp[i - v] + w)

  for i in range(100000, -1, -1):
    if dp[i] != INF and dp[i] <= W:
      print(i)
      break
      

if __name__ == "__main__":
  solve()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def nap(n, cap):
    mxk = 0
    inf = 10 ** 10
    wei = [0] + [inf] * 100000
    for _ in range(n):
        w, v = map(int, input().split())
        for vk in range(100000, v - 1, -1):
            nw = wei[vk - v] + w
            if nw > cap: continue
            if wei[vk] > nw:
                wei[vk] = nw
                if vk > mxk:
                    mxk = vk
    return mxk


n, cap = map(int, input().split())
print(nap(n, cap))

Submission status: Accepted

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

    for i in range(N):
        wi = weight[i]
        vi = value[i]
        for v in range(V, -1, -1):
            w = dp[v] + wi
            if dp[v + vi] <= w: continue
            dp[v + vi] = w
        V += vi

    for i in range(V, -1, -1):
      if dp[i] <= W: return i
    return 0

print(solve())

Submission status: Accepted

Solution code:
def main():
    N, W = [int(n) for n in input().split()]
    
    baggages = [[int(n) for n in input().split()] for i in range(N)]# 荷物1, 荷物2, ...と数え、荷物0は数合わせの(0, 0)
    baggages.insert(0, [0, 0])

    VALUE, WEIGHT = 1, 0
    VALUE_LIMIT = int(1e5)
    INF = int(1e15)

    
    dp = [[-1] * (VALUE_LIMIT+1) for n in range(N+1)]# 荷物は0~N, 価値は0~VALUE_LIMIT
    # dp[baggage][value] := baggage番目までの荷物を使ってvalueだけとる最小重量
    dp[0] = [INF] * (VALUE_LIMIT+1)
    dp[0][0] = 0
    
    for baggage in range(1, N+1):
        for value in range(VALUE_LIMIT+1):
            if dp[baggage][value] != -1:
                continue
            bag_w = baggages[baggage][WEIGHT]
            bag_v = baggages[baggage][VALUE]
            val1 = dp[baggage-1][value]
            val2 = (dp[baggage-1][value-bag_v] + bag_w) if value >= bag_v else INF
            dp[baggage][value] = min(val1, val2)
    
    max_val = 0
    for index, w in enumerate(dp[N]):
        if w <= W:
            max_val = index
    print(max_val)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys

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

dp = [float('inf')] * (sum(v)+1)
dp[0] = 0

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

Submission status: Accepted

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

dp = [{} for i in range(N+1)]
dp[0][0] = 0
for i,(w,v) in enumerate(wv):
    for v0,w0 in dp[i].items():
        if v0 in dp[i+1]:
            dp[i+1][v0] = min(dp[i+1][v0], w0)
        else:
            dp[i+1][v0] = w0
        if w0+w > W: continue
        if v0+v in dp[i+1]:
            dp[i+1][v0+v] = min(dp[i+1][v0+v], w0+w)
        else:
            dp[i+1][v0+v] = w0+w
print(max(dp[-1].keys()))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,w = li()
INF = float('inf')

dp = [[INF]*(n*1000+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
    
for i in range(1,n+1):
    wi, vi = li()
    for j in range(1, n*1000+1):
        if j-vi >= 0:
            dp[i][j] = min(dp[i][j],
                           dp[i-1][j],
                           dp[i-1][j-vi] + wi)
        else:
            dp[i][j] = min(dp[i][j],
                           dp[i-1][j])
        
ans = 0
for i in range(n*1000+1):
    if dp[n][i] <= w:
        ans = i
        
print(ans)

Submission status: Accepted

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

M = sum(v)

dp = [[W+1 for _ in range(M + 1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    dp[i+1][v[i]] = min(dp[i][v[i]], w[i])
    for j in range(v[i]):
        dp[i+1][j] = dp[i][j]
    for j in range(v[i], M + 1):
        dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i])
for i in range(M, -1, -1):
    if dp[N][i] <= W:
        print(i)
        exit()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,W=map(int,input().split())
max_v=10**5
DP=[0]+[float('inf')]*max_v #DP[i]: 価値iを達成するための最小重量
for _ in range(N):
    w,v=map(int,input().split())
    for i in range(max_v,v-1,-1):
        DP[i]=min(DP[i],DP[i-v]+w)
ans=0
for v,w in enumerate(DP):
    if w<=W:
        ans=v
print(ans)

Submission status: Accepted

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

max_total = 0
p = []
for it in range(N):
    p.append(list(map(int,input().split())))
    max_total += p[-1][1]
    
    
MAX_WEIGHT = 1000000009
dp = [[MAX_WEIGHT for i in range(max_total+1)] for j in range(N+1)]
dp[0][0]=0
i = 0
for w, v in p:
    i += 1
    for target_val in range(0, max_total+1):
        
        if target_val-v >=0 and dp[i-1][target_val] > (dp[i-1][target_val-v]+w):
            dp[i][target_val] = dp[i-1][target_val-v]+w
        else:
            dp[i][target_val] = dp[i-1][target_val]
            
ret = 0
for v, w in enumerate(dp[N]):
    if w<=W and v>ret:
        ret = v
print(ret)

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
weighs,values = [],[]
for i in range(n):
    wa,va = map(int,input().split())
    weighs.append(wa)
    values.append(va)

dp = [0 for k in range(100001)]
used = [[0 for i in range(n)] for k in range(100001)]

for i in range(1,100001):
    mina = 1000000000000
    useda = [0 for i in range(n)]
    for k in range(n):
        if i-values[k] >= 0:
            if dp[i-values[k]] != -1 and used[i-values[k]][k] == 0 :
                #print(i,k)
                if  dp[i-values[k]]+weighs[k]<mina:
                        #print("いい感じ")
                        mina = dp[i-values[k]]+weighs[k]
                        useda = used[i-values[k]][:]
                        useda[k] = 1
                #print(mina,useda)
    if mina == 1000000000000:
        dp[i] = -1
    else:
        dp[i] = mina
    used[i] = useda

ans = 0
for i in range(100001):
    if dp[i] != -1 and dp[i] <= w:
        #print(i)
        ans = max(ans,i)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(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)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("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)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return

#E
def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I():
    return 
#J

#K

#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
l=(n*1000)+1
dp=[9999999999]*(l)
dp[0]=0
for i in range(n):
	wt,val=map(int,input().split())
	for j in range(l-1,val-1,-1):
		dp[j]=min(dp[j],dp[j-val]+wt)
for i in range(l-1,-1,-1):
	if dp[i]<=w:
		print(i)
		exit()

Submission status: Accepted

Solution code:
n,w=map(int,input().split())
dp=[999999999999999]*(100001)
dp[0]=0
for i in range(n):
	wt,val=map(int,input().split())
	for j in range(100000,val-1,-1):
		dp[j]=min(dp[j],dp[j-val]+wt)
for i in range(100000,-1,-1):
	if dp[i]<=w:
		print(i)
		exit()

Submission status: Accepted

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

weight = []
value = []

for i in range(n):
    a, b = map(int, input().split())
    weight.append(a)
    value.append(b)

max_v = sum(value)

#dp[i][j] := i番目までの品物から価値がj以上を達成するように選んだときの重さの和の最小値
inf = float("inf")
dp = [[inf]*(max_v+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(max_v+1):
        if j - value[i] >= 0:
            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(max_v+1):
    if dp[n][j] > w:
            continue
    else:
        ans = max(ans, j)
print(ans)

Submission status: Accepted

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

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [W+1] * (N * 1000 + 1)
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))

Submission status: Accepted

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

N, W = [int(i) for i in input().split()]

def ans(N, W):
    d = [float("inf")] * (N * 1000 + 1)
    d[0] = 0
    V = 0

    for i in range(N):
        wi, vi = [int(i) for i in input().split()]
        V = V + vi

        for v in range(V, vi-1, -1):
            w_ = d[v - vi] + wi
            if w_ < d[v]:
                d[v] = w_

    for v in range(V, -1, -1):
        if d[v] <= W:
            return v

print(ans(N, W))

Submission status: Accepted

Solution code:
n,w = map(int,input().split())
info = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
v = 0
for i in range(n+1):
  v += info[i][1]

## dp[i][j]:i番目までのアイテムを詰めたときに総価値jになるときの最小重さ
dp = [[float("inf")]*(v+1) for i 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(1,v+1):
    if j-info[i][1]>=0:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-info[i][1]]+info[i][0])
    else:
      dp[i][j] = dp[i-1][j]

for j in range(v+1):
  if dp[n][j] <= w:
    ans = j
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Tasks: EDPC(Educational DP Contest) E - Knapsack 2
import sys
input = sys.stdin.readline

def f(n, W):
    dp = [float('inf')] * (100010)
    dp[0] = 0
    maxv = 0
    for i in range(n):
        wi, vi = map(int, input().split())
        maxv += vi
        for v in range(maxv, -1, -1):
            w_ = wi if v - vi < 0 else dp[v - vi] + wi
            if dp[v] > w_ and w_ <= W:
                dp[v] = w_
    return(dp.index(float('inf')) - 1)

n, w = map(int, input().split()) # 1 <= n <= 100, 1 <= w <= 10^9
print(f(n, w))

Submission status: Accepted

Solution code:
def e_knapsack2(N, W, Goods):
    """
    Dと同じ設定だが、制約が違う(1 <= v_i <= 10^3 と価値の制約がゆるめ)
    """
    import numpy as np
    # dp[v]: 価値vを達成するのに必要な重量の最小値
    # dpの長さは、すべての荷物を入れたときの価値+1で十分
    # 各要素の初期値は、Wを超える値ならよい(np.infだとうまく動作しないが)
    max_value = np.sum(np.array(Goods), axis=0)[1]
    dp = np.full(max_value + 1, W + 1, dtype='int64')
    dp[0] = 0  # 価値0を達成する荷物の重量は0とする
    for w, v in Goods:
        # 価値i(0<=i<=max_value-v)のときの重さの最小値に対し
        # 注目している荷物を入れて、価値i+vのときの重さの最小値を更新
        np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
    return np.max(np.where(dp <= W))

N, W = [int(i) for i in input().split()]
Goods = [[int(i) for i in input().split()] for j in range(N)]
print(e_knapsack2(N, W, Goods))

Submission status: Accepted

Solution code:
from sys import stdin
n,W=map(int,input().split())
INF=1<<60
sum_v=0
vector=[]
for i in range(n):
    w,v=map(int,stdin.readline().split())
    sum_v+=v
    vector.append((w,v))

dp=[INF for i in range(sum_v+1)]
dp[0]=0

for w,v in vector:
    for j in range(sum_v-v,-1,-1):
        dp[v+j]=min(dp[v+j],dp[j]+w)

index=0
for i in range(len(dp)):
    if dp[i]<=W:
        index=max(index,i)
print(index)

Submission status: Accepted

Solution code:
N, W = list(map(int,raw_input().split()))
dp = [float("inf") for i in range(100001)]
dp[0] = 0
for i in xrange(N):
  wi, vi = list(map(int,raw_input().split()))
  for v in xrange(100000-vi, -1, -1):
    dp[v+vi] = min(dp[v+vi],dp[v]+wi)
print(max([v for v in xrange(100001) if dp[v]<=W]))