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:
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # ではなく...
    # dp[i][v] := 荷物0~iの中から荷物を選んで価値vを超える時の重さ合計の最小値
    # 初期値dp[0][v] = 0の重さ(もし0の価値がvを超えないならINF)
    V = 1000*100
    INF = float("inf")
    dp = [[INF]*(V+1) for i in range(N)]
    dp[0][0] = 0
    for i in range(N-1):
        for j in range(V+1):
            if j>=v[i+1]:
                # i+1番目を選ぶ
                dp[i+1][j] = min(dp[i+1][j], (dp[i][j-v[i+1]])+w[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    # dpのうちW以下であるものの価値の最大値
    for val in range(V,-1,-1):
        if dp[-1][val]<=W:
            print(val)
            break

main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

S = list(ST())
T = list(ST())
dp = FILL2(0,len(S)+1,len(T)+1)
for i in range(len(S)+1):
    for j in range(len(T)+1):
        if i+1<=len(S) and j+1<=len(T):
            if S[i]==T[j]:
                dp[i+1][j+1] = dp[i][j] + 1
        if i+1<=len(S):
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= len(T):
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])

l = dp[len(S)][len(T)]
i = len(S)
j = len(T)
ans = ''
while l > 0:
    if S[i-1]==T[j-1]:
        i -= 1
        j -= 1
        l -= 1
        ans = S[i]+ans
    else:
        if dp[i][j-1]==dp[i][j]:
            j -= 1
        else:
            i -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N, W = MI()
inp = LI2(N)
w = [0]+[inp[i][0] for i in range(N)]
v = [0]+[inp[i][1] for i in range(N)]
dp = FILL2(INF,N+1,1001)
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(1001):
        if j-v[i] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
for j in range(1001):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Wrong Answer

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

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


