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: Wrong Answer

Solution code:
N,W = list(map(int,input().split()))
wv = [list(map(int,input().split())) for i in range(N)]
w = [0]+[wv[i][0] for i in range(N)] #荷物無し、1番荷物～N番荷物の重さリスト
v = [0]+[wv[i][1] for i in range(N)] #荷物無し、1番荷物～N番荷物の価値リスト
V = sum(v)

# DP用の行列（今回は最小値を求めるためinfで埋める）
dp = [[float('INF') for i in range(V+1)] for i in range(N+1)]
dp[0][0] = 0

# 「1番荷物(i=1)」......「N番荷物(i=N)」から何番目まで使うかの場合分け
# 価値合計が「0」「1」......「V」だった場合の場合分け
for i in range(1,N+1):
    for j in range(V+1):
        if v[i] > j: # もしi番目の重さが仮の合計価値(j)を超えている場合
            dp[i][j] = dp[i-1][j]
        else: # 合計価値の残り「j-v[i]」をDPリストから参照してDP更新
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
print(dp)

# dp[N][j]をjが大きいところから見ていって、初めてW以下になったときのjが答え
ans = V
while dp[N][ans] > W:
    ans -= 1

print(ans)

Submission status: Wrong Answer

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = minimum weight required to get value exactly i, and by using elements 1,...,j

dp = [[float('inf') for i in range(N+1)] for j in range(1000 * N + 1)]

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v

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

highest_value = 0
for value in range(1000 * N + 1):
    for item in range(1,N+1):
        
        # Case: dont include item
        dp[value][item] = min(dp[value][item],
                              dp[value][item-1])

        # Case: include item
        if value - values[item-1] < 0: continue
        dp[value][item] = min(dp[value][item], dp[value - values[item-1]][item-1] + weights[item-1])

    if float('inf') > dp[value][-1] <= W:
        highest_value = max(value, highest_value)
    if float('inf') > dp[value][-1]  > W:
        print(highest_value)
        break

Submission status: Wrong Answer

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

for i in range(N*1000)[::-1]:
  if dp[i]>0 and dp[i]<=W:
    print(i)
    break
else:
  print(0)

Submission status: Wrong Answer

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

for i in range(N*1000)[::-1]:
  if dp[i]>0 and dp[i]<=W:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

N, W = na()
maxV = 10 ** 5
dp = [[10**9+7] * (maxV+1) for i in range(N+1)]  # dp[i][v] i番目までで価値がvの時の重さの合計の最小値
dp[0][0] = 0
for i in range(1, N+1):
    wi, vi = na()
    for v in range(1, maxV+1):
        if v - vi >= 0:
            dp[i][v] = min(dp[i - 1][v], dp[i - 1][v - vi] + wi)
        else:
            dp[i][v] = dp[i - 1][v]
ans = -1
for i in range(1, N + 1):
    for v in range(1, maxV+1):
        if dp[i][v] <= W:
            ans = max(ans, v)
print(ans)

Submission status: Wrong Answer

Solution code:
n,w_max = map(int,input().split())
w = [0]
v = [0]

for _ in range(n):
    W,V = map(int,input().split())
    w.append(W)
    v.append(V)
