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=map(int,input().split())
inf=float('inf')

dp=[inf]*100
m=0



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

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

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

dp[0][0]=0

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

for i in reversed(range(N*1000+1)):
    if dp[i][N]<=W:
        print(i)
        break

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())
    
dp=[[10**10 for i in range(N+1)] for j in range(100*1000+1)] 
for i in range(1,100001):
    if i<=v[0]:
        dp[i][1]=w[0]
    else:
        break
for i in range(2,N+1):
    for j in range(1,100001):
        #print(i,j)
        if j-v[i-1]>=0:
            dp[j][i]=min(dp[j][i-1],dp[j-v[i-1]][i-1]+w[i-1])
        else:
            dp[j][i]=dp[j][i-1]

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
wt,values=[],[]
for _ in range(n):
    w,val=map(int,input().split())
    wt.append(w)
    values.append(val)
# since for an i we only need look at i-1 row hence 1D array can be used to memoise
# inner loop goes backward since we can take an item more then once (bounded Knapsack)

max_profit=max(values)*n # not neccessary we can take it n*10^3
dp=[float('inf')]*(max_profit+1)
dp[0]=0
for i in range(n):
    for j in range(max_profit,values[i]-1):
        dp[j]=min(dp[j],wt[i]+dp[j-values[i]])
ans=0
for i in range(1,max_profit+1):
    if dp[i]<=W:
        ans=i
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
wi=[]
vi=[]

for i in range(n):
  a,b=map(int,input().split())
  wi+=[a]
  vi+=[b]
  
vvv=sum(vi)

dp=[0]+[None]*vvv
dp[vvv]=sum(wi)

for i in range(vvv,0,-1):
    if dp[i]!=None:
        for j in range(n):
            if i-vi[j]>=1:
              if dp[i-vi[j]]!=None:
                dp[i-vi[j]]=min(dp[i-vi[j]],dp[i]-wi[j])
              else:
                dp[i-vi[j]]=dp[i]-wi[j]


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, w = LI()
wv = LIR(n)
vv = 10 ** 3
dp = [INF] * (vv + 1)
dp[0] = 0
for i in range(n):
    wi, vi = wv[i]
    for j in range(vv, vi - 1, -1):
        dp[j] = min(dp[j], dp[j - vi] + wi)

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

Submission status: Wrong Answer

Solution code:
INF = 10**15
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)
dp = [[INF]*10100 for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
  for j in range(10100):
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    if 0 <= j-value[i]:
      dp[i][j] = min(dp[i][j], dp[i-1][j-value[i]]+ weight[i])

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

Submission status: Wrong Answer

Solution code:
INF = 10**20
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)
dp = [[INF]*10100 for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
  for j in range(10100):
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    if -1 < j-value[i]:
      dp[i][j] = min(dp[i][j], dp[i-1][j-value[i]]+ weight[i])

ans = 0
for i in range(10100):
  if dp[N][i] < W+1:
    ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10**20
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)
dp = [[INF]*10100 for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
  for j in range(10100):
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    if -1 < j-value[i]:
      dp[i][j] = min(dp[i][j], dp[i-1][j-value[i]]+ weight[i])

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

Submission status: Wrong Answer

Solution code:
INF = 10**20
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)
dp = [[INF]*10000 for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
  for j in range(10000):
    dp[i][j] = min(dp[i][j], dp[i-1][j])
    if -1 < j-value[i]:
      dp[i][j] = min(dp[i][j], dp[i-1][j-value[i]]+ weight[i])

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

Submission status: Wrong Answer

Solution code:
def input_li():
    return list(map(int, input().split()))

def input_int():
    return int(input())

N, W = input_li()
MAX_V = 10 ** 3 * (N + 1)
MAX_W = 10 ** 9 + 1
# dp[n][v] ... 荷物nまでの価値vを得るために必要な最小の重量を格納する
dp = [[MAX_W] * MAX_V for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    w, v = input_li()
    for sum_v in range(MAX_V):
        if v > sum_v:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])
        else:
            dp[i + 1][sum_v] = min(
                dp[i + 1][sum_v],
                dp[i][sum_v - v] + w
            )
ans = 0
for sum_v in range(MAX_V):
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

Submission status: Wrong Answer

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

weights = [0]*n
values = [0]*n

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

v = sum(values)

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

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

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

for j in range(v+1):
    if dp[-1][j] == w:
        print(j)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

N, W = list(map(int, input().split()))
INF = 10**10

