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:
#EDP-E
import sys
n,W = map(int, sys.stdin.readline().split())

dp = [[1000000001 for i in range(100001)] for _ in range(n)]


w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    for va in range(100001): 
        if v >= va:
            dp[i][va] = dp[i-1][va]
        else:
            dp[i][va] = min(dp[i][va], dp[i-1][va-v] + w)
    dp[i][v] = min(dp[i][v], w)

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

Submission status: Wrong Answer

Solution code:
def main():

    N, W = map(int, raw_input().split())
    if W > 10**7:
        W = 10**7
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()

Submission status: Wrong Answer

Solution code:
def main():

    N, W = map(int, raw_input().split())
    if W > 10**5:
        W = 10**5
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    dp = [10 ** 10] * (10 ** 3 * n + 1)
    dp[0] = 0
    max_v = 0
    for ww, vv in wv:
        for i in range(max_v+1):
            dp[i+vv] = min(dp[i+vv], dp[i] + ww)
            max_v = i+vv
    mt = 0
    for i in range(len(dp)):
        if dp[i] <= w:
            mt = max(mt, dp[i] if dp[i] != 10 ** 10 else 0)
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[[float("inf")]*(10**3+1) for _ 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**3+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]


ans=float("inf")
for i in range(10**3+1):
    if dp[n][i]<=m:
        ans=i

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
dp=[[float("inf")]*(10**3+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
    w,v=map(int,input().split())
    dp[i][v]=min(w,dp[i-1][v])
    for j in range(10**3+1):
        if dp[i-1][j]==0:
            continue
        if j+v<=10**3:
            dp[i][j+v]=min(dp[i][j+v],dp[i-1][j]+w)
        dp[i][j]=min(dp[i-1][j],dp[i][j])

ans=float("inf")
for i in range(10**3+1):
    if dp[n][i]<=m:
        ans=i

print(ans)

Submission status: Wrong Answer

Solution code:
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=limit_w<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n ,limit_w = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
sum_v = sum(v)
dp = [[INF for i in range(sum_v + 1)] for j in range(n + 1)] 
# dp[i][j]には重さが入る.
# dp[i][j]=(i番目までの品物から価値がちょうどｊになるための重さの最小値)

# ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(sum_v + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
            
# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
ans = 0
for i in range(sum_v + 1):
    if dp[n][i] <= limit_w:
        ans = i
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N,W=map(int,input().split())

l=[-1]*(10**5+1)
l[0]=0
dp=l[:]


for i in range(N):
    w,v=map(int,input().split())
    for index,item in enumerate(l):
        if item!=-1 and item+w<=W:
            dp[index+v]=max(item+w,l[index+v])
    l=dp[:]
    
for index,item in enumerate(l):
    if item!=-1:
        ans=index

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
N,W=map(int,input().split())

l=[-1]*(10**5+1)
l[0]=0
dp=l[:]


for i in range(N):
    w,v=map(int,input().split())
    for index,item in enumerate(l):
        if item!=-1 and item+w<=W:
            dp[index+v]=max(item+w,l[index+v])
    l=dp[:]
    
for index,item in enumerate(l[::-1]):
    if item!=-1:
        print(10**5-index)
        exit()

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(N)]
m=10**3+1
dp=[[float('inf')] * (m+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
  w,v = wv[i]
  for j in range(m):
    dp[i+1][j] = dp[i][j]
    if j < v:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
ans=0
for k in range(m):
  if dp[N][k]<=W:
    ans=k
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
INF = 10**3
wv=[list(map(int,input().split())) for _ in range(N)]
dp=[[float('inf') for _ in range(INF)] for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
  w,v = wv[i]
  for j in range(INF):
    dp[i+1][j] = dp[i][j]
    if j < v:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
ans=0
for k in range(INF):
  if dp[N][k]<=W:
    ans=k
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
INF = 10**3
wv=[list(map(int,input().split())) for _ in range(N)]
dp=[[float('inf') for _ in range(INF)] for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
  w,v = wv[i]
  for j in range(INF):
    dp[i+1][j] = dp[i][j]
    if j < v:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
ans=0
for i in range(INF):
  if dp[N][i] <= W:
    ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
INF = 10**3
wv=[list(map(int,input().split())) for _ in range(N)]
dp=[[float('inf') for _ in range(INF)] for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
  v = wv[i][1]
  for j in range(INF):
    dp[i+1][j] = dp[i][j]
    if j - v >= 0:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v] + wv[i][0])
ans=0
for i in range(INF):
  if dp[N][i] <= W:
    ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
INF = 10**3
wv=[list(map(int,input().split())) for _ in range(N)]
dp=[[10**9 for _ in range(INF)] for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
  v = wv[i][1]
  for j in range(INF):
    dp[i+1][j] = dp[i][j]
    if j >= v:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v] + wv[i][0])
ans=0
for i in range(INF):
  if dp[N][i] <= W:
    ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
N,W=map(int,input().split())
INF = 10**3
wv=[list(map(int,input().split())) for _ in range(N)]
dp=[[0 for _ in range(INF)] for _ in range(N+1)]
for i in range(N):
  v = wv[i][1]
  for j in range(INF):
    dp[i+1][j] = dp[i][j]
    if j >= v:
      dp[i+1][j] = max(dp[i+1][j], dp[i][j-v] + wv[i][0])
for i in range(INF):
  if dp[N][i] > W:
    print(i)
    exit()
  elif dp[N][i] == W:
    print(i)
    exit()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
v_max = 100010
INF = 100000010
n, w = map(int, input().split())
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

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

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max):
    if dp[n][j] <= w:
        result = j
print(result)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
v_max = 1010
INF = 1000000100000
n, w = map(int, input().split())
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

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

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max):
    if dp[n][j] <= w:
        result = j
print(result)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
v_max = 1010
INF = 1000000100
n, w = map(int, input().split())
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

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

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max):
    if dp[n][j] <= w:
        result = j