v_sum = sum(v)
lrg = 10*12
dp = [[lrg]*(v_sum+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 u in range(v_sum+1):
        if u>=v[i]:
            dp[i][u] = min(dp[i-1][u-v[i]]+w[i],dp[i-1][u])
        else:###
            dp[i][u] = min(w[i],dp[i-1][u])

ans = []
for u in range(v_sum+1):
    if dp[n][u] <= w_max:
        ans.append(u)
#print(*dp[n])
print(max(ans))

Submission status: Wrong Answer

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = minimum weight required to get at least value i, and by using elements 1,...,j

dp = [[float('inf') for i in range(N+1)] for j in range(1001)]

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v

for i in range(N+1):
    dp[0][i] = 0
        
for value in range(1001):
    for item in range(1,N+1):
        
        # Case: dont include item
        dp[value][item] = min(dp[value][item],
                              dp[value][item-1])

        # Case: include item
        if value - values[item-1] < 0: continue
        dp[value][item] = min([dp[value][item]] +
                              [dp[v][item-1] + weights[item-1]
                               for v in range(value-values[item-1],value+1)])

highest_value = 0 
for value in range(1001):
    for item in range(1, N+1):
        if dp[value][item] <= W:
            highest_value = max(highest_value, value)

print(highest_value)

Submission status: Wrong Answer

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = minimum weight required to get value i, and by using elements 1,...,j

dp = [[float('inf') for i in range(N+1)] for j in range(1001)]

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v

for i in range(N+1):
    dp[0][i] = 0
        
for value in range(1001):
    for item in range(1,N+1):
        
        # Case: dont include item
        dp[value][item] = min(dp[value][item],
                              dp[value][item-1])

        # Case: include item
        if value - values[item-1] < 0: continue
        dp[value][item] = min(dp[value][item],
                              dp[value - values[item-1]][item-1] + weights[item-1])

highest_value = 0 
for value in range(1001):
    for item in range(1, N+1):
        if dp[value][item] <= W:
            highest_value = max(highest_value, value)

print(highest_value)

Submission status: Wrong Answer

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

max_v=0
for i in range(N):
    max_v+=wv[i][1]

dp=[[99999999999]*(max_v+1) for _ in range(N)]

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

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

Submission status: Wrong Answer

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

# dp[i][v] := min w
INF = 10**10
dp = [[0,] + [INF,] * (10**3)]

for w,v in mX:
    nDp = [min(dp[-1][t], dp[-1][t-v]+w)
           if t-v >= 0 else dp[-1][t]
           for t in range(10**3+1)]
    dp.append(nDp)

#print(dp[-1][8:14])

minW = dp[-1][::-1]
for i,w in enumerate(minW):
    if w <= W:
        print(10**3 - i)
        break

Submission status: Wrong Answer

Solution code:
max_v = 100000
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[float('inf') for _ in range(max_v+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
  for j in range(max_v):
    if j - wv[i][1] >= 0:
      dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
    else:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

print(ans)

Submission status: Wrong Answer

Solution code:
max_v = 1000
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[float('inf') for _ in range(max_v+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
  for j in range(max_v):
    if j - wv[i][1] >= 0:
      dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
    else:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
weights=[[0]*(10**5+1) for i in range(n+1)]
for i in range(n):
    weights[i+1][wv[i][1]]=max(weights[i+1][wv[i][1]], wv[i][0])
    for j in range(10**5+1):
        if weights[i][j]!=0:
            weights[i+1][j]=max(weights[i+1][j], weights[i][j])
            if weights[i][j]+wv[i][0]<=w:
                weights[i+1][j+wv[i][1]]=max(weights[i+1][j+wv[i][1]], weights[i][j]+wv[i][0])

for i in range(10**5+1):
    if weights[-1][10**5-i]!=0:
        print(10**5-i)
        quit()

Submission status: Wrong Answer

Solution code:
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)
dp = [[10**50 for i in range(sum(v)+1)]for j in range(N+1)]
dp[0][v[0]] = m[0]
for i in range(N):
    for j in range(sum(v)+1):
        if j == 0:
            dp[i][j] = 0
        if dp[i][j] != 10**50 and j+v[i] <= sum(v):
            dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break

Submission status: Wrong Answer

Solution code:
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)
dp = [[10**50 for i in range(sum(v)+1)]for j in range(N+1)]
dp[0][v[0]] = m[0]
for i in range(N):
    for j in range(sum(v)):
        if j == 0:
            dp[i][j] = 0
        if dp[i][j] != 10**50 and j+v[i] <= sum(v):
            dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break

Submission status: Wrong Answer

Solution code:
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)
dp = [[1000 for i in range(sum(v)+1)]for j in range(N+1)]
dp[0][v[0]] = m[0]
for i in range(N):
    for j in range(sum(v)):
        if j == 0:
            dp[i][j] = 0
        if dp[i][j] != 1000 and j+v[i] <= sum(v):
            dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


# https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-問題---knapsack-2


# N個の荷物、ナップザックの容量はW
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

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

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする

# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = 100000
#dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Wrong Answer

Solution code:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


# https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-問題---knapsack-2


# N個の荷物、ナップザックの容量はW
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

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

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする

# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = 10000
#dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


# https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-問題---knapsack-2


# N個の荷物、ナップザックの容量はW
N, W = map(int, input().split())
w = [0] * N
v = [0] * N

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

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする

# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = 1000
#dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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())
V=sum(v)
dp=[[0]*(V+1) for _ in range(N)]
dp[0] = [w[0] if i<=v[0] else V*10 for i in range(V+1)]
dp[0][0]=0
for i in range(1,N):
    for vv in range(V+1):
        if vv>=v[i]:
            dp[i][vv]=min(dp[i-1][vv],dp[i-1][vv-v[i]]+w[i])
        else:
            dp[i][vv]=dp[i-1][vv]

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

Submission status: Wrong Answer

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())

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

ans=0
for i in range(V+1):
    if dp[-1][i]>ans and dp[-1][i]<=W:
        ans=dp[-1][i]
        j=i
print(j)

Submission status: Wrong Answer

Solution code:
#d
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=sum(v)
dp=[[0]*(V+1) for _ in range(N)]
dp[0] = [w[0] if i<=v[0] else V*10 for i in range(V+1)]
dp[0][0]=0
for i in range(1,N):
    for vv in range(V+1):
        if vv>=v[i]:
            dp[i][vv]=min(dp[i-1][vv],dp[i-1][vv-v[i]]+w[i])
        else:
            dp[i][vv]=dp[i-1][vv]
print( max( j for j in dp[-1] if j <=W ) )

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

[n,w] = list(map(int,input().split()))
vl = []
wl = []
maxval = 1000*n
INF = 10**9*n
dp = [[INF for j in range(n+1)] for val in range(maxval+1)]
for item in range(n+1):
    dp[0][item] = 0
for _ in range(n):
    [t1,t2] = list(map(int,input().split()))
    wl.append(t1)
    vl.append(t2)
vmax=-1
for val in range(1,maxval+1):
    for item in range(1,item+1):
        if val < vl[item-1]:
            dp[val][item] = dp[val][item-1]
        else:
            dp[val][item] = min(dp[val-vl[item-1]][item-1]+wl[item-1], dp[val][item-1])

        if dp[val][item] <= w:
            vmax = val
print(vmax)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

[n,w] = list(map(int,input().split()))
vl = []
wl = []
maxval = 1000*n
INF = 10**9*n
dp = [[INF for j in range(n+1)] for val in range(maxval+1)]
for item in range(n+1):
    dp[0][item] = 0
for _ in range(n):
    [t1,t2] = list(map(int,input().split()))
    wl.append(t1)
    vl.append(t2)
vmax=-1
for val in range(1,maxval+1):
    for item in range(1,item+1):
        dp[val][item] = min(dp[val-vl[item-1]][item-1]+wl[item-1], dp[val][item-1])

for val in range(maxval,-1,-1):
    t = list(filter(lambda x: x<=w,dp[val]))
    if len(t) > 0:
        vmax = val
        break
print(vmax)

Submission status: Wrong Answer

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

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

for i in range(1, N+1):
    for v in range(0, 10002):
        weight = WV[i-1][0]
        value = WV[i-1][1]
        dp[i][v] = min(dp[i-1][v], dp[i-1][v-value]+weight)
res = 0
for v, w in enumerate(dp[-1]):
    if w <= W: res = v

print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
"""解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-%E5%95%8F%E9%A1%8C---knapsack-2

・まず制約を見る
Wの最大値が10**9なので、dp[i][w] みたいにすると、間に合わない

N=100, viの最大値が10**3 なので、N+max(vi) = 10**5 なので、viを使うといけそう

dp[i][v] := i番目までを選んだ時の、価値がv以上のときの、重さの総和の最小値


・DPテーブル
      i   =   0      1      2      3      4      5
例: (w,v) = (2,3), (1,2), (3,6), (2,1), (1,3), (5,85)

i/v | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ...
----------------------------------------------------------------------
0   | 0 | 2 | 2 | 2 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞  | ∞  | ∞  | ∞  | ... 
1   | 0 | 1 | 1 | 2 | 3 | 3 | ∞ | ∞ | ∞ | ∞ | ∞  | ∞  | ∞  | ∞  | ...
2   | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 4 | 4 | 5 | 6  | 6  | ∞  | ∞  | ...
3   |
4   |
5   |

"""

def solve():
    N, W = list(map(int, input().split()))
    Ws, Vs = [], []
    for i in range(N):
        w, v = list(map(int, input().split()))
        Ws.append(w)
        Vs.append(v)
    
    # dp[i][v] := i番目までを選んだ時の、価値がv以上のときの、重さの総和の最小値
    dp = [[float("inf") for _ in range(0, 10**5+1)] for __ in range(0, N)]

    # 初期値
    for i in range(0, N):
        dp[i][0] = 0 # 価値0の重さの最小値は0
    
    for v in range(0, 10**5+1):
        if v <= Vs[0]:
            dp[0][v] = Ws[0]
    
    # dpを埋める
    for i in range(1, N):
        for v in range(0, 10**5+1):
            if v-Vs[i] >= 0:
                dp[i][v] = min(dp[i-1][v], dp[i-1][v-Vs[i]]+Ws[i])
            else:
                dp[i][v] = min(dp[i-1][v], Ws[i])

    # 答えを出す
    for v in range(10**5, -1, -1):
        if dp[N-1][v] <= W:
            ans = v
            break
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys

# 商品の数，ナップサックの許容重量
n, c = list(map(int, input().split()))

# 制約より起こり得る商品価値の総和の最大値+余分
M = (10 * 3) * n + 10

# n=1のときの例外処理
if n == 1:
    w, v = map(int, input().split())
    ans = v if c >= w else 0
    print(ans)
    sys.exit()

# DPリスト
dp = [[float("inf")] * M for i in range(n)]
dp[-1][0] = 0

for i in range(n):
    w, v = map(int, input().split())
    # 配るDP
    for j in reversed(range(M)):
        dp[i][j] = dp[i - 1][j]
        if j + v < M:
            dp[i][j + v] = min(dp[i - 1][j + v], dp[i - 1][j] + w)

ans = 0
for i in range(M):
    if dp[-1][i] <= c:
        ans = max(i, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

M = (10 * 3) * n + 10

if n == 1:
    ans = wv[0][1] if w >= wv[0][0] else 0
    print(ans)
    sys.exit()


dp = [[float("inf")] * M for i in range(n)]
dp[-1][0] = 0

for i in range(n):
    for j in range(M):
        weights = [dp[i - 1][j]]
        if j - wv[i][1] >= 0:
            weights.append(dp[i - 1][j - wv[i][1]] + wv[i][0])

        dp[i][j] = min(weights)

ans = 0
for i in range(M):
    if dp[-1][i] <= w:
        ans = max(i, ans)


print(ans)

Submission status: Wrong Answer

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

M = (10 * 3) * n + 10

dp = [[float("inf")] * M for i in range(n)]

for i in range(n):
    for j in range(1, M):
        weights = [dp[i - 1][j]]
        if j - wv[i][1] <= 0:
            weights.append(wv[i][0])
        if j - wv[i][1] >= 0:
            weights.append(dp[i - 1][j - wv[i][1]] + wv[i][0])

        dp[i][j] = min(weights)

for i, x in enumerate(dp[-1][1:-1]):
    if x > w:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
import numpy as np

n, W = map(int, input().split())
w, v = [],[]
for i in range(n):
    temp = list(map(int, input().split()))
    w.append(temp[0])
    v.append(temp[1])

table = np.full(sum(v), np.inf)
table[0] = 0

for i in range(n):
    l = table[:-v[i]]
    r = table[v[i]:]
    np.minimum(l + w[i], r, out = r)
    
print(np.max(np.where(table <= W)))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
items = [None] * N
for n in range(N):
    w, v = map(int, input().split())
    items[n] = (w, v)
V = 10 ** 3 + 1

dp = [[10 ** 9 + 1] * (V) for _ in range(N + 1)]
dp[0][0] = 0

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

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

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
items = [None] * N
for n in range(N):
    w, v = map(int, input().split())
    items[n] = (w, v)
V = 10 ** 3 + 1

dp = [[W + 1] * (V) for _ in range(N + 1)]
dp[0][0] = 0

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

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

Submission status: Wrong Answer

Solution code:
N,W,*l = map(int,open(0).read().split())
wl = l[::2]
vl = l[1::2]
M = N*max(vl)
INF = float("inf")
dp = [[INF]*M for _ in range(N+1)]
dp[0][0] = 0

# minimum weight with value == j
for i in range(N):
	w,v = wl[i],vl[i]
	for j in range(M):
		if j >= v:
			dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
		else:
			dp[i+1][j] = dp[i][j]
		
# maximum value provided dp[N][value] <= W
ans=0
for val,wei in enumerate(dp[N]):
	if wei <= W:
		ans = max(ans,val)
print(ans)

Submission status: Wrong Answer

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

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

dp = [[10**10 for i in range(2*10**3)] for j in range(2*N)]
dp[0][0] = 0

for i in range(N):
    for j in range(10**3):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-wv[i][1]]+wv[i][0])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(10**3):
    if dp[N][i] <= W: 
        ans = i
print(ans)

Submission status: Wrong Answer

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

max_v = 10005

dp = [[float('inf') for i in range(max_v)] for j in range(n + 1)]

dp[0][0] = 0
for i in range(n):
    for sum_v in range(max_v):
        if sum_v - item[i][1] >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - item[i][1]] + item[i][0])
        dp[i + 1][sum_v] = min((dp[i + 1][sum_v], dp[i][sum_v]))

