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 N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy as np
import sys
import math
n,w = L()
v = 10**5
wv = NL(n)
dp = [[sys.maxsize]*(v+1) for i in range(n)]
#print(dp)
#print(wv)
for j in range(v+1):
    if j <= wv[0][1]:
        dp[0][j] = wv[0][0]
    else:
        break
sum = wv[0][1]
for i in range(1,n):
    sum += wv[i][1]
    for j in range(v+1):
        if j <= wv[i][1]:
            dp[i][j] = min(wv[i][0],dp[i-1][j])
        elif j <= sum:
            #print(sum-j)
            dp[i][j] =min(wv[i][0]+dp[i-1][j-wv[i][1]],dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
for j in range(v+1):
    if dp[n-1][j] <= w:
        ans = j
    else:
        break
#print(dp)
print(j-1)

Submission status: Wrong Answer

Solution code:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy as np
import sys
import math
n,w = L()
v = 10**5
wv = NL(n)
dp = [[sys.maxsize]*(v+1) for i in range(n)]
#print(dp)
#print(wv)
for j in range(v+1):
    if j <= wv[0][1]:
        dp[0][j] = wv[0][0]
    else:
        break
sum = dp[0][1]
for i in range(1,n):
    sum += wv[i][1]
    for j in range(v+1):
        if j <= wv[i][1]:
            dp[i][j] = min(wv[i][0],dp[i-1][j])
        elif j <= sum:
            #print(sum-j)
            dp[i][j] =min(wv[i][0]+dp[i-1][j-wv[i][1]],dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
for j in range(v+1):
    if dp[n-1][j] <= w:
        ans = j
    else:
        break
#print(dp)
print(j-1)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_e
import sys
N, W = map(int, input().split())
ws = []
vs = []
totalV = 0
for _ in range(N):
    w, v = map(int, input().split())
    ws.append(w)
    vs.append(v)
    totalV += v
dp = [[0 for _ in range(totalV + 1)] for _ in range(N + 1)]

for i in range(1, totalV + 1):
    dp[0][i] = sys.maxsize

for i in range(1, N + 1):
    for j in range(1, totalV + 1):
        dp[i][j] = dp[i - 1][j]
        if j - vs[i - 1] >= 0:
            # dp[i][j] := min weight to achive vs[i - 1] using ws[0] ~ ws[j - 2]
            dp[i][j] = min(dp[i][j], dp[i - 1][j - vs[i - 1]] + ws[i - 1])

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

Submission status: Wrong Answer

Solution code:
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
        ans = 1
        for i in range(1, x+1): ans = (ans * i) % mod
        return ans
def arr2D(n, m, default=0):
        lst = []
        for i in range(n): temp = [default] * m; lst.append(temp)
        return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(n, W, weight, value):
    if W > 10**5+2: return sum(value)
    dp = arr2D(n+1, W+1)

    for i in range(1, n+1):
        for j in range(1, W+1):
            # print(i, j)
            val = max(dp[i][j-1], dp[i-1][j])
            if j >= weight[i-1]:
                dp[i][j] = max(val, dp[i-1][j-weight[i-1]] + value[i-1])
            else: dp[i][j] = val
    return dp[n][W]

n, W = list(map(int, input().split()))
weight = []
value = []
for i in range(n):
        a, b = list(map(int, input().split()))
        weight.append(a)
        value.append(b)
print(solve(n, W, weight, value))

Submission status: Wrong Answer

Solution code:
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
        ans = 1
        for i in range(1, x+1): ans = (ans * i) % mod
        return ans
def arr2D(n, m, default=0):
        lst = []
        for i in range(n): temp = [default] * m; lst.append(temp)
        return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(n, W, weight, value):
    if W > 10**4+2: return sum(value)
    dp = arr2D(n+1, W+1)

    for i in range(1, n+1):
        for j in range(1, W+1):
            # print(i, j)
            val = max(dp[i][j-1], dp[i-1][j])
            if j >= weight[i-1]:
                dp[i][j] = max(val, dp[i-1][j-weight[i-1]] + value[i-1])
            else: dp[i][j] = val
    return dp[n][W]

n, W = list(map(int, input().split()))
weight = []
value = []
for i in range(n):
        a, b = list(map(int, input().split()))
        weight.append(a)
        value.append(b)
print(solve(n, W, weight, value))

Submission status: Wrong Answer

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

MAX = 10**11 + 1
dp = [[MAX]*(10**3+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for j in range(0, 10**3+1):
        if j == 0:
            dp[i][j] = 0
        elif j >= v_list[i-1]:
            dp[i][j] = min(dp[i-1][j], w_list[i-1]+dp[i-1][j-v_list[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp[i]) 
ans = 10**5 + 1
for k in range(10**3+1):
    if dp[N][k] <= W:
        ans = k
#print(dp[N])
print(ans)

Submission status: Wrong Answer

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

MAX = 10**9 + 1
dp = [[MAX]*(10**3+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for j in range(0, 10**3+1):
        if j == 0:
            dp[i][j] = 0
        elif j >= v_list[i-1]:
            dp[i][j] = min(dp[i-1][j], w_list[i-1]+dp[i-1][j-v_list[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp[i]) 
ans = 10**5 + 1
for k in range(10**3+1):
    if dp[N][k] <= W:
        ans = k
#print(dp[N])
print(ans)

Submission status: Wrong Answer

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

MAX = 10**5 + 1
dp = [[MAX]*(10**3+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for j in range(0, 10**3+1):
        if j == 0:
            dp[i][j] = 0
        elif j >= v_list[i-1]:
            dp[i][j] = min(dp[i-1][j], w_list[i-1]+dp[i-1][j-v_list[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp[i]) 
ans = 0
for k in range(10**3+1):
    if dp[N][k] <= W:
        ans = k
#print(dp[N])
print(ans)

Submission status: Wrong Answer

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

MAX = 10**5 + 1
dp = [[MAX]*(10**3+1) for i in range(N+1)]
for i in range(1, N+1):
    for j in range(0, 10**3+1):
        if j == 0:
            dp[i][j] = 0
        elif j >= v_list[i-1]:
            dp[i][j] = min(dp[i-1][j], w_list[i-1]+dp[i-1][j-v_list[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp[i]) 
ans = 0
for k in range(10**3+1):
    if dp[N][k] <= W:
        ans = k
#print(dp[N])
print(ans)

Submission status: Wrong Answer

Solution code:
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
	ans = 1
	for i in range(1, x+1): ans = (ans * i) % mod
	return ans
def arr2D(n, m, default=0):
	lst = []
	for i in range(n): temp = [default] * m; lst.append(temp)
	return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(st1, st2):
	n, m = len(st1), len(st2)
	dp = arr2D(n+1, m+1)

	for i in range(1, n+1):
		for j in range(1, m+1):
			if st1[i-1] == st2[j-1]:
				dp[i][j] = dp[i-1][j-1] + 1
			else:
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])

	lcs = ""
	i, j = n, m
	while i != 0 and j != 0:
		if dp[i][j] == dp[i-1][j]:
			i -= 1
		elif dp[i][j] == dp[i][j-1]:
			j -= 1
		else:
			lcs += st1[i-1]
			i -= 1
			j -= 1
	return lcs[::-1]
		
st1 = input()
st2 = input()
print(solve(st1, st2))

Submission status: Wrong Answer

Solution code:
def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 1000
# W <= 10**9 なので、
# dp[i][w]: i番目の選択で重さwだった時の価値の最大値、は計算量厳しい
# dp[i][v]: i番目の選択で価値vだった時の重さの最小値、で考えて重さの最小値がW以下のものから最大価値を算出する

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

# 初期条件
# 選ばない
dp[0][0] = 0
# 選ぶ
w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V+1):
        cw, cv = L[i]
        # 選ばない
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        # 選ぶ
        if v + cv > V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)

# 重さの最小値がW以下で達成できるvの最大値
v_max = 0
for v in range(V+1):
    if dp[N-1][v] <= W:
        v_max = v
print(v_max)

Submission status: Wrong Answer

Solution code:


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

INF = 10**15
dp = list([INF for _ in range(100010)] for _ in range(N+1))
dp[0][0] = 0

nap = []
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])

for i in range(N):
    w1, v1 = nap[i]
    for j in range(10010):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0
for j in range(10001):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Wrong Answer

Solution code:


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

INF = 10**15
dp = list([INF for _ in range(100010)] for _ in range(N+1))
dp[0][0] = 0

nap = []
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])

for i in range(N):
    w1, v1 = nap[i]
    for j in range(10010):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = dp[i][j]
ans = 0
for j in range(10001):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Wrong Answer

Solution code:


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

INF = 10**15
dp = list([INF for _ in range(100001)] for _ in range(N+1))
dp[0][0] = 0

nap = []
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])

for i in range(N):
    w1, v1 = nap[i]
    for j in range(10001):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = dp[i][j]
ans = 0
for j in range(10001):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Wrong Answer

Solution code:
"""
0-1 ナップサック
重みが大きい場合は
価値基準に変更
"""
n,w = map(int,input().split())
l = []
value = 0
for i in range(n):
    v1,w1 = map(int,input().split())
    l.append([v1,w1])
    value += v1

INF = 10**10
dp = list([INF for i in range(value+1)] for _ in range(n+1))
dp[0][0] = 0

for i in range(n):
    for j in range(value+1):
        v1,w1 = l[i]
        if j - v1 >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v1]+w1)
        else:
            dp[i+1][j] = dp[i][j]

ans = 0
for j in range(value+1):
    if dp[n][j] <= w:
        ans = j
print(ans)

Submission status: Wrong Answer

Solution code:


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

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

nap = []
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])

for i in range(N):
    w1, v1 = nap[i]
    for j in range(10001):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = dp[i][j]
ans = 0
for j in range(10001):
    if dp[N][j] <= W:
        ans = j

print(ans)

Submission status: Wrong Answer

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

def main(n,w,p):
    #dp[n][v]
    dp = [[0 for i in range(n*10*3+1)]]
    ans = 0
    for i in range(n):
        item = p[i]
        temp = []
        for j in range(n*10*3+1):
            #Cannot achieve
            cur = 0
            if j<item[1]:
                cur = dp[i][j]
                temp.append(cur)
            elif j==item[1]:
                cur = item[0]
                if dp[i][j]:
                    cur = min(item[0],dp[i][j])
                temp.append(cur)
            else:
                if dp[i][j] and dp[i][j-item[1]]:
                    cur = min(dp[i][j],dp[i][j-item[1]]+item[0])
                elif dp[i][j]:
                    cur = dp[i][j]
                elif dp[i][j-item[1]]:
                    cur = dp[i][j-item[1]]+item[0]
                temp.append(cur)
            if cur and cur<=w:
                ans = max(ans,j)
        dp.append(temp)
    print(ans)

                    
if __name__=="__main__":
    n,w,p = getval()
    main(n,w,p)

Submission status: Wrong Answer

Solution code:
import math

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

DP = [[math.inf] * 100001 for _ in range(N+1)]
DP[0][0] = 0
ans = 0

for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(1, 100001):
        if j >= v:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-v]+w)
        else:
            DP[i][j] = DP[i-1][j]

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

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(list(map(int, input().split())))
dp = [[float('inf')] * (10 ** 3 + 1) for _ in range(N)]
for i in range(10 ** 3 + 1):
    if i <= items[0][1]:
        dp[0][i] = items[0][0]

