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:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, W = MAP()
wN, vN = [0]*N, [0]*N
for i in range(N):
    wN[i], vN[i] = MAP()

# dp[何個目までから選ぶか][選んだ荷物の価値] = その価値を達成するために最低限必要な重さ
V = max(vN)*N
dp = [[INF] * (V+1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(V+1):
        # 真下には常に送る
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j + vN[i] <= V:
            # 添字が範囲内なら右下にも送る
            dp[i+1][j+vN[i]] = min(dp[i+1][j+vN[i]], dp[i][j] + wN[i])
ans = 0
for i in range(V+1):
    if dp[N][i] <= W:
        ans = max(ans, i)
print(ans)

Submission status: Accepted

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

V = {}
V[0] = 0
for i in range(N):
  w, v = map(int, input().strip().split())
  keys = sorted(list(V.keys()), reverse=True)
  for vk in keys:
    if (vk + v) in V:
      V[vk + v] = min(V[vk + v], V[vk] + w)
    else:
      V[vk + v] = V[vk] + w

v_max = 0
for vk in V.keys():
  if ((V[vk] <= W) and (vk > v_max)):
    v_max = vk

print(v_max)

Submission status: Accepted

Solution code:
INF = float('inf')

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

sumV = 10**5
dp = [INF] * (sumV+1)
dp[0] = 0
for wi, vi in items:
    for v in reversed(range(sumV+1)):
        if dp[v] == INF: continue
        dp[v+vi] = min(dp[v+vi], dp[v] + wi)

print(max([v for v in range(sumV+1) if dp[v] <= capW]))

Submission status: Accepted

Solution code:
from sys import stdin, stdout

INF = float('inf')
n, C = map(int, stdin.readline().split())
W = 10 ** 5

dp = [[INF for i in range(W + 1)] for j in range(2)]
dp[0][0] = 0
cur = 0

for i in range(n):
    w, c = map(int, stdin.readline().split())
    w, c = c, w
    
    for j in range(W + 1):
        dp[cur ^ 1][j] = min(dp[cur ^ 1][j], dp[cur][j])
        
        if j + w <= W:
            dp[cur ^ 1][j + w] = min(dp[cur ^ 1][j + w], dp[cur][j] + c)
        
        dp[cur][j] = INF
    
    cur ^= 1

ans = 0
for i in range(W + 1):
    if dp[cur][i] <= C:
        ans = i
        
stdout.write(str(ans))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv in dp:
                if nw < dp[nv]:
                    dp[nv] = nw
            else:
                dp[nv] = nw


print(max(dp.keys()))

Submission status: Accepted

Solution code:
import numpy as np
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n,wmax=IL()
dp=np.full(n*pow(10,3)+1,wmax+1,dtype=int)
dp[0]=0
for i in range(n):
    w,v=IL()
    dp[v:]=np.minimum(dp[v:],dp[:-v]+w)
for i in range(n*pow(10,3)+1):
    if dp[i]<=wmax:
        ans=i
print(ans)

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
w = []
v = []
for i in range(n):
    vals = list(map(int, input().split()))
    w.append(vals[0])
    v.append(vals[1])
sum_v = sum(v)
inf = 10**10
dp = [inf] * (sum_v + 1)
dp[0] = 0
for i in range(n):
    for j in reversed(range(sum_v - v[i] + 1)):
        if dp[j] == inf:
            continue
        dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i])
for i in reversed(range(sum_v + 1)):
    if dp[i] > W:
        continue
    print(i)
    break

Submission status: Accepted

Solution code:
import numpy as np
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])
INF = 10**13

def maxvalue_dp(ws, vs, W):
    V = sum(vs)
    dp = np.zeros(V + 1, np.int64)
    dp += INF
    dp[0] = 0
    for w, v in zip(ws, vs):
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
    for v in range(V, -1, -1):
        if dp[v] <= W:
            return v

print(maxvalue_dp(ws, vs, W))

Submission status: Accepted

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

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

V = sum(v for w,v in items)

