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:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]

INF = 10 ** 10
dp = [[INF] * (N * 1000 + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(N * 1000 + 1):
        if j <= wv[i - 1][1]:
            dp[i][j] = min(dp[i][j], wv[i - 1][0])
        else:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - wv[i - 1][1]] + wv[i - 1][0])
        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 = 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())))
max_val=1000*n
dp=[[float('inf') for i in range(max_val+1)] for j in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
	for j in range(0,max_val+1):
		dp[i][j]=dp[i-1][j]
		if(l[i-1][1]<=j):
			dp[i][j]=min(dp[i][j],dp[i-1][j-l[i-1][1]]+l[i-1][0])

for i in range(max_val,-1,-1):
	if(dp[n][i]<=w):
		print(i)
		break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
INF = float("inf")
# Input#
# n = int(input())
n, tar_w = map(int, input().split())

w = [-1]
v = [-1]
value_max = 0
for i in range(n):
    w_in, v_in = list(map(int, input().split()))
    w.append(w_in)
    v.append(v_in)
    value_max += v_in


memo = [[-1] * (value_max + 1) for i in range(n + 1)]

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

for i in range(value_max + 1):
    memo[0][i] = INF


def dp(i, value):
    if memo[i][value] == -1:
        if value > v[i]:
            rest = dp(i - 1, value - v[i])
            if rest == INF:
                tar = INF
            else:
                tar = rest + w[i]
            memo[i][value] = min(dp(i - 1, value), tar)
        else:
            memo[i][value] = min(dp(i - 1, value), w[i])
    return memo[i][value]


ans = -1
OK_MAX = 0
NG_MIN = value_max + 1

while OK_MAX + 1 != NG_MIN:
    i = int((OK_MAX + NG_MIN) / 2)
    ans_tmp = dp(n, i)
    if ans_tmp <= tar_w:
        OK_MAX = i
    else:
        NG_MIN = i

ans = OK_MAX

print("{}".format(ans))

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
w, v = [0], [0]
for i in range(N):
    w_i, v_i = map(int, input().split())
    w.append(w_i)
    v.append(v_i)
sum_V = sum(v)
DP = [[float('inf') for c in range(sum_V+1)] for i in range(N+1)]

for i in range(0, N+1):
    for c in range(0, sum_V+1):
        if i == 0:
            if c == 0:
                DP[i][c] = 0
        elif c - v[i] < 0:
            DP[i][c] = DP[i-1][c]
        else:
            DP[i][c] = min(DP[i-1][c], DP[i-1][c-v[i]] + w[i])
ans = sum_V
while (DP[N][ans] > W):
    ans -= 1
print(ans)

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)]
vmax = sum([wv[i][1] for i in range(N)])
INF = 10**20
  
dp = np.full(vmax+1, INF)
dp[0] = 0

for i in range(N):
  w,v = wv[i-1]
  dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
  
print(max([i for i in range(vmax+1) if dp[i] <= W]))

Submission status: Accepted

Solution code:
n,w = [int(x) for x in input().split()]
wts = []
vals = []
for i in range(n):
    wi,vi = [int(x) for x in input().split()]
    wts.append(wi)
    vals.append(vi)

valsum = sum(vals)
dp = []
maxval = 0
for i  in range(n):
    dp.append([float('inf')]*(valsum+1))

for j in range(valsum+1):
    if j==vals[0]:
        dp[0][j] = wts[0]
        if wts[0]<=w:
            maxval = max(maxval,j)

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