for i in range(1, N):
    weight = items[i][0]
    value = items[i][1]
    for j in range(10 ** 3 + 1):
        if j <= value:
            dp[i][j] = min(dp[i - 1][j], weight)
        else:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - value] + weight)
ans = 0
for i in range(10 ** 3 + 1):
    if dp[-1][i] <= W:
        ans = i
# print(*dp, sep='\n')
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=[int(x) for x in input().split()]
w=[-1 for _ in range(N)]
v=[-1 for _ in range(N)]
for i in range(N):
	w[i],v[i]=[int(x) for x in input().split()]
#Constraints N<=100 W<=10^9 w[i]<=10^9 and v[i]<=10^3
#dp[w] used to store maximum value at weight<=w
#dp[v] used to store minimum weight at value==v
dp=[10000000 for _ in range(100001)]
dp[0]=0
for i in range(N):
	for v_ in range(100000,v[i]-1,-1):
		#print(v_-v[i])
		dp[v_]=min(dp[v_],dp[v_-v[i]]+w[i])
for v_ in range(100000,-1,-1):
	if dp[v_]<=W: print(v_); break

Submission status: Wrong Answer

Solution code:
N,W=[int(x) for x in input().split()]
w=[-1 for _ in range(N)]
v=[-1 for _ in range(N)]
for i in range(N):
	w[i],v[i]=[int(x) for x in input().split()]