dp = [float('inf')]*(V+1)
dp[0] = 0
for w,v in items:
  for j in reversed(range(V-v+1)):
    dp[j+v] = min(dp[j+v], dp[j]+w)

print(max(v for v,w in enumerate(dp) if w <= W))

Submission status: Accepted

Solution code:
INF = 10 ** 12
MV = 10 ** 5

N, W = map(int, input().split())
dp = [[INF for _ in range(MV + 1)] for _ in range(N + 1)]
dp[0][0] = 0
# dp[品物のidx][価値の総和] = 実現する最小重量

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(MV + 1):
        if j - v >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

ans = -1
j = MV
while j >= 0:
    if dp[N][j] <= W:
        ans = j
        break
    j -= 1
print(ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_e
#2019-01-13
import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = np.ones(N*1000+1, dtype=int) *(W+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    DP[v[i]:] = np.minimum(DP[:-v[i]]+ w[i], DP[v[i]:])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        ans = k
        
print(ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_e
#2019-01-13
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]

DP = [float("inf")] * (N*1000+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    for j in range(N*1000,-1,-1):
        DP[j] = min(DP[j- v[i]] + w[i], DP[j])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        
        ans = k
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
c = [tuple(map(int,input().split())) for i in range(N)]
DP = [[float('inf') for i in range(10**3*N+1)] for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    for v in range(10**3*N+1):
        if v-c[i][1] < 0:
            DP[i+1][v] = DP[i][v]
        else:
            DP[i+1][v] = min(DP[i][v-c[i][1]]+c[i][0],DP[i][v])

ans = 0
DP = DP[N]
for v in range(10**3*N,-1,-1):
    if DP[v] <= W:
        ans = v
        break
print(ans)

Submission status: Accepted

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

V=10**5
dp= [ None for i in range(V+1) ]
dp[0]=0


for w,v in A:
	for i in range(V,-1,-1):
		if dp[i] is not None:
			if  0<=i+v<=V:
				if dp[i+v] is None:
					dp[i+v]=dp[i]+w
				else:
					dp[i+v]=min( dp[i+v], dp[i]+w )


for i in range(V,-1,-1):
	if dp[i] is not None:
		if dp[i]<=W:
			print i
			quit()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [10**9+1] * (V + 1)
dp[0] = 0
for i in range(N):
    for j in range(V, -1, -1):
        dp[j] = min(dp[j], dp[j-L[i][1]] + L[i][0])
ans = 0
for j in range(V+1):
    if  W >= dp[j]:
        ans = max(ans, j)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [[10**9+1] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j]:
        ans = max(ans, j)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [[float('inf')] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j]:
        ans = max(ans, j)
print(ans)

Submission status: Accepted

Solution code:
n,w=map(int, input().split())
m=10**5+1
x=[list(map(int, input().split())) for i in range(n)]
dp=[[float('inf')]*m for i in range(n+1)]
dp[0][0]=0
for i in range(n):
    for j in range(m):
        if j>=x[i][1]:
            dp[i+1][j]=min(dp[i][j],dp[i][j-x[i][1]]+x[i][0])
        else:
            dp[i+1][j]=dp[i][j]
ans=0
for i in range(m):
    if dp[-1][i]<=w:ans=max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
value,weight = [],[]
def chmin(a,b):
    if (a > b):
        a = b
        return True
    return False
for i in range(N):
    w,v = map(int,input().split())
    value.append(v)
    weight.append(w)
# dp[i][v]: i番目までの品物から価値vを超えるように選んだ時の重さの最小値
dp = [[float("inf")] * (sum(value)+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    for v in range(sum(value)+1):
        if v - value[i-1] >= 0:
            dp[i][v] = min(dp[i-1][v-value[i-1]] + weight[i-1],dp[i-1][v])
        else:
            dp[i][v] = dp[i-1][v]
ans = 0
for v in range(sum(value),-1,-1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
N, W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))
dp = np.full(N * 1000 + 1, W + 1, dtype=np.int64)
dp[0] = 0
for w, v in zip(it, it):
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
print(((dp <= W) * np.arange(N * 1000 + 1)).max())

Submission status: Accepted

Solution code:
import sys
import numpy as np
N, W = map(int, input().split())
it = iter(map(int, sys.stdin.read().split()))
dp = np.full(N * 1000 + 1, 10 ** 10, dtype=np.int64)
dp[0] = 0
for w, v in zip(it, it):
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
print(((dp <= W) * np.arange(N * 1000 + 1)).max())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,w = LI()
    aa = sorted([LI() for _ in range(n)])
    u = sum(map(lambda x: x[1], aa))
    r = [inf] * (u+1)
    r[0] = 0
    mx = 0
    for a,b in aa:
        mx += b
        for i in range(min(mx, u-b),-1,-1):
            if r[i+b] > a + r[i]:
                r[i+b] = a + r[i]

    for i in range(u,0,-1):
        if r[i] <= w:
            return i

    return 0


print(main())

Submission status: Accepted

Solution code:
t = int(1e5)
n, m = map(int, input().split())
ans = 0
dp = [m + 1 for _ in range(t + 1)]
dp[0] = 0
for _ in range(n):
    w, v = map(int, input().split())
    for i in range(t, v - 1, -1):
        if dp[i - v] + w <= m:
            dp[i] = min(dp[i], dp[i - v] + w)
            ans = max(ans, i)
print(ans)

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,W=I()
g=[0]+[I()for _ in range(n)]
vm=n*1000+1
dp=[[0]+[10**18]*vm]+[[0]*vm for _ in range(n)]
for i in range(1,n+1):
    w,v=g[i]
    for j in range(vm):
        k=j-v
        if k<0:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=min(dp[i-1][j],dp[i-1][k]+w)
for j in range(vm)[::-1]:
    if dp[n][j]<=W:
        print(j)
        break

Submission status: Accepted

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

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

for i in range(N):
    for j in reversed(range(v_sum)):
        if j + v[i] < v_sum and dp[j] != inf:
            dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i])

for i in reversed(range(v_sum)):
    if dp[i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys
raw_input = sys.stdin.readline
N,W = map(int,raw_input().split())
arr = []
tot = 0
for i in range(N):
    arr.append(map(int,raw_input().split()))
    tot += arr[i][1]
dp = [100000000000 for x in range(tot+1)]
dp[0] = 0
for i in range(N):
    a,b = arr[i]
    for j in range(tot,b-1,-1):
        dp[j] = min(dp[j],dp[j-b]+a)
for i in range(tot,-1,-1):
    if dp[i]<=W:
        print i
        break

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N, W = LI()
L = [LI() for _ in range(N)]
V = 0
for i in range(N): V += L[i][1]

# dp[v]: 価値vを詰め込んだナップザックの重量の最小値
dp = [INF] * (V + 1)
dp[0] = 0
for weight, value in L:
    for v in range(V + 1)[::-1]:
        if v - value < 0:
            continue
        dp[v] = min(dp[v], dp[v - value] + weight)

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N, W = LI()
L = [LI() for _ in range(N)]
V = 0
for i in range(N): V += L[i][1]

# dp[v]: 価値vを詰め込んだナップザックの重量の最小値
dp = [INF] * (V + 1)
dp[0] = 0
for weight, value in L:
    for v in range(V + 1)[::-1]:
        if v - value < 0:
            continue
        dp[v] = min(dp[v], dp[v - value] + weight)

for i in range(V + 1)[::-1]:
    if dp[i] != INF and dp[i] <= W:
        print(i)
        exit()

Submission status: Accepted

Solution code:
def main():
    N, W = map(int, input().split())
    VMAX = int(1e5)+1
    dp = [[float("inf")] * (VMAX) for _ in range(2)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(VMAX):
            dp[(i+1) % 2][j] = min(dp[i % 2][j], dp[i % 2][max(j-v, 0)]+w)
    left = 0
    right = VMAX
    while left < right:
        center = (left + right) // 2
        if dp[N % 2][center] <= W:
            left = center + 1
        else:
            right = center
    print(left-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
sum_v = sum([item[1] for item in items])
inf = float("inf")
dp = [inf for _ in range(sum_v+1)]

dp[0] = 0
for i in range(N):
    for j in range(sum_v, -1, -1):
        if j - items[i][1] >= 0:
            dp[j] = min(dp[j], dp[j - items[i][1]] + items[i][0])

for v in range(sum_v, -1, -1):
    if dp[v] <= W:
        print(v)
        exit()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
sum_v = sum([item[1] for item in items])
inf = float("inf")
dp = [[inf for _ in range(sum_v+1)] for _ in range(N+1)]


dp[0][0] = 0
for i in range(N):
    for j in range(sum_v+1):
        if j - items[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j - items[i][1]] + items[i][0])
        else:
            dp[i+1][j] = dp[i][j]
for v in range(sum_v, -1, -1):
    if dp[N][v] <= W:
        print(v)
        exit()

Submission status: Accepted

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

V = max(w_v, key=lambda x: x[1])[1] * N
# 1~i-1番目の品物から価値の総和がj以下になるように選んだときの重さ
dp = [[float('inf') for _ in range(V+1)] for _ in range(N+1)]
dp[0][0] = 0

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.full(N*1000+1, W+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(((dp <= W)*np.arange(N*1000+1)).max())

Submission status: Accepted

Solution code:
def e_knapsack2(N, W, Goods):
    """
    Dと同じ設定だが、制約が違う(1 <= v_i <= 10^3 と価値の制約がゆるめ)
    """
    from collections import defaultdict

    # dp[v]: 価値vを達成するために要求される重さの最小値
    dp = defaultdict(lambda: float('inf'))
    dp[0] = 0
    # w, vの順序が逆になっているのはdpテーブルの都合上
    for w, v in Goods:
        for nv, nw in list(dp.items()):
            if nw + w <= W:
                dp[nv + v] = min(dp[nv + v], nw + w)
    # 遷移の仕方により、keyの値を達成する品物の重さの和がWを超えることは
    # ないので、keyの最大値を解とすればいい
    return max(dp.keys())

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:
N,W=map(int,input().split())

dp=[[0,0] for i in range(100001)]

dp[0][0]=1

w=[]
v=[]

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

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

Submission status: Accepted

Solution code:
N,W=[int(x) for x in raw_input().split()]
A=[]
maxval=0
for i in range(N):
    w,v=[int(x) for x in raw_input().split()]
    A.append([w,v])
    maxval+=v
B=[[ 1e10  for i in range(maxval+1)] for j in range(N)]
B[0][A[0][1]]=A[0][0]
for x in range(N):
    B[x][0]=0

for i in range(1,N):
    w,v=A[i]
    for j in range(1, maxval+1):
        if (j>=v and B[i-1][j-v]+w <=W):
            B[i][j]=min(B[i-1][j-v]+w, B[i-1][j])
        else:
            B[i][j]=B[i-1][j]
for j in range(maxval,-1,-1):
    if B[-1][j]!=1e10:
        print j
        break

Submission status: Accepted

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

items = [list(map(int, input().split())) for _ in range(N)]
v_sum = sum([item[1] for item in items])

inf = float("inf")
dp = [inf for _ in range(v_sum + 1)]

dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        if dp[j] > dp[j - items[i][1]] + items[i][0]:
            dp[j] = dp[j - items[i][1]] + items[i][0]

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        exit()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


MAX_VALUE = 10**5
N, W = ds_in()

# 価値i以上の最小重さ
min_weights = np.ones(MAX_VALUE + 1) * float('inf')
min_weights[0] = 0

total_value = 0
for _ in range(N):
    wv = ds_in()  # [weight, value]
    min_weights[wv[1]:] = np.minimum(min_weights[:-wv[1]] + wv[0],
                                     min_weights[wv[1]:])

for i in range(MAX_VALUE, 0, -1):
    if min_weights[i] <= W:
        print(i)
        exit()

Submission status: Accepted

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

NIL = int(1e18)
MAX = int(1e5)

dp = [NIL]*(MAX+1)
dp[0]= 0

for i in range(1, N+1):
    w, v = wl[i], vl[i]
    for k in reversed(range(MAX+1)):
        if k + v <= MAX and dp[k] != NIL:
            dp[k+v] = min(dp[k+v], dp[k] + w)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def 解():
    input = sys.stdin.readline

    N,W=[int(_) for _ in input().split()]
    dp={0:0}
    for _ in range(N):
        w,v=[int(_) for _ in input().split()]
        #for j in dp.copy():
        for j in sorted(dp.keys(),reverse=True):
            nw = dp[j]+w
            nv = j+v
            if nw <= W :
                if nv in dp:
                    if nw < dp[nv]:
                        dp[nv] = nw
                else:
                    dp[nv] = nw

    print(max(dp.keys()))
解()

Submission status: Accepted

Solution code:
n, W = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
dp = [float("inf") for _ in range(1000*n+1)]
dp[0] = 0
#dp[i][j]: i個目まで選んで価値jにするのに必要な重さ(Wを超えないように記録)
for i in range(n):
	for v in range(1000*n, t[i][1]-1, -1):
		if dp[v - t[i][1]] + t[i][0] <= W:
			dp[v] = min(dp[v], dp[v - t[i][1]] + t[i][0])
		

#print(dp[1][30], dp[2][30])
#print(dp)

ans = 0
for v in range(1000*n+1):
	if dp[v] <= W:
		ans = v

print(ans)

Submission status: Accepted

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

max_V = sum(vlst)
INF = 10 ** 20
dp = [INF] * (max_V + 1)
dp[0] = 0
for w, v in zip(wlst, vlst):
  for i in range(max_V, v - 1, -1):
    dp[i] = min(dp[i], dp[i - v] + w)

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

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
table=[]
for i in range(N):
    w,v=map(int,input().split())
    table.append((w,v))
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    w,v=table[i-1]
    for j in range(N*(10**3)+1):
        if j-v>=0:
            dp[i][j]=min(dp[i-1][j-v]+w,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for j in range(N*(10**3),-1,-1):
    if dp[N][j]<=W:
        print(j)
        break

Submission status: Accepted

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


MAX_INT = (1 << 63) - 1
N, W = [int(elem) for elem in fin().split()]
weight_value_pairs = tuple(tuple(int(elem) for elem in fin().split()) for _ in range(N))
max_value = max(v for _, v in weight_value_pairs)
max_total_value = N * max_value

dp = [MAX_INT] * (max_total_value + 1)
dp[0] = 0
for i in range(N):
    w, v = weight_value_pairs[i]
    for j in reversed(range(max_total_value + 1)):
        dp[j] = min(dp[j], dp[j - v] + w)

max_val = 0
for val, total_weight in enumerate(dp):
    if total_weight <= W:
        max_val = val
print(max_val)

Submission status: Accepted

Solution code:
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())
MAX_NV = 100*1000 # N*v
inf = float('inf')
# dp tabel -> dp list
dp = [inf]*(MAX_NV+1) 
dp[0]  = 0
for i in range(N):
    for j in reversed(range(MAX_NV+1)):
        if j-v[i]<0:
            dp[j] = dp[j]
        else:
            dp[j] = min(dp[j],
                        dp[j-v[i]] + w[i])
    # print(dp[:100])

ans = 0
for value,dpi in enumerate(dp):
    if dpi<=W:
        ans = max(ans, value)
print(ans)

Submission status: Accepted

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

dp = [[0] * (100001) for i in range(N + 1)]
for i in range(1, 100001):
    dp[0][i] = 10 ** 20

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

ans = 0
for i in range(100000, -1, -1):
    if dp[N][i] <= W:
        ans = i
        break

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
def inpl(): return list(map(int, input().split()))

N, L = inpl()
DP = [1e10]*(10**5 + 2)
DP[0] = 0
for i in range(N):
    DP2 = [1e10]*(10**5 + 2)
    w, v = inpl()

    for i in range(10**5, v-1, -1):
        DP2[i] = min(DP[i-v] + w, DP[i], DP2[i+1])
    for i in range(v-1, -1, -1):
        DP2[i] = min(DP[i], DP2[i+1])
    DP = DP2
print(bisect(DP, L)-1)

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
V=sum(v)
INF=10**15
dp=[[INF for j in range(V+1)] for i in range(N+1)]
#dp[i][j]:iまで試して価値の合計がjのときの重さの最小値
dp[0][0]=0
for i in range(N):
    for j in range(V+1):
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i],INF)
        else:
            dp[i+1][j]=min(dp[i][j],INF)
b=[]
for i in range(V+1):
    if dp[N][i]!=INF:
        b.append((dp[N][i],i))
ans=0
for (x,y) in b:
    if x<=W:
        ans=max(ans,y)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(lambda: float('inf'))
dp[0] = 0
for w, v in Things:
    for nv, nw in list(dp.items()):
        if nw + w <= W:
            dp[nv + v] = min(dp[nv + v], nw + w)
ans = 0
for v, w in dp.items():
    if w <= W and v >= ans:
        ans = v
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [[1000000001 for i in range(N*1000+1)] for j in range(N+1)]
dp[0][0] = 0
for j in range(N):
    w, v = map(int, input().split())
    for k in range(N*1000+1):
        dp[j+1][k] = min(dp[j][k-v] + w, dp[j][k])


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

Submission status: Accepted

Solution code:
N, W = map(int, raw_input().split())
INF = 0x3f3f3f3f
obj = []
for i in xrange(N):
    w, v = map(int, raw_input().split())
    obj.append((w, v))
dp = [[INF for _ in xrange(100001)] for i in xrange(N)]

w, v = obj[0]
dp[0][0] = 0
dp[0][v] = w
for i in xrange(1, N):
    w, v = obj[i]
    for j in xrange(100001):
        if dp[i-1][j] != INF:
            dp[i][j] = dp[i-1][j]
    for j in xrange(v, 100001):
        if dp[i-1][j-v] != INF and dp[i-1][j-v]+w <= W:
            dp[i][j] = min(dp[i][j], dp[i-1][j-v]+w)
res = 0
for i in xrange(100001):
    if dp[N-1][i] != INF:
        res = i
print res

Submission status: Accepted

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

# dp[i] := 価値[i]に対する最低の重さ
dp = [float('inf')] * (N * 10 ** 3 + 1)
dp[0] = 0

for w, v in Items:
    for i in range(len(dp))[::-1]:
        if i - v < 0:
            continue
        dp[i] = min(dp[i], dp[i - v] + w)

for v, res in zip(range(len(dp))[::-1], dp[::-1]):
    if res <= W:
        print(v)
        exit()

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(N)]
V=10**3

DP_V=[float("inf")]*(V*N+1)
DP_V[0]=0
for i in range(N):
    for j in range(V*N,-1,-1):
        if j+WV[i][1]<=V*N:
            DP_V[j+WV[i][1]]=min(DP_V[j+WV[i][1]],DP_V[j]+WV[i][0])

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

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()
wv = []
for _ in range(n):
    wv.append(tuple(li()))
    
MAX = 10**15
SIZE = 10**5+1
UPPER = 10**12
    
dp = [[MAX]*SIZE for _ in range(n+1)]
for item in range(n):
    dp[item][0] = 0

for item in range(n):
    wi, vi = wv[item]
    for value in range(1, SIZE):
        if value - vi >= 0:
            if 0 <= dp[item][value-vi] + wi <= w:
                dp[item+1][value] = min(dp[item][value],
                                        dp[item][value-vi] + wi)
                
            else:
                dp[item+1][value] = dp[item][value]
            
        else:
            dp[item+1][value] = dp[item][value]
        

ans = 0
for value in range(SIZE):
    if dp[n][value] <= UPPER:
        ans = max(ans, value)
        
print(ans)