ans = 0
for sum_v in range(max_v):
    if dp[-1][sum_v] <= w:
        ans = sum_v
print(ans)

Submission status: Wrong Answer

Solution code:
def number():
    return int(input())


def space():
    return list(map(int, input().split()))


def seq_space(n):
    return [list(map(int, input().split())) for _ in range(n)]


N, W = space()
WV = seq_space(N)

V = 10**5

DP = [[float('inf')] * V for _ in range(N)]

w, v = WV[0]
DP[0][v] = w
for i in range(1, N):
    w, v = WV[i]
    for j in range(0, V):
        if j < v:
            DP[i][j] = DP[i-1][j]
        elif j == v:
            DP[i][j] = min(DP[i-1][j], w)
        else:
            DP[i][j] = min(DP[i-1][j-v] + w, DP[i-1][j])

value = -1

for i in range(len(DP)):
    for j in range(V):
        if DP[i][j] > W:
            continue
        value = max(value, j)

print(value)

Submission status: Wrong Answer

Solution code:
def number():
    return int(input())


def space():
    return list(map(int, input().split()))


def seq_space(n):
    return [list(map(int, input().split())) for _ in range(n)]


N, W = space()
WV = seq_space(N)

V = 10**5

DP = [[float('inf')] * V for _ in range(N)]