print(result)

Submission status: Wrong Answer

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

INF = 1e9+7
MAX_v = 1010
n,w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[INF]*MAX_v for _ in range(n+1)]
dp[0][0]= 0
for i in range(1, n+1):
    for sum_v in range(MAX_v):
        dp[i][sum_v] = dp[i-1][sum_v]
        if sum_v-wv[i-1][1]>=0:
            dp[i][sum_v]=min(dp[i][sum_v], dp[i-1][sum_v-wv[i-1][1]]+wv[i-1][0])

ans = 0
for i in range(MAX_v):
    if dp[n][i]<=w:
        ans = i
print(ans)

Submission status: Wrong Answer

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

INF = 1e9
MAX_v = 1010
n,w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[INF]*MAX_v for _ in range(n+1)]
dp[0][0]= 0
for i in range(1, n+1):
    for sum_v in range(MAX_v):
        dp[i][sum_v] = dp[i-1][sum_v]
        if sum_v-wv[i-1][1]>=0:
            dp[i][sum_v]=min(dp[i][sum_v], dp[i-1][sum_v-wv[i-1][1]]+wv[i-1][0])

ans = 0
for i in range(MAX_v):
    if dp[n][i]<=w:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
imput = sys.stdin.readline
def main():
    # input
    N, weight = map(int, input().split())
    W, V = [], []
    for _ in range(N):
        w, v = map(int, input().split())
        W.append(w)
        V.append(v)
    V_max = sum(V)

    # loop
    dp = [[10**9]*(V_max+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(0, V_max+1):
            if j<V[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]]+W[i])

    # check
    ans = []
    for j in range(1, V_max+1):
        if dp[i+1][j] <= weight:
            print(dp[i+1][j], j)
            ans.append(j)
    print(max(ans))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
max_value = N*(10**3)
dp = [[10**11]*(max_value+1) for _ in range(N+1)]
dp[0][0]=0
for j in range(1, N+1):
    w, v = map(int, input().split())
    for k in range(1, max_value+1):
        if k < v:
            dp[j][k] = dp[j-1][k]
        else:
            dp[j][k] = min(dp[j-1][k-v]+w, dp[j-1][k])
answer = 0
for index, weight in enumerate(dp[N]):
    if weight <= W:
        answer = index