for i in range(1,n):
    for j in range(1,valsum+1):
        if j>=vals[i]:
            dp[i][j] = min(dp[i-1][j-vals[i]]+wts[i],dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
        if dp[i][j]<=w:
            maxval = max(maxval,j)
print(maxval)

Submission status: Accepted

Solution code:
#E
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())
w=[0]+w
v=[0]+v
INF=float('inf')
dp=[[INF for i in range(N+1)] for j in range(10**5+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(10**5+1):
        if j-v[i]>=0:
            dp[j][i]=min(dp[j-v[i]][i-1]+w[i],dp[j][i-1])
        else:
            dp[j][i]=dp[j][i-1]
t=True
n=1
while t:
    if dp[-n][N]<=W:
        print(10**5-n+1)
        t=False
    else:
        n+=1

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


import numpy as np
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) #ナップサックに入れた場合
chmin(dp[i+1,j] , dp[i, j]) # ナップサックに入れなかった場合
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, 2 * V_max), 10**12, dtype=np.int64)
    # 初期化
    dp[0][0] = 0  # 一個も選ばず価値が0なら必ず重さも0

    # 更新
    for i in range(N):
        # numba使うならベクトル化しないほうが早い!!!
        for j in range(V_max):
            jv = j + V[i]
            dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
            dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    # 左から見てく
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


import numpy as np
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) #ナップサックに入れた場合
chmin(dp[i+1,j] , dp[i, j]) # ナップサックに入れなかった場合
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    # 初期化
    dp[0][0] = 0  # 一個も選ばず価値が0なら必ず重さも0

    # 更新
    for i in range(N):
        dp[i + 1, :] = np.minimum(dp[i + 1, :], dp[i, :])
        dp[i + 1, V[i]:] = np.minimum(dp[i + 1, V[i]:], dp[i, :-V[i]] + W[i])
        # 以下のコードを高速化
        # for j in range(V_max):
        #     jv = j + V[i]
        #     if jv < V_max:
        #         dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
        #     dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    # 左から見てく
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


import numpy as np
# from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) #ナップサックに入れた場合
chmin(dp[i+1,j] , dp[i, j]) # ナップサックに入れなかった場合
'''


# @njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    # 初期化
    dp[0][0] = 0  # 一個も選ばず価値が0なら必ず重さも0

    # 更新
    for i in range(N):
        dp[i + 1, :] = np.minimum(dp[i + 1, :], dp[i, :])
        dp[i + 1, V[i]:] = np.minimum(dp[i + 1, V[i]:], dp[i, :-V[i]] + W[i])
        # for j in range(V_max):
        #     jv = j + V[i]
        #     if jv < V_max:
        #         dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
        #     dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    # 左から見てく
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


import numpy as np
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) #ナップサックに入れた場合
chmin(dp[i+1,j] , dp[i, j]) # ナップサックに入れなかった場合
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    # 初期化
    dp[0,0] = 0  # 一個も選ばず価値が0なら必ず重さも0

    # 更新
    for i in range(N):
        dp[i + 1, :] = np.minimum(dp[i + 1, :], dp[i, :])
        for j in range(V_max):
            jv = j + V[i]
            if jv>=V_max:
              break
            dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])

    # 左から見てく
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


import numpy as np
from numba import njit

N, W_max = ints()
W, V = read_col(N)
W = np.array(W, dtype=np.int64)
V = np.array(V, dtype=np.int64)

'''
dp[i,j] ... 重さの最小 (:iまで考慮したとき、価値がちょうどjのとき)
答えはW以下の数字が入ってるマスの一番左側

