Problem:


Score : 100 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

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

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

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

Sample Input 2

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

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

Sample Output 3

17

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



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    WV = [[int(x) for x in input().split()] for _ in range(N)]

    sumv = 0
    for w, v in WV:
        sumv += v

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

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

    ans = 0
    for i in range(sumv + 1):
        if dp[N][i] > W:
            break
        else:
            ans = i

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    WV = [[int(x) for x in input().split()] for _ in range(N)]

    sumv = 0
    for w, v in WV:
        sumv += v

    dp = [[float("inf")] * (sumv + 1) for j in range(N + 1)]

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

    ans = 0
    for i in range(sumv + 1):
        if dp[N][i] > W:
            break
        else:
            ans = i

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,w  = map(int, (input().split()))
goods = [list(map(int, input().split())) for _ in range(n)]
MAX_V = sum(map(lambda x: x[1], goods))+1
INF = 10**19

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

for i in range(1, n+1):
    for j in range(MAX_V):
        #print(dp)
        if j-goods[i-1][1] >= 0:
            dp[i][j] = min(dp[i-1][j-goods[i-1][1]]+goods[i-1][0], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

ans = 0
for i in range(MAX_V):
    if dp[n][i] <= w:
        ans = max(ans, i)

print(ans)

Submission status: Accepted

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

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

for i in range(1, N+1):
  for j in range(total_v+1):
    if j < v[i-1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i-1])
for i in range(total_v, -1, -1):
  if dp[N][i] <= W:
    print(i)
    break

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
nums = []
for _ in range(n):
  nums.append(list(map(int, input().split())))
  
total_v = sum(nums[i][1] for i in range(n))

dp = [[float('inf') for _ in range(total_v+1)] for _ in range(n+1)]
dp[0][0] = 0

for i in range(1, n+1):
  for j in range(total_v+1):
    if j < nums[i-1][1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-nums[i-1][1]] + nums[i-1][0])
for i in range(total_v, -1, -1):
  if dp[n][i] != float('inf') and dp[n][i] <= w:
    print(i)
    break

Submission status: Accepted

Solution code:
# dp[n][w]とすると，O(nw)でwが大きすぎて大変
# dp[n][v]として，価値vを達成するための最小のwを記録するO(N^2 V_{max})
# さらにdp[v]としてw, vを使うかどうかで更新する
import sys
input = sys.stdin.readline
import numpy as np

n, W = map(int, input().split())
dp = np.full(10**5 + 1, 10**12, dtype='int64')
dp[0] = 0 
for _ in range(n):
    w, v = map(int, input().split())
    dp[v:] = np.minimum(dp[:-v]+w, dp[v:])

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [w+1]*(10**5+1)
    dp[0] = 0
    item.sort(key=lambda x: x[1])
    x = 0
    for p, q in item:
        for i in reversed(range(q, min(len(dp), x+q+1))):
            dp[i] = min(dp[i-q]+p, dp[i])
        x += q
    ans = 0
    for i in reversed(range(len(dp))):
        if dp[i] <= w:
            ans = i
            break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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
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:
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())
    
dp = [[10**9+1]*(sum(v)+1) for i in range(N+1)]
dp[0][0] = 0