#Constraints N<=100 W<=10^9 w[i]<=10^9 and v[i]<=10^3
#dp[w] used to store maximum value at weight<=w
#dp[v] used to store minimum weight at value==v
dp=[10000000 for _ in range(100002)]
dp[0]=0
for i in range(N):
	for v_ in range(100001,v[i]-1,-1):
		#print(v_-v[i])
		dp[v_]=min(dp[v_],dp[v_-v[i]]+w[i])
for v_ in range(100001,-1,-1):
	if dp[v_]<=W: print(v_); break

Submission status: Wrong Answer

Solution code:
n,W = map(int,input().split())
w,v = [],[]
for i in range(n):
    wi,vi = map(int,input().split())
    w.append(wi)
    v.append(vi)
sv = sum(v)
INF = float("INF")
dp = [[INF]*sv for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(sv):
        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])
    #print(dp)
ans = 0
for i in range(sv):
    #print(dp[n][i])
    if dp[n][i] <= W:
        ans = max(ans,i)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.zeros(W+1, dtype=np.int8)

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

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)
Vmax = max(v)
INF = 10**9
dp =[[INF]*(Vmax*N+1) for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    for j in range(Vmax*N):
        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]
        
for i in range(Vmax*N):
    if dp[N][i] <= W:ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
N,W = map(int,input().split())
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)
Vmax = max(v)
INF = 999
dp =[[INF]*(Vmax*N+1) for _ in range(N+1)]
dp[0][0]=0