dp = [[INF]*(1005) for i in range(N+5)]

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

for i in range(1,N+1):
    w, v = list(map(int, input().split()))
    for j in range(1001):
        if j - v <= 0:
            a = 0
        else:
            a = dp[i-1][j-v]
        dp[i][j] = min(dp[i-1][j], a+w)

for i in range(1005):
    if dp[N][i] > W:
        print(i-1)
        exit()

Submission status: Wrong Answer

Solution code:
N, W = list(map(int, input().split()))
dp = [[W+1]*(10000+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = list(map(int, input().split()))
    for j in range(10000+1):
        if j+v <= 10000:
            dp[i+1][j+v] = min(dp[i+1][j+v], dp[i][j] + w)
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
i = -1
while True:
    if dp[N][i] <= W:
        print(10000+1+i)
        break
    else:
        i -= 1

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(10**5+1)]
	for _ in range(N):
		v,w = map(int, input().split())
		for i in range(10**5,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = b
				else:
					dp[i] = a
		
	print(dp[-1])
 
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(N)]
item.sort(key=lambda x: x[1])
item.append([0, 0])

splited_item = []
prev = 0
start = 0
for i,sub in enumerate(item):
    if i == 0:
        continue
    if sub[0] != prev:
        splited_item.extend([item[start:i]])
        start = i
    prev = sub[0]

item = []
for part in splited_item:
    item.extend(list(reversed(part)))


ans = 0
total_weight = 0

for i in range(N):
    while item:
        weight, value = item.pop()
        if weight <= W - total_weight:
            ans += value
            total_weight += weight
            break
    if not item:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
def pprint(M):
	for row in M:
		print(row)
	print("~~~")


def main():
	n, W = rli()
	weights, vals = [], []
	for _ in range(n):
		w, v = rli()
		weights.append(w)
		vals.append(v)
	maxval = 100
	dp = [INF for _ in range(maxval+1)]
	dp[0] = 0
	for w, v in zip(weights, vals):
		for i in range(maxval, -1, -1):
			if i - v < 0: continue
			dp[i] = min(dp[i], dp[i-v] + w)
	for i in range(maxval, -1, -1):
		if dp[i] <= W:
			print(i)
			break
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

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

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

#  i:N個目 j:価値

dp[0][0] = 0

for i, (w, v) in enumerate(x, 1):
    for j in range(1, 10**5 + 1):
        dp[i][j] = dp[i - 1][j]
        if v <= j:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - v] + w)

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

Submission status: Wrong Answer

Solution code:
import scipy.optimize

def get_tmp_ans(v,l):
    n=0
    for i in range(len(l)):
        if l[i]==1:n+=abs(v[i])
    return n

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

list1=[]
for x in a:
    list1.append([x[1]/x[0],x[1],x[0]])

val=[]
wei=[]
max_w=[w]
for x in sorted(list1)[::-1]:
    val.append(-x[1])
    wei.append(x[2])
wei=[wei]
x_bounds=[(0,1)]*n

sr=scipy.optimize.linprog(val,A_ub=wei,b_ub=max_w,bounds=x_bounds,method="revised simplex")
res=get_tmp_ans(val,sr["x"])

list2=[[val,wei,max_w,x_bounds,res]]

while len(list2)!=0:

    poped=list2.pop()
    res=max(res,poped[4])
    if len(poped[0])==1:continue

    if poped[2][0]>poped[1][0][0]:
        l=[ poped[0][1:],[poped[1][0][1:]],[poped[2][0]-poped[1][0][0]],poped[3][1:],poped[4]+poped[0][0] ]
        sr=scipy.optimize.linprog(l[0],A_ub=l[1],b_ub=l[2],bounds=l[3],method="revised simplex")
        point=get_tmp_ans(l[0],sr["x"])
        if sr["success"] and point>=res:
            l[4]=point
            list2.append(l)

    l=[ poped[0][1:],[poped[1][0][1:]],[poped[2][0]],poped[3][1:],poped[4] ]
    sr=scipy.optimize.linprog(l[0],A_ub=l[1],b_ub=l[2],bounds=l[3],method="revised simplex")
    point=get_tmp_ans(l[0],sr["x"])
    if sr["success"] and point>=res:
        l[4]=point
        list2.append(l)

print(res)

Submission status: Wrong Answer

Solution code:
def chmin(dp, i, *x):
  dp[i] = min(dp[i], *x)