print(answer)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
max_value = N*(10**3)
dp = [[max_value]*(max_value+1) for _ in range(N+1)]
dp[0][0]=0
for j in range(1, N+1):
    w, v = map(int, input().split())
    for k in range(1, max_value+1):
        if k < v:
            dp[j][k] = dp[j-1][k]
        else:
            dp[j][k] = min(dp[j-1][k-v]+w, dp[j-1][k])
print(dp[N])
answer = 0
for i in dp[N]:
    if i <= W:
        answer = i
print(answer)

Submission status: Wrong Answer

Solution code:
N,W = [int(s) for s in input().split()]
dp = [[10**10]*(1000*100) for _ in range(N+1)]#外側から内側のイメージ

dp[0][0] = 0
for i in range(N):
    w, v = [int(s) for s in input().split()]
    for sum_v in range(1000*100):
        if sum_v - v >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v-v] + w)
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

ans = 0
for sum_v in range(1000*100):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Wrong Answer

Solution code:
N,W = [int(s) for s in input().split()]
dp = [[10**10]*(1001) for _ in range(N+1)]#外側から内側のイメージ

dp[0][0] = 0
for i in range(N):
    w, v = [int(s) for s in input().split()]
    for sum_v in range(1001):
        if sum_v - v >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v-v] + w)
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

ans = 0
for sum_v in range(1001):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Wrong Answer

Solution code:
N,W = [int(s) for s in input().split()]
dp = [[10**10]*(1000) for _ in range(N+1)]#外側から内側のイメージ

dp[0][0] = 0
for i in range(N):
    w, v = [int(s) for s in input().split()]
    for sum_v in range(1000):
        if sum_v - v >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v-v] + w)
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

ans = 0
for sum_v in range(1000):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Submission status: Wrong Answer

Solution code:
N,W = [int(s) for s in input().split()]
dp = [[10**10]*(1000) for _ in range(N+1)]#外側から内側のイメージ

dp[0][0] = 0
for i in range(N):
    w, v = [int(s) for s in input().split()]
    for sum_v in range(1000):
        if sum_v -v >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v-v] + w)
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

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

print(ans)

Submission status: Wrong Answer

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

DP = [0] * (sum_v+1)

for i in range(N):
    for j in (reversed(range(sum_v))):
        if j == 0 or DP[j] != 0:
            if DP[j + v[i]] > DP[j] + w[i] or DP[j + v[i]] == 0:
                DP[j + v[i]] = DP[j] + w[i]

for j in (reversed(range(sum_v))):
    if DP[j] != 0 and DP[j] <= W:
        print(j)
        break

Submission status: Wrong Answer

Solution code:
n,w=list(map(int, input().split()))
wv =[]
sum_w = 0
sum_v = 0
for i in range(n):
    wv_1 = list(map(int, input().split()))
    wv.append(wv_1)
    sum_w += wv_1[0]
    sum_v += wv_1[1]

dp = [[float("inf") for _ in  range(sum_v+1)] for _ in range(n+1)]
dp[0][0] = 0

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

for i,name in enumerate(dp[n][::-1]):
    if name <= w:
        break

print(sum_v - i)

Submission status: Wrong Answer

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

N,W=map(int,input().split())
V = 1000
INF = 1e+9
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[INF]*(N*V+1) for _ in range(N+1)]
dp[0][0] = 0

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

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

Submission status: Wrong Answer

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n)]

#初期化
dp[0][L[0][1]] = L[0][0]
#print(dp)


for i in range(1, n):
    Lw, Lv = L[i][0], L[i][1] #価値テーブルに重量を入れる
    dp[i][Lv] = min(Lw, dp[i-1].get(Lv, Lw))
    for v, w in dp[i-1].items():
        dp[i][v] = min(w, dp[i-1].get(v, w)) #上下比較
        tmp_w= min(Lw+ w, dp[i-1].get(Lv+v, Lw+w))
        if tmp_w <=limit:
            dp[i][Lv+ v] = tmp_w
        

print(max(dp[-1].keys()))

Submission status: Wrong Answer

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv = L[i][0], L[i][1] 
    dp[i+1][Lv] = min(Lw, dp[i].get(Lv, Lw))          #価値テーブルに重量を入れる
    for v, w in dp[i].items():
        dp[i+1][v] = min(w, dp[i].get(v, w)) #上下比較
        tmp_w= min(Lw+ w, dp[i].get(Lv+v, Lw+w))
        if tmp_w <=limit:
            dp[i+1][Lv+ v] = tmp_w
        