更新則
chmin(dp[i+1,j+V[i]] , dp[i, j]+W[i]) #ナップサックに入れた場合
chmin(dp[i+1,j] , dp[i, j]) # ナップサックに入れなかった場合
'''


@njit('(i8, i8, i8[:], i8[:])', cache=True)
def solve(N, W_max, W, V):
    V_max = np.sum(V) + 1
    dp = np.full((N + 1, V_max), 10**12, dtype=np.int64)
    # 初期化
    dp[0][0] = 0  # 一個も選ばず価値が0なら必ず重さも0

    # 更新
    for i in range(N):
        for j in range(V_max):
            jv = j + V[i]
            if jv < V_max:
                dp[i + 1, jv] = min(dp[i + 1, jv], dp[i, j] + W[i])
            dp[i + 1, j] = min(dp[i + 1, j], dp[i, j])

    # 左から見てく
    for j in range(V_max - 1, -1, -1):
        if np.any(dp[:, j] <= W_max):
            print(j)
            return


solve(N, W_max, W, V)

Submission status: Accepted

Solution code:
import numpy as np

n, W = map(int, input().split())
w = []
v = []
for i in range(n):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)
  
dp = np.full(10**3 *n +1, 10**18)
dp[0] = 0

for i in range(n):
  dp[v[i]:] = np.minimum(dp[v[i]:], dp[:-v[i]]+w[i])
  
ans = 0
for i in range(10**3 *n, -1, -1):
  if dp[i] <= W:
    ans = i
    break
    
print(ans)

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
wv = [0]
for i in range(N):
    wv.append(list(map(int,input().split())))
    
#- dp[i][j] i番目までの品物から、価値がjとなるように選んだ時の、重さの最小値
Vmax = 10**3*100
dp = [[float('inf')]*(Vmax+1) for i in range(N+1)]
dp[0][0]=0#なにも品物を選ばないなら価値0で重さ0

for i in range(1,N+1):#N番目以降は品物がもうないので0。→N-1からやる
    for j in range(0,Vmax+1): #価値でループ
        if j<wv[i][1]:#i番目の荷物の価値がそもそも入れたい価値よりも大きい→いれられない
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-wv[i][1]]+wv[i][0])#いれない or いれる　の大きいほう
#最後の出力は、最終番目以降の品物(つまり、全部)から、価値の大きいほうから見ていき、許容W以下のもの
for i in range(Vmax,-1,-1):
    if dp[N][i] <= W:
        print(i)
        break

Submission status: Accepted

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


# dp[i][j]=(i番目までの品物を、価値がj以上になるように選んだときの最小重さ)
# N<=100, v_i<=1000 なので、価値の総和<=100000
dp = [[10**12 for _ in range(100001)] for _ in range(N + 1)]
dp[0][0] = 0
# print(dp)
for i in range(1, N + 1):
    for j in range(0, 100001):
        # i番目のアイテムを入れることができる場合
        if j - wv[i][1] >= 0:
            # i番目のアイテムを入れない場合、入れる場合
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        # i番目のアイテムを入れることができない場合
        else:
            dp[i][j] = dp[i - 1][j]

# 1<= 価値の総和 <=100000
# 100000から降順に、本当にナップサックに入るのか確かめる
ans = 100000
while(dp[N][ans] > W):
    ans -= 1

# print(dp)
print(ans)

Submission status: Accepted

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

# dp[i][j]=(i番目までの品物を、価値がj以上になるように選んだときの最小重さ)
dp = [[10**12 for _ in range(100001)] for _ in range(N+1)]
dp[0][0] = 0
# print(dp)
for i in range(1, N + 1):
    for j in range(0, 100001):
        # i番目のアイテムを入れることができる場合
        if j - wv[i][1] >= 0:
            # 実際にアイテムを入れる場合、入れない場合
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        # i番目のアイテムを入れることができない場合
        else:
            dp[i][j] = dp[i - 1][j]

ans = 100000
while(dp[N][ans] > W):
    ans -= 1

# print(dp)
print(ans)

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[float('inf') for _ in range(10**5+1)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    weight,value=a[i]
    for j in range(10**5+1):
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        if j+value<=10**5:
            dp[i+1][j+value]=min(dp[i][j+value],dp[i][j]+weight)
for i in range(10**5+1):
    if dp[-1][-i-1]<=W:
        print(10**5-i)
        break

Submission status: Accepted

Solution code:
n,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
m=sum([a[i][1] for i in range(n)])
dp=[[float('inf') for _ in range(m+1)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    weight,value=a[i]
    for j in range(m+1):
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        if j+value<=m:
            dp[i+1][j+value]=min(dp[i][j+value],dp[i][j]+weight)
for i in range(m+1):
    if dp[-1][-i-1]<=W:
        print(m-i)
        break

Submission status: Accepted

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

dp=[inf]*100001
dp[0]=0


for i in range(0,n):
    nextdp=[inf]*100001
    x=[int(i) for i in input().split()]
    for j in range(100001):
        if x[1] <= j:
            nextdp[j]=min(dp[j],x[0]+dp[j-x[1]])
        else:
            nextdp[j]=dp[j]
    dp=nextdp


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

Submission status: Accepted

Solution code:
import math

n, W = map(int, input().split())
costs, weights = [], []
sum_vals = 0
for i in range(n):
    a,b =map(int, input().split())
    sum_vals+=b
    costs.append(b)
    weights.append(a)
dp = [int(10e18)+1]*(sum_vals+1)
dp[0] = 0
for item in range(0, n):
    for value_already in range(sum_vals-costs[item], -1, -1):
        dp[value_already+costs[item]] = min(dp[value_already+costs[item]], dp[value_already]+weights[item])
ans = 0
for i in range(1, sum_vals+1):
    if(dp[i]<= W):
        ans = max(ans, i)
print(ans)

Submission status: Accepted

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

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

V_MAX = 10**5
dp = [[w + 1] * (V_MAX + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i, (wi, vi) in enumerate(items):
    for j in range(V_MAX + 1):
        if j >= vi:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - vi] + wi)
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0
for j in range(V_MAX + 1):
    if dp[n][j] <= w:
        ans = max(ans, j)

print(ans)

Submission status: Accepted

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

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

V_MAX = 10**5
dp = [[w + 1] * (V_MAX + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i, (wi, vi) in enumerate(items):
    for j in range(V_MAX + 1):
        if j >= vi:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - vi] + wi)
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0
for i in range(n + 1):
    for j in range(V_MAX + 1):
        if dp[i][j] <= w:
            ans = max(ans, j)

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')    
dp=[[inf for i in range(N+1)] for j in range(N*1000+1)] 

dp[0][0]=0

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


            
for i in reversed(range(N*1000+1)):
    if dp[i][N]<=W:
        print(i)
        break
#for i in reversed(range(N*1000+1)):
 #   print('{} '.format(i),dp[i][N])

Submission status: Accepted

Solution code:
def main():
    item_count, capacity = [int(x) for x in input().split()]
    weights, values = [], []
    for _ in range(item_count):
        w, v = [int(x) for x in input().split()]
        weights.append(w)
        values.append(v)

    # dp[ i ][ sum_v ] := i 番目までの品物から価値が sum_v 以上を
    #                     達成するように選んだときの、重さの総和の最小値
    INF = 10 ** 9 + 1
    max_v = sum(values)
    dp = [[INF] * (max_v + 1) for _ in range(item_count)]
    for i in range(item_count):
        dp[i][0] = 0
    ans = 0
    for item_i in range(item_count):
        for sum_v in range(1, max_v + 1):
            v = values[item_i]
            if v <= sum_v:
                min_w = min(
                    # weights[item_i], values[item_i] を選ぶ場合。
                    # ここで価値が負にならないよう条件分岐した。
                    dp[item_i - 1][sum_v - v] + weights[item_i],
                    dp[item_i - 1][sum_v])
            else:
                min_w = dp[item_i - 1][sum_v]
            dp[item_i][sum_v] = min_w
            if min_w <= capacity:
                ans = max(ans, sum_v)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, W = map(int,input().split())
dp = [W+1]*(10**5 + 1)
vr=[]
for i in range(n):
  w,v= map(int,input().split())
  vr.append(v)
  if i==0:
  	dp[v]=w
  for j in range(10**5-v,-1,-1):
  	cw=w+dp[j]
  	if j==v and vr.count(v)==1:
  		continue
  	if cw<=W:
  		dp[j+v]=min(dp[j+v],cw)
  dp[v]=min(w,dp[v])

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

Submission status: Accepted

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

w_list = [0] * n
v_list = [0] * n
for i in range(n):
    w_list[i], v_list[i] = map(int, input().split())
v_max = sum(v_list)
dp = [10 ** 9 + 1] * (v_max + 1)

for i, v in enumerate(v_list):
    for j in range(v_max, 0, - 1):
        x = dp[j] + w_list[i]
        if x <= w and x < dp[j + v]:
            dp[j + v] = x
    dp[v] = min(dp[v], w_list[i])

for v in range(v_max, -1, -1):
    if dp[v] <= w:
        print(v)
        quit()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
ITEM = []
vmax, wmax = 0,0
for _ in range(N):
  w,v = map(int, input().split())
  ITEM.append((v,w))
  vmax = max(vmax,v)
  wmax = max(wmax,w)

INF = 10**18
    
def solve1():
  #dp[i][v] i個めまで選んで、価値Vを実現するための最小の重量
  # TLEしたらiを消す。
  dp = [INF] * (vmax*N+1)
  dp[0] = 0
  for i in range(1,N+1):
    v1,w1 = ITEM[i-1]
    # dp[i]消すなら、vは大きい方から探索する
    for v in range(vmax*i,-1,-1):
      if v-v1>=0:
        dp[v] = min(dp[v], dp[v-v1]+w1)
  ret = 0
  for i in range(len(dp)):
    if dp[i] <= W:
      ret = max(ret, i)
  #print(dp[:30])
  return ret

ans = solve1()
  
print(ans)

Submission status: Accepted

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

dp = [[1000000001] * 100001 for _ in range(N + 1)] #i番目までで価値がj以上となる最小重さ
dp[0][0] = 100000001
ans = 0
for i in range(1, N + 1):
    for j in range(1, 100001):
        if v[i] < j:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
        else:
            dp[i][j] = min(dp[i - 1][j], w[i])


for i in range(100001):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import numba
import math

@numba.njit
def main():
    dpt = np.array([math.inf] * (10**3*N + 1))
    dpt[0] = 0
    for i in range(N):
        for j in range(len(dpt)-1, items[i][1]-1, -1):
            dpt[j] = min(dpt[j], dpt[j-items[i][1]]+items[i][0])

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

if __name__ == '__main__':
    N, W = map(int, input().split())
    items = np.array([list(map(int, input().split())) for i in range(N)])
    main()

Submission status: Accepted

Solution code:
# https://www.geeksforgeeks.org/knapsack-with-large-weights/

# in this question we are basicallly forced to alter the state so be alble to solve the problem within time constraints
# here W (capacity of knapsak is huge ,like order 10^9)
# but the thing to be considered is the low value of price
# submitted at Atcoder https://atcoder.jp/contests/dp/tasks/dp_e

# here max profit is 10*3 and N<=100

n,W=map(int,input().split())
wt,values=[],[]
for _ in range(n):
    w,val=map(int,input().split())
    wt.append(w)
    values.append(val)
# since for an i we only need look at i-1 row hence 1D array can be used to memoise
# inner loop goes backward since we can take an item more then once (bounded Knapsack)
# dp[j] is gives the min weight required to earn j profit
max_profit=max(values)*n # not neccessary we can take it n*10^3
dp=[float('inf')]*(max_profit+1)
dp[0]=0

for i in range(n):
    for j in range(max_profit,values[i]-1,-1):
        dp[j]=min(dp[j],wt[i]+dp[j-values[i]])
    #print(dp)
ans=0

for i in range(1,max_profit+1):
    if dp[i]<=W:
        ans=i
print(ans)

Submission status: Accepted

Solution code:
import sys
 
import numba as nb
import numpy as np
 
input = sys.stdin.readline
 
 
@nb.njit("i8(i8,i8,i8[:],i8[:])")
def solve(N, W, w, v):
    dp = np.full(shape=(N + 1, np.sum(v) + 1), fill_value=(N * W), dtype=np.int64)
    dp[:, 0] = 0
    for i in range(N):
        np.minimum(w[i], dp[i][:v[i]], dp[i + 1][:v[i]])
        np.minimum(w[i] + dp[i][: - v[i]], dp[i][v[i]:], dp[i + 1][v[i]:])
    return np.where(dp[-1] <= W)[0][-1]
 
 
def main():
    N, W = map(int, input().split())
 
    w = np.empty(shape=N, dtype=np.int64)
    v = np.empty(shape=N, dtype=np.int64)
    for i in range(N):
        w[i], v[i] = map(int, input().split())
 
    ans = solve(N, W, w, v)
    print(ans)
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numpy as np

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    wv = [0] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    INF = 10 ** 10
    V = sum(v for _, v in wv)
    dp = np.full(shape=(V + 1), fill_value=INF, dtype=np.int64)
    dp[0] = 0
    for w, v in wv:
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

dp = [[float("inf")]*(n*10**3+1) for _ in range(n+1)]
dp[0][0] = 0

for n_i in range(1, n+1):
  for v_i in range(n*10**3+1):
    if v_i-WV[n_i-1][1]>=0:
      dp[n_i][v_i] = min(dp[n_i-1][v_i], dp[n_i-1][v_i-WV[n_i-1][1]]+WV[n_i-1][0])
    else:
      dp[n_i][v_i] = min(dp[n_i][v_i], dp[n_i-1][v_i])
      
ans = 0
for v_i in range(n*10**3+1):
  if dp[n][v_i]<=w:
    ans = v_i
  
print(ans)

Submission status: Accepted

Solution code:


INF = float('inf')


def tc():
    n, cap = map(int, input().split())
    weights, values = [], []
    for _ in range(n):
        w, v = map(int, input().split())
        weights.append(w)
        values.append(v)
    # swap the definition from previous problem, so that
    # the smaller values are the dp dimension
    # dp[i]: min total weight with total value exactly i
    value_sum = sum(values)
    dp = [INF] * (value_sum + 1)
    dp[0] = 0

    for i in range(n):
        w, v = weights[i], values[i]
        # remember to reverse, because you don't want
        # to doublecount the same items
        for prev_v in reversed(range(value_sum - v + 1)):
            dp[prev_v + v] = min(dp[prev_v + v], dp[prev_v] + w)

    ans = 0
    for v, w in enumerate(dp):
        if w <= cap:
            ans = max(ans, v)

    print(ans)


tc()

Submission status: Accepted

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

# やることは一緒だけど, WがくそでかいのでこのままだとTLE
# なので発想を変えて, 保存する状態量を変更するのがポイント
# dp[i][j]:i番目までの品物から, "価値が"（ちょうど）jになるように詰めた時の最小の重さ
# 価値は高々100*10**3だから間に合うハズ

V=sum(v)
dp=[[float("inf") for j in range(V+1)] for i in range(N)]
dp[0][0]=0
dp[0][v[0]]=w[0]
# print(dp)

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

ans=V
while dp[N-1][ans]>W:
    ans-=1
print(ans)

Submission status: Accepted

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


INF = 10**18


def main():

    N, W = in_nn()
    w, v = [], []
    for i in range(N):
        a, b = in_nn()
        w.append(a)
        v.append(b)

    V = 10**5 + 1
    dp = [INF] * (V + 1)
    dp[0] = 0

    for i in range(N):
        next_dp = copy(dp)
        for j in range(V):
            if j + v[i] <= V:
                next_dp[j + v[i]] = min(next_dp[j + v[i]], dp[j] + w[i])
            else:
                break
        dp = next_dp

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,W = map(int,input().split())
 
import numpy as np
dp = np.full(10 ** 5 + 1, W + 1, dtype = int)
dp[0] = 0

for i in range(N):
  w, v = map(int, input().split())
  np.minimum(dp[:-v] + w, dp[v:], out = dp[v:])

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