N, W, *D = map(int, open(0).read().split())
w, v = D[::2], D[1::2]
ΣV, INF = N * max(v), float("inf")
dp = [[INF]*-~ΣV for _ in [0]*-~N]
dp[0][0] = 0
for i in range(N):
  for j in range(ΣV):
    if j >= v[i]:
      chmin(dp[i + 1], j, dp[i][j - v[i]] + w[i])
    chmin(dp[i + 1], j, dp[i][j])
for j in range(ΣV):
  if dp[N][j] <= W:
    a = j
print(a)

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
import copy
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
 
Sum_Value = sum(map(lambda x:x[1],Goods_List))
dp = [[0] * (Sum_Value + 1) for i in range(N)]

for i in range(N):
    if i == 0:
        dp[i][Goods_List[i][1]] = Goods_List[i][0]
    else:
        dp[i] = copy.copy(dp[i-1])
        Valid_List = [k for k, x in enumerate(dp[i]) if x != 0]
        for j in Valid_List:
            if dp[i][j + Goods_List[i][1]] == 0:
                dp[i][j + Goods_List[i][1]] = dp[i-1][j] + Goods_List[i][0]
            else:
                dp[i][j + Goods_List[i][1]] = min(dp[i-1][j] + Goods_List[i][0],dp[i][j + Goods_List[i][1]])
            dp[i][Goods_List[i][1]] = Goods_List[i][0]

for k in range(len(dp[-1])-1,0,-1):
    if (dp[-1][k] != 0) & (dp[-1][k] <= W):
        print(k)
        break

Submission status: Wrong Answer

Solution code:
### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if Current_Weight <= W:
        Current_Search_List = list(set(map(lambda x:x+Current_Weight if 
                                           x+Current_Weight <= W else 0, dp.keys())))
        for j in Current_Search_List[1:]:
            Last_Search_Weight = j - Current_Weight
            if j in dp:
                dp[j] = max(dp[j],dp[Last_Search_Weight] + Current_Value)
            else: 
                dp[j] = dp[Last_Search_Weight] + Current_Value

print(max(dp.values()))

Submission status: Wrong Answer

Solution code:
### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
Goods_List=[]

dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if (i == 0) & (Current_Weight <= W) :
        dp[Current_Weight] = Current_Value
    elif i > 0:
        Current_Search_List = list(set(map(lambda x:x+Current_Weight if 
                                           x+Current_Weight <= W else 0, dp.keys())))
        for j in Current_Search_List[1:]:
            if j == 0:
                continue
            Last_Search_Weight = j - Current_Weight
            if j in dp:
                dp[j] = max(dp[j],dp[Last_Search_Weight] + Current_Value)
            else: 
                dp[j] = dp[Last_Search_Weight] + Current_Value

print(max(dp.values()))

Submission status: Wrong Answer

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**4+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(10**4 + 1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if 0 <= j - A[i][1] and dp[i][j - A[i][1]] + A[i][0] <= W:
                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**4+1)[::-1]:
        if dp[N][j] <= W:
            ans = j
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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**4+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(10**4 + 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**4+1)[::-1]:
        if dp[N][j] <= W:
            ans = max(ans, j)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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**4+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(10**4 + 1):
            if 0 <= j - A[i][1]:
                dp[i+1][j] = min(dp[i][j], dp[i][j - A[i][1]] + A[i][0])
            else:
                dp[i+1][j] = dp[i][j]

    ans = 0
    for j in range(10**4+1)[::-1]:
        if dp[N][j] <= W:
            ans = j
            break
    print(ans)


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):
    w[i], v[i] = map(int, input().split())

INF = 10**13 

V = (10**5)
# dp[n][v] = n番目までで価値vとなる最小の重さ
dp = [INF] * (V + 1)
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: Wrong Answer

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):
    if dp[N][j] <= W:
        res = j

print(res)

Submission status: Wrong Answer

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] = 1

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):
    if dp[N][j] <= W:
        res = j

print(res)

Submission status: Wrong Answer

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

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

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(1, 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):
    if dp[N][j] <= W:
        res = max(res, j)

print(res)

Submission status: Wrong Answer

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

#bottomup
memo = [10**10]*(10**3)
memo[0] = 0

for weight, value in items:
    for i in reversed(range(len(memo)-value)):
            memo[i+value] = min(memo[i+value],memo[i] + weight)

ans = 0
for i in range(len(memo)):
    if memo[i] != 10**10 and memo[i] <= W:
        ans = i

print(ans)