#v[i]を使うかどうか
for i in range(N):
    #価値がjのときの最小の重さ総量
    for j in range(sum(v)+1):
        if j >= v[i]:
            dp[i+1][j] = min(dp[i][j-v[i]]+w[i],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
            
ans = 0

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

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w = []
v = []
sum_value = 0
inf = 10**9 + 1
for _ in range(N):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
    sum_value += v_

"""
dp[n][i]: n個目までの品物から価値の総量がiよりも大きくなるように選択したときの, 重さの最小値
"""

dp = [[inf] * (sum_value+1) for _ in range(N+1)]
dp[0][0] = 0


for n in range(1, N+1):
    for i in range(sum_value+1):
        if i >= v[n-1]:
            dp[n][i] = min(dp[n-1][i], dp[n-1][i-v[n-1]] + w[n-1])
        else:
            dp[n][i] = dp[n-1][i]
for i in range(sum_value+1)[::-1]:
    if dp[N][i] != inf and dp[N][i] <= W:
        print(i)
        break

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
V = 10 ** 5
inf = 10 ** 18
dp = [inf] * (V + 1)
dp[0] = 0

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

for i in range(V+1)[::-1]:
    if dp[i] < inf:
        print(i)
        break

Submission status: Accepted

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    mod = 1000000007

    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 = 10**5+1
    inf = float('inf')
    dp = [inf]*V
    dp[0] = 0

    for i in range(N):
        for j in range(V-1, v[i]-1, -1):
            if dp[j-v[i]]+w[i]<=W:
                dp[j] = min(dp[j], dp[j-v[i]]+w[i])
    
    res = 0
    for i, x in enumerate(dp):
        if x <= W:
            res = i
    print(res)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#典型ナップザック
#10**9はMLE(pypyではRE)

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    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 = 10**5+1
    inf = float('inf')
    dp = [inf]*V
    dp[0] = 0
    for i in range(N):
        for j in range(V, v[i]-1, -1):
            if dp[j-v[i]]+w[i]<=W:
                dp[j] = min(dp[j], dp[j-v[i]]+w[i])
    for i in range(V):
        if dp[-(i+1)]<=W:
            print(V-(i+1))
            exit()
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
inf = 10**10
V = 0
for a in range(N):
	V += A[a][1]
dp = [inf for v in range(V+1)]
dp[0] = 0
for p in range(N):
	for q in range(V - A[p][1], -1, -1):
		dp[q + A[p][1]] = min(dp[q + A[p][1]], dp[q] + A[p][0])
# print(dp)
ans = 0
for b in range(V+1):
	if (dp[b] <= W):
		ans = b
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,w = map(int,input().split())
dp = np.full(100001,w+1,dtype=int)
dp[0] = 0
for i in range(n):
    we,va = map(int, input().split())
    dp[va:] = np.minimum(dp[va:],dp[:-va]+we)
print(np.max(np.where(dp <= w)))

Submission status: Accepted

Solution code:
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
'''
w = [0]*N
v = [0]*N
for i in range(N):
        w[i], v[i] = map(int, sys.stdin.readline().split())
'''
INF = 10**11+1
dp = [[INF]*(N+1) for j in range(N*(10**3)+10)]
i = 0
ans = INF
while(True):
        for j in range(1, N+1):
                #print(i, j)
                w = WV[j-1][1]
                if i-w >= 0:
                        dp[i][j] = min(dp[i][j-1], dp[i-w][j-1]+WV[j-1][0])
                        #dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        #print(dp[i][N])
        #print(i, dp[i][N])
        if dp[i][N] > W and ans <= W:
                print(i)
                exit()
        ans = dp[i][N]
        '''
        if dp[i][N] >= W:
                if ans == 0:
                        ans = dp[i][N]
                elif ans < dp[i][N]:
                        print(i)
                        exit()
                print(i, ans)
        '''
        i += 1

Submission status: Accepted

Solution code:
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
'''
w = [0]*N
v = [0]*N
for i in range(N):
        w[i], v[i] = map(int, sys.stdin.readline().split())
'''
INF = 10**11+1
dp = [[INF]*(N+1) for j in range(N*(10**3)+10)]
i = 1
ans = INF
while(True):
        for j in range(1, N+1):
                #print(i, j)
                w = WV[j-1][1]
                if i-w > 0:
                        dp[i][j] = min(dp[i][j-1], dp[i-w][j-1]+WV[j-1][0])
                        #dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        #print(dp[i][N])
        #print(i, dp[i][N])
        if dp[i][N] > W and ans <= W:
                print(i-1)
                exit()
        ans = dp[i][N]
        '''
        if dp[i][N] >= W:
                if ans == 0:
                        ans = dp[i][N]
                elif ans < dp[i][N]:
                        print(i)
                        exit()
                print(i, ans)
        '''
        i += 1

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
item = [[0] * 2 for _ in range(N)]
for i in range(N):
    w, v = map(int, input().split())
    item[i][0], item[i][1] = w, v
dp = [[1000000001] * (1000*N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for j in range(1000*N+1):
        if item[i-1][1] <= j:
            dp[i][j] = min(dp[i-1][j-item[i-1][1]] + item[i-1][0], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
for i in range(1000*N+1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for _ in range(N)]

V = 0
# sum_v = 0
for w, v in L:
    V += v

dp = [[INF] * (V+1) for i in range(N+1)]
dp[0][0] = 0

# V = sum(v)
for i in range(1, N+1):
    for j in range(0, V+1):
        # j，1スタートだと16,0スタートだと17になる
        w = L[i-1][0]
        v = L[i-1][1]
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j - v] + w, dp[i][j])
        dp[i][j] = min(dp[i][j], dp[i-1][j])

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
f_max = 10**9+100 

dp = [[f_max] * (10**5 +100) for _ in range(N+1)]
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
def chmax(a,b):
    if a < b:
        return b
    else:
        return a
def main():
    # 初期条件
    dp[0][0]=0
    for i in range(1,N+1):
        w,v = wv[i-1][0], wv[i-1][1]
        for sum_v in range(10**5+1):
            if sum_v - v >= 0:
                dp[i][sum_v] = chmin(dp[i][sum_v], dp[i-1][sum_v-v]+ w)
            
            dp[i][sum_v] = chmin(dp[i][sum_v],dp[i-1][sum_v])
    
    ans = 0
    for i in range(10**5+100):
        if dp[N][i] <= W:
            ans = i
    
    print(ans)  

            
 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Fri Mar  6 16:01:31 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N, W = na()
wv = nan(N)
MAX_V = 100100
dp = [[inf] * MAX_V for _ in range(N + 1)]
dp[0][0] = 0

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

ans = inf
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())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
sv = sum(v)
dp = [[int(1e10)] * (sv+1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(sv + 1):
        if j - v[i-1] >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j - v[i-1]] + w[i-1])
        else:
            dp[i][j] = dp[i-1][j]
#print(dp)
ans = sv
while(dp[N][ans] > W):
    ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
l = []
for i in range(N):
  L = list(map(int, input().split()))
  l.append(L)
sum_of_weight = 0
sum_of_value = 0
for i in range(N):
  sum_of_weight += l[i][0]
  sum_of_value += l[i][1]
dp = [[sum_of_weight+1 for i in range(sum_of_value+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  for j in range(sum_of_value+1):
    if j >= l[i-1][1]:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-l[i-1][1]]+l[i-1][0])
    else:
      dp[i][j] = dp[i-1][j]
ans = 0
for i in range(N+1):
  for j in range(sum_of_value+1):
    if W >= dp[i][j] and ans < j:
      ans = j
print(ans)

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())
V = sum(v)
dp = [[float('inf')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j>=v[i]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i])
        else:
            dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if dp[N][j] <= W:
        ans = j
print(ans)

Submission status: Accepted

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

INF = 10**9 + 100
MAX_V = 10**5 + 100
dp = [INF] * (MAX_V + 1)
dp[0] = 0

for wi, vi in wv:
    for sum_v in range(MAX_V, vi-1, -1):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])