w, v = WV[0]
DP[0][v] = w

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

value = -1

for i in range(len(DP)):
    for j in range(V):
        if DP[i][j] > W:
            continue
        value = max(value, j)

print(value)

Submission status: Wrong Answer

Solution code:
def number():
    return int(input())


def space():
    return list(map(int, input().split()))


def seq_space(n):
    return [list(map(int, input().split())) for _ in range(n)]


N, W = space()
WV = seq_space(N)

V = 10**5

DP = [[float('inf')] * V for _ in range(N)]

w, v = WV[0]
DP[0][v] = w

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

value = -1

for i in range(len(DP)):
    for j in range(V):
        if DP[i][j] > W:
            continue
        value = max(value, j)

print(value)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
wv=[]
m=1
for i in range(n):
    p=[int(j) for j in input().split()]
    wv.append(p)
    m+=p[1]

dp=[10**3 for i in range(m)]
dp[0]=0

for i in range(n):
    w,v=wv[i][0],wv[i][1]
    for j in range(m):
        if dp[-1-j]!=10**100:
            dp[-1-j+v]=min(dp[-1-j+v],dp[-1-j]+w)

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

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
wv=[]
dp=[10**100 for i in range(n*10**3)]
dp[0]=0
for i in range(n):
    p=[int(j) for j in input().split()]
    wv.append(p)