print(max(dp[-1].keys()))

Submission status: Wrong Answer

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv = L[i][0], L[i][1] #価値テーブルに重量を入れる
    dp[i+1][Lv] = Lw
    for v, w in dp[i].items():
        dp[i+1][v] = min(w, dp[i].get(v, w)) #上下比較
        tmp_w= min(Lw+ w, dp[i].get(Lv+v, Lw+w))
        if tmp_w <=limit:
            dp[i+1][Lv+ v] = tmp_w
        
#print(dp)
print(max(dp[-1].keys()))

Submission status: Wrong Answer

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv = L[i][0], L[i][1] #価値テーブルに重量を入れる
    dp[i+1][Lv] = Lw
    for v, w in dp[i].items():
        dp[i+1][v] = min(w, dp[i].get(v, w)) #上下比較
        tmp_w= min(Lw+ w, dp[i].get(Lv+v, Lw+w))
        if tmp_w <=limit:
            dp[i+1][Lv+ v] = tmp_w
        
print(dp)
print(max(dp[-1].keys()))

Submission status: Wrong Answer

Solution code:
N = 100 + 7
V = 1000 + 7

inf = 10**10

dp = [[inf for _ in range(V)] for _ in range(N)]

def knapsack(n: int, W: int, wt: list, val: list) -> int:
	global dp

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

	for value in range(val[0]):
		dp[0][value] = 0
		
	dp[0][val[0]] = wt[0]

	for i in range(1,n):
		for value in range(0, V):
			if val[i] > value:
				dp[i][value] = dp[i-1][value]
			else:
				dp[i][value] = min(dp[i-1][value-val[i]] + wt[i], dp[i-1][value])

	for i in range(V-1, -1, -1):
		if dp[n-1][i] <= W:
			return i

	return -1	

def main():
	n, W = list(map(int, input().strip().split()))

	wt = []
	val = []

	for _ in range(n):
		w, v = list(map(int, input().strip().split()))

		wt.append(w)
		val.append(v)

	print(knapsack(n, W, wt, val))


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
N = 100 + 7
V = 1000 + 7

inf = 10**10

dp = [[inf for _ in range(V)] for _ in range(N)]

def knapsack(n: int, W: int, wt: list, val: list) -> int:
	global dp

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

	dp[0][val[0]] = wt[0]

	for i in range(1,n):
		for value in range(0, V):
			if val[i] > value:
				dp[i][value] = dp[i-1][value]
			else:
				dp[i][value] = min(dp[i-1][value-val[i]] + wt[i], dp[i-1][value])

	for i in range(V-1, -1, -1):
		if dp[n-1][i] <= W:
			return i

	return -1	

def main():
	n, W = list(map(int, input().strip().split()))

	wt = []
	val = []

	for _ in range(n):
		w, v = list(map(int, input().strip().split()))

		wt.append(w)
		val.append(v)

	print(knapsack(n, W, wt, val))


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv = L[i][0], L[i][1] #価値テーブルに重量を入れる
    dp[i+1][Lv] = Lw 
    for v, w in dp[i].items():
        dp[i+1][v] = min(w, dp[i].get(v, w)) #上下比較
        tmp_w= min(Lw+ w, dp[i].get(Lv+v, Lw+w))
        if tmp_w <=limit:
            dp[i+1][Lv+ v] = tmp_w
        

print(max(dp[-1].keys()))

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
INF = 10**12
dp = [[INF for i in range(1100)] for j in range(N+1)]

"""
dp[i][v] i個目の品物に対して、価値vをgetしうる重さの最小値
"""
dp[0][0] = 0

for i in range(N):
    w,v = map(int, input().split())
    for j in range(1100):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if v + j < 1100 and dp[i][j] != INF:
            # print("aaa",v+j,min(dp[i][v+j],dp[i][j]+w))
            dp[i+1][v+j] = min(dp[i][v+j],dp[i][j]+w)
            # print(dp[i+1][v+j],min(dp[i][v+j],dp[i][v]+w))