#print(dp)
ans = 0
for i in range(MAX_V, -1, -1):
    if dp[i] <= w:
        print(i)
        exit()
#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())

inf=float("inf")
sumV=sum(v)
dp=[[inf]*(sumV+1) for i in range(N+1)]
dp[0][0]=0

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

ans=0
for g in range(len(dp[-1])):
    if dp[-1][g]<=W:
        ans=g

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N,W=map(int,input().split())
max_Vi = 10**3
max_Wi = W
dp=[0]+[max_Wi+1]*(N*max_Vi)
dp=np.array(dp)
for i in range(N):
  wi,vi=map(int,input().split())
  dp[vi:]=np.minimum(dp[vi:],dp[:-vi]+wi)
print(np.max(np.where(dp <= W)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N,W=map(int,input().split())
dp=np.ones(10**5+1, dtype='int64')
dp[0]=0
dp[1:]=dp[1:]*(10**9+1)
for i in range(N):
  wi,vi=map(int,input().split())
  dp[vi:]=np.minimum(dp[vi:],dp[:-vi]+wi)
print(np.max(np.where(dp <= W)))

Submission status: Accepted

Solution code:
import numpy as np
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10**9 + 100
MAX_V = 10 ** 6

dp = np.full((n+1, MAX_V), INF, np.int64)
dp[0][0] = 0

for i, (wi, vi) in enumerate(wv):
    dp[i+1] = dp[i]
    np.minimum(dp[i][vi:], dp[i][:-vi] + wi, out=dp[i+1][vi:])

ans = np.where(dp[n] <= w)[0][-1]
print(ans)

Submission status: Accepted

Solution code:
dp = [[float('inf') for _ in range(10**5+10)] for _ in range(10**2+10)]

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)

#初期条件
dp[0][0] = 0

for i in range(N):
    for sum_v in range(10**5+10):
        if v[i] <= sum_v:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v-v[i]] + w[i])
        else:
            dp[i+1][sum_v] = dp[i][sum_v]
            