dp = [[float('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 >= wv[i][1]:
            dp[i+1][j] = min(dp[i+1][j],dp[i][j-wv[i][1]]+wv[i][0])
        else:
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
ans = 0
for i in range(v+1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
sumv=0
v,w=[],[]
m=10**9
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
    sumv+=b
dp=[m]*(sumv+1)
dp[0]=0
for i in range(n):
    for j in range(sumv,v[i]-1,-1):
        dp[j]=min(dp[j],dp[j-v[i]]+w[i])
ans=0

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect
N,W= map(int,input().split())
ans= [[float('inf') for e in range(10**5+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for j in range(0,v):
  ans[i+1][j]=min(ans[i][j],w)
 for j in range(v,10**5+1):
  ans[i+1][j]=min(ans[i][j],ans[i][j-v]+w)
print(bisect.bisect(ans[N],W))
print(ans[N])

Submission status: Wrong Answer

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

w_list.insert(0,0)#アイテム番号を1インデックスに変更.
v_list.insert(0,0)#アイテム番号を1インデックスに変更.

INF = 10**12
dp = [[INF]*(max(v_list)*N+1) for _ in range(N+1)]
dp[0][0] = 0

#print(dp)

for i in range(1,N+1):
  for j in range(max(v_list)*N+1):
    #print(i,j)
    if j - v_list[i-1] >= 0:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-v_list[i]] + w_list[i])
    else:
      dp[i][j] = dp[i-1][j]
  #print(dp)


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

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N,Max_W = map(int,input().split())
INF = np.inf

dp = np.full(10**3+1,0,dtype=np.int64)
 
for i in range(N):
    w,v = map(int,input().split())
    a = dp[:-v] + w
    b = dp[v:]
    m = np.maximum(a,b)
    dp[v:] = m
max_w = 0
max_v = 0
for v,i in enumerate(dp):
    if i <= Max_W and max_w < i:
        max_w = i
        max_v = v
print(max_v)

Submission status: Wrong Answer

Solution code:
a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0

#価値と重さのやつをリストにしてる
for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v

  wv_list.append([w, v])

#初期化
#とりあえず、全部最大になるように
inf=float('inf')
n_list = [[inf for i in range(max_value + 1)] for j in range(N)]

#
n_list[0][wv_list[0][1]] = wv_list[0][0]

for i in range(1, N):

  for j in range(max_value):

    s = j + wv_list[i][1]

    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
    n_list[i][wv_list[i][1]] = wv_list[i][0]

for i in range(1, max_value):

  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,weight=map(int,input().split())
    WV=[tuple(map(int,input().split())) for i in range(n)]
    dp=[[0]*(10**5+1) for _ in range(n+1)] #i番目までの品物について，価値の総和がjのときのナップザックの重さ
    for i in range(n):
        ni=i+1
        w,v=WV[ni-1]
        for j in range(10**5+1):
            if dp[i][j]+w<=weight and (j==0 or dp[i][j]>0):
                dp[i+1][j+v]=max(dp[i+1][j+v],dp[i][j]+w)
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
    for i in range(10**5,-1,-1):
        if dp[-1][i]>0:
            print(i)
            break

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
w=100005
dp=[[0]*(w+1) for i in range(n+1)]
wet=[]
val=[]
for i in range(n):
  we,va=map(int,input().split())
  wet.append((we,va))
wet.sort()
#print(wet)
for i in range(n+1):
  for j in range(w+1):
    if(i==0 or j==0):
      continue
    dp[i][j]=dp[i-1][j]
    if(wet[i-1][0]<=j):
      #print(wet[i][1],wet[i][0])
      dp[i][j]=max(dp[i][j],dp[i-1][j-wet[i-1][0]]+wet[i-1][1])
print(dp[n][w])

Submission status: Wrong Answer

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

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

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

  print("---")
  for i in range(sum(v)+1):
    print("w=",dp[N][i],"v=",i)
    if dp[N][i]>W: continue
    res=i

  print(res)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N, W = ri_()
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = ri_()
dp = [[INF] * (10 ** 3 + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(10 ** 3 + 1):
        if j - v[i] >= 0:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
        else:
            dp[i + 1][j] = dp[i][j]
ans = 0
for j in range(10 ** 3 + 1):
    if dp[N][j] <= W:
        ans = max(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
#from collections import deque
from pprint import pprint

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

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

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

dp[0][0] = 0

for i in range(1,N+1):
    for sum_v in range(0,1000*N):
        #print(i,sum_v)
        if sum_v >= wv[i-1][1]:
            dp[i][sum_v] = min(dp[i-1][sum_v],dp[i-1][sum_v-wv[i-1][1]] + wv[i-1][0])
        else:
            dp[i][sum_v] = min(dp[i-1][sum_v],dp[i][sum_v])

for j in range(1000*N-1,-1,-1):
    if dp[N][j] != float("inf") and dp[N][j] <= W:
        print(j)
        exit()

Submission status: Wrong Answer

Solution code:
#from collections import deque
from pprint import pprint

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

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

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

dp[0][0] = 0

for i in range(1,N+1):
    for sum_v in range(0,100*N):
        #print(i,sum_v)
        if sum_v >= wv[i-1][1]:
            dp[i][sum_v] = min(dp[i-1][sum_v],dp[i-1][sum_v-wv[i-1][1]] + wv[i-1][0])
        else:
            dp[i][sum_v] = min(dp[i-1][sum_v],dp[i][sum_v])

for j in range(100*N-1,-1,-1):
    if dp[N][j] != float("inf") and dp[N][j] <= W:
        print(j)
        exit()

Submission status: Wrong Answer

Solution code:
#from collections import deque
from pprint import pprint

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

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

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

dp[0][0] = 0

for i in range(1,N+1):
    for sum_v in range(0,100*N):
        #print(i,sum_v)
        if sum_v >= wv[i-1][1]:
            dp[i][sum_v] = min(dp[i-1][sum_v],dp[i-1][sum_v-wv[i-1][1]] + wv[i-1][0])
        else:
            dp[i][sum_v] = min(dp[i-1][sum_v],dp[i][sum_v])

for j in range(100*N-1,-1,-1):
    if dp[N][j] != float("inf") and dp[N][j] <= W:
        print(j)
        print(dp)
        exit()

Submission status: Wrong Answer

Solution code:
#from collections import deque
from pprint import pprint

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

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

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

dp[0][0] = 0

for i in range(1,N+1):
    for sum_v in range(0,100000):
        #print(i,sum_v)
        if sum_v >= wv[i-1][1]:
            dp[i][sum_v] = min(dp[i-1][sum_v],dp[i-1][sum_v-wv[i-1][1]] + wv[i-1][0])
        else:
            dp[i][sum_v] = min(dp[i-1][sum_v],dp[i][sum_v])

for j in range(99999,-1,-1):
    if dp[N][j] != float("inf") and dp[N][j] <= W:
        print(j)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, W = map(int, input().rstrip().split())
    item_list = []
    for _ in range(N):
        w, v = map(int, input().rstrip().split())
        item_list.append((w, v))

    # dp[i][v] = i番目まで見て価値vを達成できる最小の重さ
    dp = [[float("inf")] * (100001) for _ in range(N+1)]
    dp[0][0] = 0

    max_value = 0
    for i, item in enumerate(item_list, 1):
        for v in range(10001):
            # もし品物iが入れられる
            if dp[i-1][v] + item[0] <= W:
                dp[i][v+item[1]] = min(dp[i][v+item[1]], dp[i-1][v]+item[0])
                max_value = max(max_value, v+item[1])
            # 入れないパターン
            dp[i][v] = min(dp[i][v], dp[i-1][v])
    print(max_value)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
l=list(map(int,input().split()))
n=l[0]
w=l[1]
va=[0]*n
wa=[0]*n
for i in range(n):
        
    x=list(map(int,input().split()))
    wa[i]=x[0]
    va[i]=x[1]
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(1,n+1):
  for j in range(1,w+1):
    if wa[i-1]>j:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-wa[i-1]]+va[i-1])
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

def main():
    N, W = map(int, input().split())
    V = 10**3 * N
    
    dp = np.full(V, W+1)
    # print(len(dp))
    dp[0] = 0
    
    for _ in range(N):
        w, v = map(int, input().split())
        dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

    # print(dp)
    print(np.max(np.where(dp<=W)))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

def main():
    N, W = map(int, input().split())
    V = 10**3 * 100
    
    dp = np.full(V, W+100)
    # print(len(dp))
    dp[0] = 0
    
    for _ in range(N):
        w, v = map(int, input().split())
        dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

    # print(dp)
    print(np.max(np.where(dp<=W)))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

def main():
    N, W = map(int, input().split())
    V = 10**3 * 100
    
    dp = np.full(V, V+100)
    # print(len(dp))
    dp[0] = 0
    
    for _ in range(N):
        w, v = map(int, input().split())
        dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

    # print(dp)
    print(np.max(np.where(dp<=W)))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

# def main():
N, W = map(int, input().split())
V = 10**3 * 100

dp = np.full(V, np.inf)
# print(len(dp))
dp[0] = 0

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

# print(dp)
print(np.max(np.where(dp<=W)))
    
# if __name__ == "__main__":
#     main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

# def main():
N, W = map(int, input().split())
V = 10**3 * 100

dp = np.full(V, np.inf)
print(len(dp))
dp[0] = 0

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

# print(dp)
print(np.max(np.where(dp<=W)))
    
# if __name__ == "__main__":
#     main()

Submission status: Wrong Answer

Solution code:
n,W = map(int,input().split())
w = []
v = []
for _ in range(n):
    weight,value = map(int,input().split())
    w.append(weight)
    v.append(value)
INF =float("inf")
order = 150
dp = [[INF] * order for _ in range(n+1)] #dp[i+1][value] i番目まで価値がvalue以上になるように選んだ時の重さの最小値
dp[0] =[-INF] * order
dp[0][0]=0
for i in range(n):
    for value in range(order):
        if value - v[i] >= 0:
            dp[i+1][value] = min(dp[i+1][value], dp[i][value-v[i]] + w[i])
        if dp[i][value] != -INF:
            dp[i+1][value] = min(dp[i+1][value],dp[i][value])
ans = 0
for value in range(order):
    if 0<=dp[n][value]<= W:
        ans = max(ans,value)

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

def main():
    N, W = map(int, input().split())
    V = 10**3 * 100

    dp = np.full(V, np.inf)
    dp[0] = 0
    
    for _ in range(N):
        w, v = map(int, input().split())
        dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

    # print(dp)
    print(np.max(np.where(dp<=W)))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())

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

dp = np.full(10**4, W+1) #横軸を価値の値に変換する
dp[0] = 0

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N, W = map(int, input().split())

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

dp = np.full(10**5, W+1) #横軸を価値の値に変換する
dp[0] = 0

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N , W = map(int,input().split())
dp = np.full(N * 1000 + 1,W + 1)
dp[0] = 0

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
# knapsack with N <= 100 and W <= 10**9
n, W = map(int, input().split())
# dp[i][j] = w' means upto i elements j such that you get min weight  w'
# then your solution will be j where w' = W
dp = np.full(fill_value=10**15+1,shape=(n,10**3+1), dtype='int64')
w, v = map(int, input().split())
dp[0,v] = w
dp[0,0] = 0
for i in range(1,n):
    w, v = map(int, input().split())
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.fmin(dp[i-1, v:], dp[i-1,:1001-v]+w)
ans = 0
for j in range(1001):
    if dp[n-1][j] <= W:
        ans = max(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
# knapsack with N <= 100 and W <= 10**9
n, W = map(int, input().split())
# dp[i][j] = w' means upto i elements j such that you get min weight  w'
# then your solution will be j where w' = W
dp = np.full(fill_value=10**9+1,shape=(n,10**3+1), dtype='int64')
w, v = map(int, input().split())
dp[0,:v+1] = w
dp[0,0] = 0
for i in range(1,n):
    w, v = map(int, input().split())
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.fmin(dp[i-1, v:], dp[i-1,:1001-v]+w)
ans = 0
for j in range(1001):
    if dp[n-1][j] <= W:
        ans = max(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
# knapsack with N <= 100 and W <= 10**9
n, W = map(int, input().split())
# dp[i][j] = w' means upto i elements j such that you get min weight  w'
# then your solution will be j where w' = W
dp = np.full(fill_value=10**9+1,shape=(n,10**3+1), dtype='int64')
w, v = map(int, input().split())
dp[0,v] = w
dp[0,0] = 0
for i in range(1,n):
    w, v = map(int, input().split())
    dp[i, :v] = dp[i-1, :v]
    dp[i, v:] = np.fmin(dp[i-1, v:], dp[i-1,:1001-v]+w)
ans = 0
for j in range(1001):
    if dp[n-1][j] <= W:
        ans = max(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    N, W = map(int, input().split())
    weight, value = [0] * N, [0] * N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())

    # 添字を付け加える系DP．ナップサックとかはこの一種
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#%E9%A1%9E%E9%A1%8C-3

    INF = 10**20  # INF+INFを計算してもオーバーフローしない範囲で大きく

    I = N
    # dpテーブル dp[i][j]:=i番目以下で価値j以上の時の，重さの最小値
    J = sum(value)
    dp = [[INF]*(J+1) for _ in range(I+1)]
    # 初期条件
    dp[0][0] = 0
    # ループ
    for i in range(1, I+1):
        for j in range(J+1):
            if j-value[i-1] >= 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j-value[i-1]]+weight[i-1])
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
    ans = 0
    for j in range(J+1):
        if dp[I][j] <= W:
            ans = j
    print(ans)

resolve()

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
for _ in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
V=sum(v)

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

for i in range(N): #i番目の荷物を拾うかどうか
    for j in range(V+1): #価値jを超える重量の最小値
        dp[i+1][j]=min(dp[i][j],dp[i][max(0,j-v[i])]+w[i])
        if dp[i+1][j]<=W:
            ans=max(ans,j)
        
print(ans)

Submission status: Wrong Answer

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

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

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

    dp[0][0] = 0
    # i種類目までの荷物を見る
    for i in range(N):
        # その荷物を価値がjになるように持つ
        for j in range(V + 1):
            w, v = WV[i]

            if v <= j:
                # 荷物iを選ぶ場合
                dp[i+1][j] = min(dp[i+1][j], dp[i][j-v] + w)
            # 荷物iを選ばない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

    V = 20
    inf = float("inf")
    dp = [[inf] * (V+1) for _ in range(N+1)]

    dp[0][0] = 0
    # i種類目までの荷物を見る
    for i in range(N):
        # その荷物を価値がjになるように持つ
        for j in range(V + 1):
            w, v = WV[i]

            if v <= j:
                # 荷物iを選ぶ場合
                dp[i+1][j] = min(dp[i+1][j], dp[i][j-v] + w)
            # 荷物iを選ばない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
w=[0]*N
v=[0]*N
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
V=sum(v)

dp=[[float("inf") ]*(V+1) for _ in range(110)]
dp[0][0]=0

for i in range(0,N):
    for j in range(V+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+1][j],dp[i][j])


ans=0

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

print(ans)

Submission status: Wrong Answer

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

dp=[[float("inf") for i in range(10100)] for _ in range(110)]
dp[0][0]=0

for i in range(0,N):
    for j in range(0,10100):
        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+1][j],dp[i][j])


ans=0

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

print(ans)

Submission status: Wrong Answer

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

dp=[[float("inf") for i in range(10100)] for _ in range(110)]
dp[0][0]=0

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

ans=0

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

print(ans)

Submission status: Wrong Answer

Solution code:
inf = 2**60
'''
def table(size, init): #配列生成
  x = len(size)
  l = [init for i in range(size[x-1])]
  for i in range(x-1):
    l = [l for k in range(size[x-2-i])]
  return l
'''

n, W = map(int, input().split())
w, v = [[0]*n for i in range(2)]
for i in range(n):
  w[i], v[i] = map(int, input().split())

dp = [[-1] * (100011) for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
  for j in range(100010):
    if dp[i][j] != -1:
      dp[i+1][j] = max(dp[i][j], dp[i+1][j])
      if dp[i][j]+w[i] <= W:
        dp[i+1][j+v[i]] = max(dp[i][j] + w[i], dp[i+1][j+v[i]])

for i in range(100010):
  if dp[n][100010-i] != -1:
    print(100010-i)
    break

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
w=[]
v=[]
for _ in range(N):
    ww,vv=map(int,input().split())
    w.append(ww)
    v.append(vv)
INF=float("inf")
max_v=max(v)*N
dp=[[INF for i in range(max_v+1)] for j in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(max_v):
        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+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:
N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)

maxValue = N*max(value)
dp = [[0 for i in range(maxValue+1)] for j in range(N+1)]
for i in range(maxValue+1):
    dp[0][i] = float("inf")

dp[0][0] = 0
dp[0][value[0]] = weight[0]

for i in range(1,N+1):
    for v in range(maxValue+1):
        dp[i][v] = dp[i-1][v]
        if value[i-1] > v: continue;
        dp[i][v] = min(dp[i][v],weight[i-1] + dp[i-1][v-value[i-1]])
ans = 0
for x in range(maxValue+1):
    if dp[N][x] <= W:
        ans = x
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
    
maxValue = N*1000
dp = [[None for i in range(maxValue+1)] for j in range(N+1)]
for i in range(maxValue+1):
    dp[0][i] = float("inf")
    
dp[0][0] = 0
dp[0][value[0]] = weight[0]

for i in range(1,N+1):
    for v in range(maxValue+1):
        dp[i][v] = dp[i-1][v]
        if value[i-1] > v: continue;
        dp[i][v] = min(dp[i][v],weight[i-1] + dp[i-1][v-value[i-1]])
ans = 0
for x in range(maxValue+1):
    if dp[N][x] <= W:
        ans = x
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
weight = []
value = []
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
maxValue = N*1000
dp = [[0 for i in range(maxValue+1)] for j in range(N+1)]
for i in range(maxValue+1):
    dp[0][i] = float("inf")
dp[0][0] = 0
dp[0][value[0]] = weight[0]
for i in range(1,N+1):
    op2 = float("inf")
    for v in range(maxValue+1):
        dp[i][v] = dp[i-1][v]
        if value[i-1] > v: continue;
        dp[i][v] = min(dp[i][v],weight[i-1] + dp[i-1][v-value[i-1]])
ans = 0
for x in range(maxValue+1):
    if dp[N][x] <= W:
        ans = x
print(ans)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
Weight = [0]
Value = [0]
ans = 0
for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    Value.append(v)
VS = sum(Value)
DP = [[float('inf')] * (VS + 1) for i in range(N + 1)]

for n in range(N + 1):
    for val in range(VS + 1):
        if val == 0:
            DP[n][val] = 0
        elif Value[n] > val:
            DP[n][val] = DP[n - 1][val]
        else:
            DP[n][val] = min(DP[n - 1][val], DP[n - 1][val - Value[n]] + Weight[n])
            if (n == N) and (DP[n][val] <= W):
                ans = max(ans, val)
print(DP[N])
print(ans)

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
array = [[int(x) for x in input().split()] for x in range(n)]
v_max = 10000
dp = [[float("inf") for x in range(v_max+1)] for x in range(n+1)]
for v in range(1,v_max+1):
    for i in range(1,n+1):
        if(array[i-1][1]>=v):
            dp[i][v] = min(dp[i-1][v],array[i-1][0])
        else:
            dp[i][v] = min(dp[i-1][v],array[i-1][0]+dp[i-1][v-array[i-1][1]])
ans = 0
for v in range(v_max+1):
    if(dp[n][v] <= w):
        ans = v
print(ans)