for i in range(n):
    w,v=wv[i][0],wv[i][1]
    for j in range(n*10**3):
        if dp[-1-j]!=10**100:
            dp[-1-j+v]=min(dp[-1-j+v],dp[-1-j]+w)

ans=0
for i in range(n*10**3):
    if dp[i]<=W:
        ans=i
print(ans)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
u,m=[list(map(int,input().split()))for _ in range(n)],0
for i in u:m+=i[1]
dp=[[0]+[10000001]*m]+[[0]*(m+1)for _ in range(n)]
h=0
for i in range(1,n+1):
  a,b=map(int,u[i-1])
  for j in range(1,m+1):
    if j>=b:dp[i][j]=min(dp[i-1][j],dp[i-1][j-b]+a)
    else:dp[i][j]=dp[i-1][j]
a=0
for i in range(m+1):
  if dp[-1][i]<=w:a=max(a,i)
print(a)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
u,m=[list(map(int,input().split()))for _ in range(n)],0
for i in u:m+=i[1]
dp=[[0]+[100001]*m]+[[0]*(m+1)for _ in range(n)]
h=0
for i in range(1,n+1):
  a,b=map(int,u[i-1])
  for j in range(1,m+1):
    if j>=b:dp[i][j]=min(dp[i-1][j],dp[i-1][j-b]+a)
    else:dp[i][j]=dp[i-1][j]
a=0
for i in range(m+1):
  if dp[-1][i]<=w:a=max(a,i)
print(a)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP=[float('inf')]*(N*101)
DP[0] = 0
for w,v in wv:
    for i in range(N*101-1,v-1,-1):
        DP[i] = min(DP[i-v]+w,DP[i])
ans = 0

for i in range(len(DP)):
    if DP[i] <= W:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP=[float('inf')]*(N*100+1)
DP[0] = 0
for w,v in wv:
    for i in range(N*100,v-1,-1):
        DP[i] = min(DP[i-v]+w,DP[i])
ans = 0

for i in range(len(DP)):
    if DP[i] <= W:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[float('inf')]*(N*100+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*100+1):
        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(len(DP[-1])-1,-1,-1):
    if DP[-1][i] <= W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[float('inf')]*(N*100+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*100+1):
        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(N*100,-1,-1):
    if DP[-1][i] <= W:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
dp = [[0,0]]
for w,v in wv:
    hoge=[]
    for vd,wd in dp:
        if w+wd<W:
            hoge.append([v+vd,w+wd])
    dp =  dp + hoge
print(max(dp)[0])