for i in range(N):
    for j in range(Vmax*N):
        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]
        
for i in range(Vmax*N):
    if dp[N][i] <= W:ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

    Vmax = max(v)*N
    INF = 10**9

    dp = np.ones((N+1,Vmax+1),dtype=np.int64)*INF
    dp[0][0]=0

    for i in range(N):
        tmp = np.ones(Vmax+1,dtype=int)*INF
        if i==0:tmp[0]=0
        tmp[v[i]:] = dp[i][:-v[i]] + w[i]
        dp[i+1] = np.minimum(dp[i],tmp)


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

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

    Vmax = max(v)*N
    INF = 10**20

    dp = np.ones((N+1,Vmax+1),dtype=np.int64)*INF
    dp[0][0]=0

    for i in range(N):
        tmp = np.ones(Vmax+1,dtype=int)*INF
        tmp[v[i]:] = dp[i][:-v[i]] + w[i]
        dp[i+1] = np.minimum(dp[i],tmp)


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

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

    Vmax = max(v)*N
    INF = 10**9

    dp = np.ones((N+1,Vmax+1),dtype=np.int64)*INF
    dp[0][0]=0

    for i in range(N):
        tmp = np.ones(Vmax+1,dtype=int)*INF
        tmp[v[i]:] = dp[i][:-v[i]] + w[i]
        dp[i+1] = np.minimum(dp[i],tmp)


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

Submission status: Wrong Answer

Solution code:
n,w = map(int,input().split())
v = [0]*n
for i in range(n):
    v[i] = list(map(int,input().split()))
    
dp = [[float("Inf") for j in range(1000*n+1)] for i in range(n+1)]

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

for i,[W,V] in enumerate(v):
    for j in range(1000*n):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if dp[i][j] + W <= w:
            dp[i+1][j+V] = min(dp[i+1][j+V], dp[i][j] + W)