Submission status: Wrong Answer

Solution code:
def knapSack2(W, N, sumWmax):
    save = []
    for i in range(len(W)):
        save.append([N[i]/W[i], [W[i], N[i]]])
    save.sort(reverse=True)
    sumW = 0
    jwb = 0
    for i in range(len(save)):
        if save[i][1][0] + sumW <= sumWmax:
            sumW += save[i][1][0]
            jwb = save[i][1][1] + jwb

    return jwb



masukan = input() #"6 15"
masukan = masukan.split() #["6", "15"]
n = int(masukan[0])
k = int(masukan[1])

W = []
N = []
for _ in range(n):
  masukan = input()
  masukan = masukan.split()
  W.append(int(masukan[0]))
  N.append(int(masukan[1]))
print(knapSack2(W, N, k))

Submission status: Wrong Answer

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

def main():
    n, w = map(int,input().split())
    wei = []
    val = []
    for i in range(n):
        a, b = map(int,input().split())
        wei.append(a)
        val.append(b)

    max_v = 10**3 + 10
    dp = [[float('inf') for i in range(max_v)] for j in range(100+10)]

    dp[0][0] = 0

    for i in range(n):
        for sum_v in range(max_v):

            # i 番目の品物を選ぶ場合
            if sum_v - val[i] >= 0:
                dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v - val[i]] + wei[i])
            else:
                # i 番目の品物を選ばない場合
                dp[i+1][sum_v] = dp[i][sum_v]

    res = 0
    for i in range(100+10):
        for sum_v in range(max_v):
            if dp[i][sum_v] <= w and res < sum_v:
                res = sum_v

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    n, w = map(int,input().split())
    wei = []
    val = []
    for i in range(n):
        a, b = map(int,input().split())
        wei.append(a)
        val.append(b)

    for _ in range(10):
        wei.append([])
        val.append([])

    max_v = 10**3 + 100
    dp = [[float('inf') for i in range(max_v+1)] for j in range(100+10)]

    dp[0][0] = 0

    for i in range(n):
        for sum_v in range(max_v+1):

            # i 番目の品物を選ぶ場合
            if sum_v - val[i] >= 0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - val[i]] + wei[i])

            # i 番目の品物を選ばない場合
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

    res = 0
    for sum_v in range(max_v+1):
        if dp[n][sum_v] <= w:
            res = sum_v

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    n, w = map(int,input().split())
    wei = []
    val = []
    for i in range(n):
        a, b = map(int,input().split())
        wei.append(a)
        val.append(b)

    for _ in range(10):
        wei.append([])
        val.append([])

    max_v = 10**3 + 100
    dp = [[float('inf') for i in range(max_v)] for j in range(100+10)]

    dp[0][0] = 0

    for i in range(n):
        for sum_v in range(max_v):

            # i 番目の品物を選ぶ場合
            if sum_v - val[i] >= 0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - val[i]] + wei[i])

            # i 番目の品物を選ばない場合
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

    res = 0
    for sum_v in range(max_v):
        if dp[n][sum_v] <= w:
            res = sum_v

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    n, w = map(int,input().split())
    wei = []
    val = []
    for i in range(n):
        a, b = map(int,input().split())
        wei.append(a)
        val.append(b)

    for _ in range(10):
        wei.append([])
        val.append([])

    max_v = 10**3 + 100
    dp = [[float('inf') for i in range(max_v)] for j in range(n+10)]

    dp[0][0] = 0

    for i in range(n):
        for sum_v in range(max_v):

            # i 番目の品物を選ぶ場合
            if sum_v - val[i] >= 0:
                dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - val[i]] + wei[i])

            # i 番目の品物を選ばない場合
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])

    res = 0
    for sum_v in range(max_v):
        if dp[n][sum_v] <= w:
            res = sum_v

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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((100*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: Wrong Answer

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((100*N+1),-1,-1):
        if dp[j-v]!=INF:
            dp[j]=min(dp[j],dp[j-v]+w)
for i in range(100*N+1):
    if dp[i]<=W:
        ans=i
print(ans)

Submission status: Wrong Answer

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+1][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: Wrong Answer

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

DP= [[10**12 for j in range(100010)] for i in range(110)]
def chmin(a,b):
    if a>b:
        return b
    else:
        return a


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

DP[0][0]=0


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

ans=0        
for j in range(100010):
    if DP[N][j] <=W :
        ans=j

print(ans)

Submission status: Wrong Answer

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

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

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

for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)