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:
#!/usr/bin/env python3

def main():
    N, W = map(int, input().split())
    V = N * 10**3
    INF = 10**12
    dp = [INF] * (V+1)# dp[i]: 価値の総和をiにするための重さの最小値
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(V,-1,-1):
            if j-v >= 0:
                dp[j] = min(dp[j],dp[j-v]+w)
    # print(dp)
    ans = -1
    for i in range(V+1):
        if dp[i] <= W:
            ans = i
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    N, W = list(map(int, input().strip().split()))
    items = [[0, 0]]
    for i in range(N):
        items.append(list(map(int, input().strip().split())))
    V = 10**5
    dp = [[0]+[INF]*(V) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, V+1):
            if j-items[i][1] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-items[i][1]]+items[i][0])
    for i in reversed(range(V+1)):
        if dp[N][i] <= W:
            print(i)
            return
    # print(dp[N][:30])
if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    
    def knapsack_price(single=True):
        """
        重さが小さい時のナップサックDP
        :param single: True = 重複なし
        """
        """ dp[price <= V] = 価値を固定した時の最小重量 """
        V = sum(price_list)
        dp_max = W + 1
        dp = [dp_max] * (V + 1)
        dp[0] = 0  # 境界条件：　価値0 の時は重さは0

        for item in range(N):
            if single:
                S = reversed(range(price_list[item], V + 1))
            else:
                S = range(price_list[item], V + 1)
            for price in S:
                dp[price] = min2(dp[price], dp[price - price_list[item]] + weight_list[item])
        return max(price for price in range(V + 1) if dp[price] <= W)

    #######################################################################################################


    def max2(x, y):
        """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
        if x > y:
            return x
        else:
            return y

    def min2(x, y):
        """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
        if x < y:
            return x
        else:
            return y

    N, W = map(int, input().split())  # N: 品物の種類 W: 重量制限

    price_list = []
    weight_list = []
    for _ in range(N):
        """ price と weight が逆転して入力されている場合有り """
        weight, price = map(int, input().split())
        price_list.append(price)
        weight_list.append(weight)

    print(knapsack_price(single=True))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def knapsack_price(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[price <= V] = 価値を固定した時の最小重量 """
    V = sum(price_list)
    dp_max = W+1
    dp = [dp_max] * (V + 1)
    dp[0] = 0   # 境界条件：　価値0 の時は重さは0

    for item in range(N):
        if single:
            S = reversed(range(price_list[item], V + 1))
        else:
            S = range(price_list[item], V + 1)
        for price in S:
            dp[price] = min2(dp[price], dp[price - price_list[item]] + weight_list[item])
    return max(price for price in range(V+1) if dp[price] <= W)


#######################################################################################################
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y

def min2(x, y):
    """ pythonの組み込み関数 min は2変数に対しては遅い！！ """
    if x < y:
        return x
    else:
        return y


N, W = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    """ price と weight が逆転して入力されている場合有り """
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)

print(knapsack_price(single=True))

Submission status: Accepted

Solution code:
#####################################################################################################
##### ナップサック問題　（価値が小さい場合）
#####################################################################################################
"""

経路を状態の添え字に取るような事は無い
経路の末端の情報のみを横軸の添え字に取ることが多い
例：一年生　⇒　k項目までの総和
   パスタ　⇒　k日目に食べたパスタ
   暑い日々⇒　k日目に着た服

DPテーブルにおいて、ある値以降の全てで 1 となる場合、
その値でDPテーブルを切ってしまって、
indexがその値を超えるごとに、DPテーブルの上限に +1 をしていくというアイデアで計算量を減らせる
例: https://atcoder.jp/contests/tdpc/submissions/14958104

初期条件を常に意識するように！

ベンチマーク
（重複なし）
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4641577#1
(重複あり)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4641577#1

"""


import sys
input = sys.stdin.readline



M, W = map(int, input().split())                                # M: 品物の種類 W: 重量制限
single = True                                                   # True = 重複なし

price_list = [0]
weight_list = [0]
for _ in range(M):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

V = sum(price_list)
dp_max = W + 1                                                  # 総和重量の最大値


dp = [[dp_max] * (V + 1) for _ in range(M + 1)]                 # 左端と上端の境界条件で W, M を一個ずつ多めに取る
""" dp[item <= M ][weight <= V] = 価値を固定した時の"最小"重量 """

for item in range(M+1):                                         # 左端の境界条件
    dp[item][0] = 0                                             # 価値 0 を実現するのに必要な品物の個数は 0 個

# for weight in range(W+1):                                     # 上端の境界条件
#     dp[0][weight] = dp_min                                    # 0 種類の品物で実現できる価値総額は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for price in range(1, V+1):
        if price < price_list[item]:                            # price (総価値) < price_list[item] (品物の価値) の時は無視してよい
            dp[item][price] = dp[item - 1][price]
        else:
            temp = dp[item - single][price - price_list[item]] + weight_list[item]  # single = True: 重複なし
            if temp < dp[item-1][price]:                        # min(dp[item-1][price], temp)
                dp[item][price] = temp
            else:
                dp[item][price] = dp[item-1][price]

print(max(price for price in range(V+1) if dp[M][price] <= W))

Submission status: Accepted

Solution code:
N,W = map(int,input().split(" "))
INF =  1e11
v = [INF]*100010
v[0] = 0
for i in range(N):
  weight,value = map(int,input().split(" "))
  for j in range(100001,0,-1):
    if j < value:
      break
    v[j] = min(v[j],v[j-value]+weight)

ans = 0
for i in range(100001,0,-1):
  if v[i] <= W:
    ans = i
    break
print(ans)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
dp = [1001001001] * (1000 * n + 1)
dp[0] = 0
for _ in range(n):
    wi, vi = map(int, input().split())
    for i in range(1000 * n, vi - 1, -1):
        dp[i] = min(dp[i], dp[i-vi] + wi)
print(max(filter(lambda v: dp[v] <= w, range(1000 * n + 1))))

Submission status: Accepted

Solution code:
INF = 10**9 + 7


def main():
    N, W = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(N)]

    dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(10**5 + 1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if 0 <= j - A[i][1]:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - A[i][1]] + A[i][0])
    ans = 0
    for j in range(10**5+1)[::-1]:
        if dp[N][j] <= W:
            ans = j
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#n=int(input())
#n,k=map(int, input().split())
#a=[[0]*n for _ in range(3)]
n,we=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
  w[i],v[i]=map(int,input().split())
dp=[[float('inf')]*(n+1) for _ in range(sum(v)+1)]
for i in range(n+1):
    dp[0][i]=0
for j in range(1,n+1):
  for i in range(1,sum(v)+1):
    if(v[j-1]<=i):
      dp[i][j]=min(w[j-1]+dp[i-v[j-1]][j-1],dp[i][j-1])
    else:
      dp[i][j]=dp[i][j-1]
ans=0
for i in range(sum(v)+1):
  #print(dp[i][n])
  if(dp[i][n]<=we):
  	ans=i
print(ans)

Submission status: Accepted

Solution code:
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
maxValue=sum(values)
dp=[[float("inf")]*(maxValue+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
 
for i in range(1,n+1):
    for j in range(1,maxValue+1):
        if(values[i-1]<=j):
            dp[i][j]=min(weights[i-1]+dp[i-1][j- values[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
 
ans=0
for i in range(maxValue+1):
    if(dp[n][i]<=capacity):
        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())

INF = 10**13 

V = (10**5)+1
# dp[n][v] = n番目までで価値vとなる最小の重さ
dp = [INF] * V
dp[0] = 0
for i in range(N):
    for j in reversed(range(0, V)):
        if (j - v[i] >= 0):
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])

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

print(ans)

Submission status: Accepted

Solution code:
# N個、重さW
N, W = map(int, input().split())

# 重さ, 価値
array = [list(map(int, input().split())) for _ in range(N)]

# 価値の最大値
sum = 1
for i in range(N):
    sum += array[i][1]

weights = [[float('inf')] * (sum + 1) for _ in range(N + 1)]
# 初期値
weights[0][0] = 0
# 価値ごとの重さの最小値を出す
for n in range(N):
    # 価値が0..1000までのそれぞれについて、価値を超えているうちの重さの最小値を算出する
    for v in range(sum + 1):
        # n回目の品物を持ち帰らない場合の重量
        weights[n + 1][v] = weights[n][v]
        weight = weights[n][v - array[n][1]] + array[n][0]
        if weight < weights[n + 1][v]:
            weights[n + 1][v] = weight

ans = 0
for i in range(sum):
    if weights[N][i] <= W:
        ans = i
print(f"{ans}")

Submission status: Accepted

Solution code:
INF = 10**18
N, W = map(int, input().split())

dp = [[INF for i in range(10**5 + 1)] for j 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(10**5 + 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]

res = 0

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

print(res)

Submission status: Accepted

Solution code:
IN=lambda:map(int,input().split())
N,W=IN()
INF=float("inf")
dp=[INF]*(1000*N)
dp.insert(0,0)
c=0
ans=0
for i in range(N):
    w,v=IN()
    for j in range((1000*N+1),-1,-1):
        if dp[j-v]!=INF:
            dp[j]=min(dp[j],dp[j-v]+w)
for i in range(1000*N+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 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 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):
        # TODO: use out keyward
        dp[i + 1][:v[i]] = 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]:])
    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 numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit
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):
        # TODO: use out keyward
        dp[i + 1][:v[i]] = 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]:])
    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:

N,W=map(int,input().split())
w=[]
v=[]
vmax=100010
nmax=110

for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
    
DP= [[10**12 for j in range(vmax)] for i in range(nmax)]

def chmin(a,b):
    if a>b:
        return b
    else:
        return a

DP[0][0]=0

for i in range(N):
    for j in range(vmax):
        if  j-v[i]>=0:
            DP[i+1][j]=chmin(DP[i][j],DP[i][j-v[i]]+w[i])
        else:
            DP[i+1][j]=DP[i][j]

ans=0            
for i in range(nmax):
    for j in range(vmax):
        if DP[i][j]<=W and ans<j:
            ans=j
print(ans)

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)
val_max=sum(v)
dp=[1000000001]*(val_max+1)
#value 0~maxのリスト。それぞれの値はそのvalueを生み出す最小weight
#リストが完成したら後ろから順に見て行き、初めてW以下になったvalueのindex番号がans
dp[0]=0
for i in range(N):
    for j in range(val_max,-1,-1):
        if dp[j]!=1000000001:
            if dp[j]+w[i]<=W:
                dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])

for i in range(val_max,-1,-1):
    if dp[i]!=1000000001:
        print(i)
        break

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
max_val = N * 1000 + 1
dp = [[float("inf") for _ in range(max_val)] for _ in range(N+1)]
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int,input().split())

dp[0][0] = 0
ans = 0
for i in range(1, N+1):
    for sum_v in range(max_val):
        if sum_v - v[i-1] >= 0: 
            dp[i][sum_v] = min(dp[i-1][sum_v], dp[i-1][sum_v - v[i-1]] + w[i-1])
        else:
            dp[i][sum_v] = dp[i-1][sum_v]
    for val, weight in enumerate(dp[i]):
        if weight <= W:
            ans = max(ans, val)

print(ans)

Submission status: Accepted

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

mv = 100100
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    
    weight.append(w)
    value.append(v)

INF = 1001001000100

dp = [[INF]*mv for i in range(110)]

dp[0][0] = 0

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

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])    
        
ans = 0
l = []
for sum_v in range(mv):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Accepted

Solution code:
# Knapsack 2
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
inf = float("inf")
dp = [[inf for i in range(100100)] for j in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for v in range(100100):
        if wv[n][1] <= v:
            dp[n+1][v] = min(dp[n][v - wv[n][1]] + wv[n][0], dp[n][v])
        else:
            dp[n+1][v] = dp[n][v]

for v in reversed(range(100100)):
    if dp[-1][v] > 0 and dp[-1][v] <= W:
        print(v)
        break

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)
V=sum(v)
INF=10**18
dp=[[INF for _ in range(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]=dp[i][j]
    else:dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
for i in range(V+1):
  if dp[n][i]<=W:ans=i
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, W, WV):
    MAX_VALUE = N * 10 ** 3
    weights = [INF] * (MAX_VALUE + 1)
    weights[0] = 0
    for i in range(N):
        next_weights = weights[:]
        weight, value = WV[i]
        for j in range(MAX_VALUE - value + 1):
            next_weights[j + value] = min(
                weights[j + value],
                weights[j] + weight)
        weights = next_weights
    for i in range(MAX_VALUE, -1, -1):
        if weights[i] <= W:
            return i


T1 = """
3 8
3 30
4 50
5 60
"""


def main():
    N, W = map(int, input().split())
    WV = [
        list(map(int, input().split()))
        for i in range(N)
    ]
    print(solve(N, W, WV))


def _test():
    """
    >>> as_input(T1)
    >>> main()
    90
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
# 横軸:重さ
def knapsack(W,weight,value):
    n = len(weight)#or len(value)
    dp = [[0]*(W+1) for _ in range(n+1)]
    # 初期化
    for j in range(W):
        dp[0][j] = 0
    for i in range(n):
        for j in range(W+1):
            if weight[i] <= j:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            else:
                dp[i+1][j] = dp[i][j]
    sol = dp[-1][-1]
    return dp,sol

# Wが大きい時
# 横軸:価値
# 価値が小さい必要がある
# https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-%E5%95%8F%E9%A1%8C---knapsack-2
def knapsack2(W,weight,value):
    n = len(weight)
    max_v = n*max(value)
    dp = [[0 for j in range(max_v)] for i in range(n)]
    
    for i in range(max_v):
        if i+1 > value[0]:
            dp[0][i] = float('inf')
        else:
            dp[0][i] = weight[0]
    
    for i in range(1,n):
        for j in range(max_v):
            if j+1 > value[i]:
                dp[i][j] = min(dp[i-1][j], weight[i]+dp[i-1][j-value[i]])
            else:
                dp[i][j] = min(dp[i-1][j], weight[i])
    for i in range(1,max_v+1)[::-1]:
        if dp[-1][i-1] <= W:
            sol = i
            break
    return dp,sol

N,W = map(int,input().split())
values, weights = [],[]
for _ in range(N):
    ｗ,ｖ = map(int,input().split())
    values.append(v)
    weights.append(w)

W = min(W,sum(weights))
dp,sol = knapsack2(W,weights,values)
print(sol)

Submission status: Accepted

Solution code:
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
maxValue=sum(values)
dp=[[float("inf")]*(maxValue+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=0

for i in range(1,n+1):
    for j in range(1,maxValue+1):
        if(values[i-1]<=j):
            dp[i][j]=min(weights[i-1]+dp[i-1][j- values[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]

ans=0
for i in range(maxValue+1):
    if(dp[n][i]<=capacity):
        ans=i
print(ans)

Submission status: Accepted

Solution code:
#dp[i][j]:iまでで価値jになるようにするときの品物の重さ
#答えはdp[N]をjが大きいものから見ていってWより小さいもの

INF = 10**15

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

dp = [[INF]*(100*1000+1) for i in range(N)]
dp[0][0]=0
dp[0][v[0]]=w[0]

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

for j in range(100*1000,-1,-1):
    if dp[N-1][j] <= W:
        print(j)
        exit()

Submission status: Accepted

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

INF = 10**12

# 各valueの値に対する最小のweightを記録する
dp = [[INF] * (10**6) for _ in range(N+1)]
dp[0][0] = 0

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

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def knapsack(wt,sm,W,n,V):
    K = [float('inf')]*(sm+1)
    K[0] = 0
    for i in range(n):
        for j in range(sm-V[i],-1,-1):
                K[j+V[i]] = min(K[j+V[i]],K[j]+W[i])
    #print(K)
    return max([i for i in range(sm+1) if K[i] <= wt])

n,wt = ip()
V,W = [0]*n,[0]*n
for i in range(n):
    w,v = ip()
    V[i] = v
    W[i] = w
ans = knapsack(wt,sum(V),W,n,V)
print(ans)

Submission status: Accepted

Solution code:
n,lw=map(int,input().split())
item=[]
for i in range(n):
    inp0,inp1=map(int,input().split())
    item.append((inp0,inp1))

dp=[10**13 for i in range(1002*n)]
dp[0]=0

for i in range(n):
    w=item[i][0]
    v=item[i][1]
    for q in range(1002*n-1,-1,-1):
        if q<=v:
            dp[q]=min(dp[q], w)
        else:
            dp[q]=min(dp[q], dp[q-v]+w)

for i in range(1002*n):
    if dp[i]>lw:
        print(i-1)
        break

Submission status: Accepted

Solution code:
import copy

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

min_w_per_v = [10**11] * (10**5+3)
min_w_per_v[0] = 0

for i in range(N):
    w, v = wv[i]
    tmp = copy.deepcopy(min_w_per_v)
    for j in range(v, len(min_w_per_v)):
        min_w_per_v[j] = min(tmp[j], tmp[j-v]+w)
        
for n, i in enumerate(min_w_per_v[::-1]):
    if i <= W:
        print(10**5+3-n-1)
        break

Submission status: Accepted

Solution code:
N ,W = map(int,input().split())
INF = float('inf')
w = [0] * N
v = [0] * N

for i in range(N):
    w[i],v[i] = map(int,input().split())
vsum = sum(v)
dp = [[INF] * (vsum + 1) for i in range(N + 1)]
dp[0][0] = 0

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

Submission status: Accepted

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

w = []
v = []

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

V = sum(v)

dp = [[W+1] * (V + 1) for i in range(N+1)]
#DP[i][j] = menor peso para obter o i-th item com valor j

dp[0][0] = 0

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

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

resp = 0

for i in range(V + 1):
    if dp[-1][i] <= W:
        resp = max(i,resp)

print(resp)

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 = 10**10

dp = [[INF for i in range(100010)] for j in range(n+1) ]

dp[0][0] = 0

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

for j in range(100010):
    if dp[n][100009-j] <= W:
        print(100009-j)
        break

Submission status: Accepted

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

V = sum(v)
dp = [[W + 1] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(V + 1):
        if v[i - 1] <= j:
            dp[i][j] = min(dp[i - 1][j], w[i - 1] + dp[i - 1][j - v[i - 1]])
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0
for i in range(V + 1):
    if dp[-1][i] <= W:
        a = i
        ans = max(a, ans)
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
lim = int(1e5) + 1
inf = float("inf")

# DP
dp = [[inf for _ in range(lim)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(lim):
        if wv[i][1] <= j:
            dp[i+1][j] = min(dp[i][j - wv[i][1]] + wv[i][0], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
        
for i in range(lim):
    if dp[N][i] <= W:
        ans = i
print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    INF=sys.maxsize
    Vmax=1000
    N,W=tuple(map(int,sys.stdin.readline().split()))
    V,w,v=N*Vmax,[0],[0]
    for _ in [0]*N:
        ww,vv=tuple(map(int,sys.stdin.readline().split()))
        w.append(ww)
        v.append(vv)
    dp=[[INF for _ in range(V+1)] for _ in range(N+1)]
    dp[0][0]=0
    for i in range(1,N+1):
        for j in range(V+1):
            dp[i][j]=min(dp[i][j],dp[i-1][j])
            if 0<=j-v[i]<=V:dp[i][j]=min(dp[i][j],dp[i-1][j-v[i]]+w[i])
    res=0
    for j in range(V+1):
        if dp[N][j]<=W:res=j
    print(res)
if __name__=='__main__':main()

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 18
V_MAX = 10 ** 3 * N

dp = np.full(V_MAX + 1, INF)
dp[0] = 0

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

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

Submission status: Accepted

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 18
V_MAX = 10 ** 3 * N

dp = np.full(V_MAX + 1, INF)
dp[0] = 0

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    dp = [defaultdict(int)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        keys = sorted(list(dp[i].keys()))
        new_dp = defaultdict(int)
        for key in keys:
            new_dp[key] = max([new_dp[key], dp[i][key]])
            new_w = key + w
            if new_w <= W:
                new_dp[new_w] = max([new_dp[new_w], dp[i][key] + v])

        max_value = 0
        for key in sorted(new_dp.keys()):
            if max_value > new_dp[key]:
                del new_dp[key]
            else:
                max_value = new_dp[key]

        dp.append(new_dp)
    print(max(dp[N].values()))


if __name__ == '__main__':
    main()