res = dp[N]
ans = 0
for v,r in enumerate(res):
    if r <= W:
        ans = v
print(ans)

Submission status: Wrong Answer

Solution code:
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())

sum_v = sum(v)

dp = [[10**18] * (sum_v + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
    for j in range(sum_v + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
        if j - v[i] <= 0:
            if dp[i][j-v[i]] == 10**18:
                dp[i + 1][j] = w[i]
            else:
                dp[i + 1][j] = dp[i][j - v[i]] + w[i]
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

for i in range(sum_v + 1):
    #print(dp[N][sum_v - i],i)
    if dp[N][sum_v - i] <= W and dp[N][sum_v - i] != 0:
        print(sum_v - i)
        exit()

print(0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

    INF = int(1e13)
    dp = np.array([[INF] * (1000 * N + 1) for i in range(N+1)])
    dp[0][0] = 0

    for i in range(N):
        w, v = wv[i]
        dp[i+1] = dp[i]
        tmp = np.where(dp[i, :-v] != INF)[0]
        # print(tmp)
        dp[i+1, tmp + v] = np.minimum(dp[i+1, tmp + v], dp[i+1, tmp] + w)
    
    # print(dp[:,:15])
    for i in range(1000, -1, -1):
        if dp[N][i] <= W:
            print(i)
            break

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    t = [[int(i) for i in input().split()] for _ in range(N)]

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

    dp[0][0] = 0
    for n in range(1, N+1):
        dp[n][0] = 0
        for v in range(1, N*10**3+1):
            dp[n][v] = min(dp[n-1][v], dp[n-1][max(0, v-t[n-1][1])]+t[n-1][0])
    ans = float("inf")*-1
    for i, v in enumerate(dp[N]):
        if v <= W:
            ans = max(ans, i)

    print(ans)
    print(dp[N][:30])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

    INF = int(1e12)
    dp = np.array([[INF] * (1000 * N + 1) for i in range(N+1)])
    dp[0][0] = 0

    for i in range(N):
        w, v = wv[i]
        dp[i+1] = dp[i]
        dp[i+1, v:] = np.minimum(dp[i+1, v:], dp[i, :-v] + w)
    
    for i in range(1000, -1, -1):
        if dp[N][i] <= W:
            print(i)
            break

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

    INF = int(1e12)
    dp = np.array([[INF] * (1001) for i in range(N+1)])
    dp[0][0] = 0

    for i in range(N):
        w, v = wv[i]
        dp[i+1] = dp[i]
        dp[i+1, v:] = np.minimum(dp[i+1, v:], dp[i, :-v] + w)
    
    for i in range(1000, -1, -1):
        if dp[N][i] <= W:
            print(i)
            break

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
n, limit= map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


d = defaultdict(int)
dp = [d for _ in range(n)]

#初期状態
for w in range(L[0][0], limit+1):
    dp[0][w] = L[0][1]
#print(dp)
for i in range(1, n):
    for w in range(1, limit+1):
        if dp[i-1].get(w-L[i][0]) and dp[i-1].get(w): 
            dp[i][w] = max(dp[i-1][w-L[i][0]] + L[i][1], dp[i-1][w])
        elif dp[i-1].get(w) and w==L[i][0]:
            dp[i][w] = max(L[i][1], dp[i-1][w])
        elif dp[i-1].get(w):
            dp[i][w] = dp[i-1][w]
        elif w==L[i][0]:
            dp[i][w] = L[1][1]
    #print(dp)  
print(max(dp[-1].values()))

Submission status: Wrong Answer

Solution code:
N, W = [int(x) for x in input().split()]

w, v = [], []
MAX_V = 10100
INF = 100000000001

for i in range(N):
  wi, vi = [int(x) for x in input().split()]
  w.append(wi)
  v.append(vi)

dp = []
for i in range(N+1):
  dp.append([INF] * MAX_V)

dp[0][0] = 0

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


res = 0
for sum_v in range(MAX_V):
  if dp[N][sum_v] <= W:
    res = sum_v
  
print(res)

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
Data = [list(map(int, input().split())) for _ in range(N)]
sum_value_aploximate = N * 10**3

dp = [[None for _ in range(sum_value_aploximate)] for _ in range(N+1)]
temp = float("inf")
dp[0] = [temp for _ in range(sum_value_aploximate)]
dp[0][0] = 0

for i in range(1, N+1):
    for j in range(sum_value_aploximate):
        if Data[i-1][1] <= j:
            dp[i][j] = min(dp[i-1][j], (dp[i-1][j-Data[i-1][1]] + Data[i-1][0]))
        else:
            dp[i][j] = dp[i-1][j]

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

print(ans)

Submission status: Wrong Answer

Solution code:
import random
import copy
from collections import Counter

def get_population():
    population = []
    for i in range(individual_length):
        population.append([random.randint(0,1) for j in range(gene_length)])
    return population

def evaluate(pop):
    pop.sort(reverse=True)
    return pop

def two_point_crossover(parent1, parent2):
    r1 = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent1)
    child[r1:] = parent2[r1:]
    return child

def mutate(parent):
    r = random.randint(0, gene_length-1)
    child = copy.deepcopy(parent)
    child[r] = 1 if child[r] == 0 else 0
    return child

def fitness(pop):
    value = 0
    weight = 0
    for i in range(N):
        if pop[i]:
            value += L[i][1]
            weight += L[i][0]
    if weight <= W:
        return value
    else:
        return 0

N,W = [int(zz) for zz in input().split()]
L = [[0,0] for _ in range(N)]

ans = []
for i in range(N):
    p,q = [int(zz) for zz in input().split()]
    L[i][0] = p
    L[i][1] = q

gene_length = N
individual_length = 100
generation = 300
mutate_rate = 0.1
elite_rate = 0.2

pop = evaluate([(fitness(p), p) for p in get_population()])

for i_episode in range(generation):

    eva = evaluate(pop)
    elites = eva[:int(len(pop)*elite_rate)]

    pop = elites
    while len(pop) < individual_length:
        if random.random() < mutate_rate:
            m = random.randint(0, len(elites)-1)
            child = mutate(elites[m][1])
        else:
            m1 = random.randint(0, len(elites)-1)
            m2 = random.randint(0, len(elites)-1)
            child = two_point_crossover(elites[m1][1], elites[m2][1])
        pop.append((fitness(child), child))

eva = evaluate(pop)
print(eva[0][0])

Submission status: Wrong Answer

Solution code:
N,W = [int(x) for x in input().split()]
dp = [[10**9]*(10**5+1) for _ in range(N+2)]
uv = [[0,0]]+[[int(x) for x in input().split()] for _ in range(N)]
dp[0][0]=0
for i in range(N+1):
  for j in range(10**5+1):
    dp[i+1][j] = min(dp[i+1][j],dp[i][j])
    if uv[i][1]+j<=10**5:
      dp[i+1][j+uv[i][1]] = min(dp[i][j]+uv[i][0],dp[i+1][j+uv[i][1]])
ans = 0
for i in range(10**5+1):
  if 0<dp[N+1][i]<=W:
    ans = max(ans,i)
print(ans)

Submission status: Wrong Answer

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

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

INF = float('inf')
max_val=20
dp = [[INF]*(max_val) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for sum_val in range(max_val):
        if sum_val-wv[i][1] >= 0:
            dp[i+1][sum_val] = min(dp[i][sum_val], dp[i][sum_val-wv[i][1]]+wv[i][0])
        else:
            dp[i+1][sum_val] = dp[i][sum_val]

ans=0
for i in range(max_val):
    if dp[n][i]<=w:
        ans=i
print(ans)

Submission status: Wrong Answer

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

dp = [[0 for _ in range(maxw+1)] for _ in range(n+1)]
v_list, w_list = [], []

for i in range(n):
    _v, _w = map(int, input().split())
    v_list.append(_v)
    w_list.append(_w)

def check(idx, w):
    if dp[idx][w]>0:
        return dp[idx][w]
    if idx==n:
        return 0
    elif w_list[idx]>w:
        return check(idx+1,w)
    else:
        dp[idx][w] = max(check(idx+1, w-w_list[idx])+v_list[idx], check(idx+1,w))
        return dp[idx][w]

print(check(0, maxw))