#最適値の出力
res = 0

for i in range (10**5+10):
    if (dp[N][i] <= W):
        res = i

print(res)

Submission status: Accepted

Solution code:
import numpy as np  

n, w = map(int, input().split())
dp = np.full(n*1000+1, float('inf'))
dp[0] = 0

for _ in range(n):
    weight, value = map(int, input().split())
    dp[value:] = np.minimum(dp[value:], dp[:-value] + weight) 

print(np.max(np.where(dp <= w)))

Submission status: Accepted

Solution code:
'''

                            Online Python Compiler.
                Code, Compile, Run and Debug python program online.
Write your code in this editor and press "Run" button to execute it.

'''

firstline = str(input())
firstline = firstline.split()
n = int( firstline[0] )
total = int( firstline[1] )

maxvalue = int( pow(10, 5) + 1)
#maxvalue = 100
colums = [10000000001000000000 for _ in range(maxvalue)]
dp = [ colums[::] for _ in range(n+1) ]

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

stone = []

for i in range(n):
    getInput = str(input())
    getInput = getInput.split()
    stone.append(( int(getInput[1]) , int(getInput[0]) ) )

stone = sorted(stone)

index = 0
for currentstone in stone:
    currentvalue = currentstone[0]
    currentweight = currentstone[1]
    index += 1 
    for V in range(1, maxvalue):
        if currentvalue <= V:
            dp[index][V] = min(currentweight + dp[index-1][V - currentvalue], dp[index - 1][V])
        else:
            dp[index][V] = dp[index-1][V]

bestvalue = 0
for i in range(1, maxvalue ):
    if dp[n][i] <= total and dp[n][i] !=9999999 :
        bestvalue = i
#print(stone)
#
print(bestvalue)

Submission status: Accepted