ans = 0
for i in range(n+1):
    for j in range(1000*n):
        if dp[i][j] <= w:
            ans = max(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
[N,W]=[int(x) for x in input().split()]
wv=[[int(x) for x in input().split()] for i in range(N)]

dp=np.array([[10**10]*(10**5) for i in range(N)])

dp[0][wv[0][1]]=wv[0][0]
dp[0][0]=0

for i in range(1,N):
  last=10**5-wv[i][1]+1
  dp[i][wv[i][1]:]=np.minimum(dp[i-1][wv[i][1]:],dp[i-1][:last-1]+wv[i][0])
  dp[i][:wv[i][1]]=dp[i-1][:wv[i][1]]
ans=0
count=10**5-1
while(ans==0):
  if dp[N-1][count]<=W:
    ans=count
    break
  else:
    count=count-1
print(ans)

Submission status: Wrong Answer

Solution code:
n,w=map(int,input().split())
l=[]
for i in range(n):
	l.append(list(map(int,input().split())))
max_val=1000*n
dp=[[float('inf') for i in range(max_val+1)] for j in range(n+1)]

dp[1][l[0][1]]=l[0][0]
for i in range(2,n+1):
	for j in range(1,max_val+1):
		dp[i][j]=dp[i-1][j]
		if(l[i-1][1]<=j):
			dp[i][j]=min(dp[i][j],dp[i-1][j-l[i-1][1]]+l[i-1][0])
ans=float('-inf')
for i in range(max_val+1):
	if(dp[n][i]<=w):
		ans=max(ans,i)
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    #start here
    n, W = map(int,input().split())
    if (W > 10**5+1):
        ans = 0
        for i in range(n):
            w, v = map(int,input().split())
            ans+=v
        print(ans)
        return
    l = []
    dp = [[0 for i in range(W+1)] for j in range(n)]
    for i in range(n):
        w, v = map(int,input().split())
        for j in range(1, W+1):
            if(w>j):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], v+dp[i-1][j-w])
    print(dp[n-1][W])
solve()

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
wv = [tuple(map(int,input().split())) for _ in range(N)]
INF = 10**20

vmax = sum([wv[i][1] for i in range(N)])

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

for i in range(1,N+1):
  for j in range(wv[i-1][1],vmax+1):
    dp[i][j] = min(dp[i-1][j], dp[i-1][j-wv[i-1][1]]+wv[i-1][0])

#print(dp[-1])
for i in range(vmax, -1, -1):
  #print(i,dp[-1][i],W)
  if dp[-1][i] <= W:
    print(i)
    exit()

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
wv = [tuple(map(int,input().split())) for _ in range(N)]
INF = 10**20

vmax = sum([wv[i][1] for i in range(N)])

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

for i in range(1,N+1):
  for j in range(1,vmax+1):
    if j >= wv[i-1][1]:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-wv[i-1][1]]+wv[i-1][0])
    else:
      dp[i][j] = dp[i-1][j]
      
#print(dp[-1])
for i in range(vmax, -1, -1):
  #print(i,dp[-1][i],W)
  if dp[-1][i] <= W:
    print(i)
    exit()

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
INF = 10**9+1

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

for i in range(N):
    for j in range(N*10**3):
        if j > wv[i][1]:
            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][j], wv[i][0])
        
ans = 0
for i in range(N+1):
    for j in range(N*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())
wv = [[0, 0]]
for _ in range(N):
    w, v = map(int, input().split())
    wv.append([w, v])

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

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

# print(dp)
print(ans)

Submission status: Wrong Answer

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

dp=[inf]*100
dp[0]=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]+dp[j-x[1]])
        else:
            nextdp[j]=dp[j]
    dp=nextdp


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

Submission status: Wrong Answer

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

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


for i in range(0,n):
    nextdp=[inf]*100001
    x=[int(i) for i in input().split()]
    for j in range(100001):
        if x[1] >= j:
            nextdp[j]=min(dp[j],x[0])
        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())
inf=float('inf')

dp=[inf]*100001
m=0



for i in range(0,n):
    nextdp=[inf]*100001
    x=[int(i) for i in input().split()]
    for j in range(100001):
        if x[1] >= j:
            nextdp[j]=min(dp[j],x[0])
        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