Solution code:
def main():
    N,W=map(int,input().split())
    w=[0]*(N+1)
    v=[0]*(N+1)
    for i in range(1,N+1):
        a,b=map(int,input().split())
        w[i]=a
        v[i]=b
    v_sum=sum(v)
    inf=10**12
    dp=[[inf]*(v_sum+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(1,v_sum+1):
            dp[i][j]=min(dp[i-1][j],dp[i-1][max(0,j-v[i])]+w[i])

    for j in range(v_sum+1):
        if dp[N][j]>W:
            result=j-1
            break
        if j==v_sum:
            result=j
    print(result)

if __name__=="__main__":
    main()

Submission status: Accepted

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

    Wi, Vi = [], []
    for _ in range(N):
        w, v = tuple(map(int, input().split()))
        Wi.append(w)
        Vi.append(v)

    # print(N, W)
    # print(Wi, Vi)

    return N, W, Wi, Vi


def solve(N, W, Wi, Vi):
    DP = [[float("inf")] * (sum(Vi) + 1) for _ in range(N + 1)]

    DP[0][0] = 0

    for i in range(N):
        value = Vi[i]
        w_max = sum(Vi) + 1
        for v in range(w_max):
            remain = v - value
            if 0 <= remain:
                # 選ぶ
                DP[i + 1][v] = min(DP[i + 1][v], DP[i][remain] + Wi[i])
            # 選ばない
            DP[i + 1][v] = min(DP[i + 1][v], DP[i][v])

    # print(DP)
    ans = 0
    for line in DP:
        for v, e in enumerate(line):
            if not e == float("inf") and e <= W:
                # print(v, e)
                ans = max(ans, v)

    # print(DP)

    return ans


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
dp = [[10000000000000 for _ in range(2001 * N + 10)] for _ in range(N + 2) ]
ans = 0
for i in range(N):
    dp[i][0] = 0
for i in range(N):
    for j in range(N * 1000):
      	
        dp[i + 1][j + v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
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,input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[float("inf")] * (10**5+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(1, 10**5+1):
        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:
n, w = map(int, input().split())

import numpy as np 

dp = np.full(1000*n+1, w+1, dtype=int)

dp[0] = 0

for i in range(n):
    weight, value = map(int, input().split())
    dp[value:] = np.minimum(dp[value:], dp[:-value] + weight)

print(np.max(np.where(dp <= w)))

Submission status: Accepted

Solution code:
N,W=map(int,input().split())
weight=[0]*N
value=[0]*N
sumv=0
for i in range(N):
    weight[i],value[i]=map(int,input().split())
    sumv+=value[i]
dp=[[1000000000000]*(sumv+1) for i in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(sumv+1):
        if(value[i]<=j):
            dp[i+1][j]=min(dp[i][j-value[i]]+weight[i],dp[i][j])
        else:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
res=0
for i in range(sumv+1):
    if(dp[N][i]<=W):
        res=max(res,i)
print(res)

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)

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    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[i][j]: 0〜(i-1)まで使ったときの価値jのときの重みの総和の最小値
    dp = [[sum(w)]*(sum_v+1) for i in range(N+1)]
    dp[0][0] = 0

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

    print(max([i for i, w in enumerate(dp[N]) if w<=W]))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n ,c = map(int,input().split())
wt =[]; val=[]
wt.append(0);val.append(0)

for _ in range(n):
  wi , vi = map(int,input().split())
  wt.append(wi)
  val.append(vi)
  
# dp [n][max_val] = 0 

max_val = sum(val)
INF = 10 **10
dp = [[INF for i in range(max_val+1)]for j in range(n+1)]

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

for i in range(1,n+1):
  wi = wt[i];vi = val[i]
  for V in range(1,max_val+1):
    if vi<=V:
      dp[i][V] = min(wi+dp[i-1][V-vi] , dp[i-1][V])
    else:
      dp[i][V] = dp[i-1][V]

res = 0

for i in range(max_val+1):
  if dp[n][i] <= c:
    res = i
    
print(res)

Submission status: Accepted

Solution code:
n ,c = map(int,input().split())
wt =[]; val=[]
wt.append(0);val.append(0)
for _ in range(n):
  wi , vi = map(int,input().split())
  wt.append(wi)
  val.append(vi)
  
# dp [n][V+1] = 0 
INF = 10 **10
max_val = sum(val)
dp = [[INF for i in range(max_val+1)]for j in range(n+1)]

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

for i in range(1,n+1):
  wi = wt[i];vi = val[i]
  for V in range(1,max_val+1):
    if vi<=V:
      dp[i][V] = min(wi+dp[i-1][V-vi] , dp[i-1][V])
    else:
      dp[i][V] = dp[i-1][V]
      
res = 0
for i in range(max_val+1):
  if dp[n][i] <= c:
    res = i
    
print(res)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
INF = 10**9+7
NV = (10**3)*N
dp = [[INF for j in range(NV+1)] for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(NV+1):
        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)
ans = 0
for j in range(NV+1):
    if dp[N][j] <= W:
        ans = j
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

N, W = input_nums()

weights = []
values = []

for i in range(N):
    w, v = input_nums()
    weights.append(w)
    values.append(v)

MAXV = 10**5+100
INF = 10**18
# dpの準備
dp = [[INF]*(MAXV+1) for _ in range(N+1)]
# dp初期条件
dp[0][0] = 0
weights.append(0)
values.append(0)

for i in range(N):
    for sum_v in range(MAXV):
        if sum_v - values[i] >= 0:
            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])

res = 0
for sum_v in range(MAXV):
    if dp[N][sum_v] <= W:
        res = sum_v
print(res)

Submission status: Accepted

Solution code:
#knapsack2
n,w=map(int,input().split())
data=[]
for i in range(n):
    u,v=map(int,input().split())
    data.append((u,v))
inf=10**20
pack_min=[[10**20 for i in range(10**5+1)]for _ in range(101)]
#pack_min[i][j]=i番目の荷物までを使って、価値の値をｊにするために必要な重さの最小の値、不可能ならinf
for i in range(101):
    pack_min[i][0]=0
    #価値の値を0にするために必要な重さの最小の値は0である
for i in range(n):
    a,b=data[i][0],data[i][1]
    #a,bはそれぞれ重さ、価値を表すものである
    for j in range(10**5+1):
        if j>=b:
            pack_min[i+1][j]=min(pack_min[i][j],pack_min[i][j-b]+a)
        else:
            pack_min[i+1][j]=pack_min[i][j]

        
ans=0

for i in range(10**5+1):
    if pack_min[n][i]<=w:
        try:
            ans=i
        except:
            break
print(ans)

Submission status: Accepted

Solution code:
def main():
  N,W=map(int,input().split())
  Wlist=[]
  Vlist=[]
  for i in range(N):
    w,v=map(int,input().split())
    Wlist+=[w]
    Vlist+=[v]
  Vmax=max(Vlist)
  V=Vmax*N
  dp=[[float('inf') for p in range(V+1)] for i in range(N)]
  for i in range(V+1):
    if i<=Vlist[0]:
      dp[0][i]=Wlist[0]
  dp[0][0]=0
  for i in range(1,N):
    vi=Vlist[i]
    wi=Wlist[i]
    for j in range(V+1):
      if j-vi>=0:
        dp[i][j]=min(dp[i-1][j-vi]+wi,dp[i-1][j])
      else:
        dp[i][j]=min(dp[i-1][j],dp[i][j])
  dpn=dp[N-1]
  ans=0
  for i in range(V+1):
    if dpn[i]<=W:
      ans=i
  print(ans)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    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 = [[float('inf')] * (max_v * N + 5) for _ in range(N + 5)]

    dp[0][0] = 0

    for i in range(N):
        for j in range(max_v * N):
            if j + v[i] <= max_v * N:
                dp[i+1][j + v[i]] = min(dp[i+1][j + v[i]], dp[i][j] + w[i])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]) 

    ans = 0
    for j in range(max_v * N + 1):
        if dp[N][j] <= W:
            ans = j

    print(ans)

if __name__ == "__main__":
    main()