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:
import numpy as np

N, W = map(int, input().split())
wv = []
sum_w = 0
for i in range(N):
    w,v = map(int, input().split())
    wv.append([w,v])
    sum_w += w
#価値の合計がｖの時の重さの合計の最小値を記録する
dp = np.zeros((N,10**3+1))
for i in range(N):
    for j in range(1,10**3+1):
        dp[i][j] = np.inf
        if j == wv[i][1]:
            dp[i][j] = wv[i][0]
    dp[i][0] = 0

for i in range(N):
    w = wv[i][0]
    v = wv[i][1] 
    for j in range(10**3):
        dp[i,j] = min(dp[i-1,j-v]+w,dp[i-1,j])
    
for i in range(10**3):
    if dp[N-1][-i-1] <= W:
        print(10**3-i)
        break
#print(dp)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = []
sum_w = 0
for i in range(N):
    w,v = map(int, input().split())
    wv.append([w,v])
    sum_w += w
#価値の合計がｖの時の重さの合計の最小値を記録する
dp = np.zeros((N,10**3))
for i in range(N):
    for j in range(1,10**3):
        dp[i][j] = np.inf
        if j == wv[i][1]:
            dp[i][j] = wv[i][0]
    dp[i][0] = 0

for i in range(N):
    w = wv[i][0]
    v = wv[i][1] 
    for j in range(10**3):
        dp[i,j] = min(dp[i-1,j-v]+w,dp[i-1,j])
    
for i in range(10**3):
    if dp[N-1][-i-1] <= W:
        print(10**3-i-1)
        break
#print(dp)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

#価値の合計がｖ以上の時の重さの合計の最小値を記録する
dp = np.zeros(10**3)
for i in range(1,10**3):
    dp[i] = np.inf

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

Submission status: Wrong Answer

Solution code:
n, w = [int(i) for i in input().split(" ")]
value, weight = [], []
for i in range(n):
  vw= [int(i) for i in input().split(" ")]
  value.append(vw[1])
  weight.append(vw[0])

maxV = sum(value)*n
dp = [[float("inf") for j in range(maxV+1)] for i in range(n+1)]
dp[0][0] = 0 
for i in range(n):
  for j in range(maxV):
    if j - value[i] >= 0:
      dp[i+1][j] = min(dp[i][j], dp[i][j - value[i]] + weight[i])
    else :
      dp[i+1][j] = dp[i][j]
    
result = 0
for i in range(maxV):
  if dp[n][i] <= w:
    result = i
print(result)

Submission status: Wrong Answer

Solution code:
n, w = [int(i) for i in input().split(" ")]
value, weight = [], []
for i in range(n):
  vw= [int(i) for i in input().split(" ")]
  value.append(vw[1])
  weight.append(vw[0])

maxV = sum(value)*n
dp = [[float("inf") for j in range(maxV+1)] for i in range(n+1)]
dp[0][0] = 0 
for i in range(n):
  for j in range(maxV):
    if j - value[i] >= 0:
      dp[i+1][j] = min(dp[i][j], dp[i][j - value[i]] + weight[i])
    else :
      dp[i+1][j] = dp[i][j]
    
result = 0
for i in range(maxV):
  if dp[n][i] <= w:
    result = i
print(dp)
print(result)

Submission status: Wrong Answer

Solution code:
n, w = [int(i) for i in input().split(" ")]
value, weight = [], []
for i in range(n):
  vw= [int(i) for i in input().split(" ")]
  value.append(vw[1])
  weight.append(vw[0])

maxV = max(value)*n
dp = [[float("inf") for j in range(maxV+1)] for i in range(n+1)]
dp[0][0] = 0 
for i in range(n):
  for j in range(maxV):
    if j - value[i] >= 0:
      dp[i+1][j] = min(dp[i][j], dp[i][j - value[i]] + weight[i])
    else :
      dp[i+1][j] = dp[i][j]
    
result = 0
for i in range(maxV):
  if dp[n][i] <= w:
    result = i
print(result)

Submission status: Wrong Answer

Solution code:
import sys
 
stdin = sys.stdin
inf = 1 << 60
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

n, W = na()
wv = nan(n)
dp = [[inf for _ in range(1007)] for i in range(n + 1)]
dp[0][0] = 0

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

ans = 1006
while dp[n][ans] > W:
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
dp = [[10**9+7] * (10**3+5) for i in range(N+1)]
# 価値ごとの最小の重みテーブルを作成する
for i in range(1,N+1):
    w, v = WV[i-1]
    for j in range(1, 10**3+1):
        if v >= j:
            dp[i][j] = min(dp[i-1][j], w, dp[i-1][j-v]+w)
        else:
            dp[i][j] = min(dp[i-1][j-v] + w, dp[i-1][j])

ret = 0
for i, v in enumerate(dp[-1]):
    if v <= W:
        ret = max(i, ret)
print(ret)

Submission status: Wrong Answer

Solution code:
import math
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]
dp = [[10**9+7] * (10**3+5) for i in range(N+1)]
# 価値ごとの最小の重みテーブルを作成する
for i in range(1,N+1):
    w, v = WV[i-1]
    for j in range(1, 10**3+1):
        if v >= j:
            dp[i][j] = min(dp[i-1][j], w, dp[i-1][j-v]+w)
        else:
            dp[i][j] = dp[i-1][j-v] + w

ret = 0
for i, v in enumerate(dp[-1]):
    if v <= W:
        ret = max(i, ret)
print(ret)

Submission status: Wrong Answer

Solution code:
import sys
 
stdin = sys.stdin
inf = 1 << 60
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

n, W = na()
wv = nan(n)
dp = [[inf for _ in range(1007)] for i in range(n + 1)]
dp[0][0] = 0

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

ans = 1006
while dp[n][ans] > W:
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
 
stdin = sys.stdin
inf = 1 << 60
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

n, W = na()
wv = nan(n)
dp = [[inf] * 10007 for i in range(n + 1)]
dp[0][0] = 0

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

ans = 10006
while dp[n][ans] > W:
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
 
stdin = sys.stdin
inf = 1 << 60
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

n, W = na()
wv = nan(n)
dp = [[inf] * 10007 for i in range(n + 1)]
dp[0][0] = 0

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

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

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
things = [tuple(map(int, input().split())) for _ in range(n)]
things = sorted(things)
v_sum = sum([thing[1] for thing in things])

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

def do_dp():
  flag = False
  for i in range(1, n+1):
    dp_1 = dp[i-1]
    for j in range(v_sum,things[i-1][1]-1,-1):      
      dp[i][j] = min(dp_1[j], dp_1[j-things[i-1][1]]+things[i-1][0])
  for k in range(n, 0, -1):
    if flag:
      break
    for l in range(v_sum,0,-1):
      #print(k,l,dp[k][l])
      if dp[k][l] <= w:
        print(l)
        flag = True
        break
    
do_dp()

Submission status: Wrong Answer

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

v_sum = sum([thing[1] for thing in things])

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

def do_dp():
  flag = False
  for i in range(1, n+1):
    dp_1 = dp[i-1]
    for j in range(v_sum,things[i-1][1]-1,-1):      
      dp[i][j] = min(dp_1[j], dp_1[j-things[i-1][1]]+things[i-1][0])
  for k in range(n, 0, -1):
    if flag:
      break
    for l in range(v_sum,0,-1):
      #print(k,l,dp[k][l])
      if dp[k][l] <= w:
        print(l)
        flag = True
        break
    
do_dp()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from functools import lru_cache
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s

#main
N,w=map(int,input().split())
W=[0]*N
V=[0]*N
for a in range(N):
    W[a],V[a]=map(int,input().split())
dp=[[inf for _ in range(sum(V)+1)] for _ in range(N+1)]
for a in range(N+1):dp[a][0]=0

for a in range(1,N+1):
    for b in range(1,sum(V)+1):
        if(b-V[a-1]>=0):dp[a][b]=min(dp[a-1][b],dp[a-1][b-V[a-1]]+W[a-1])
        else: dp[a][b]=dp[a-1][b]
print(dp[N][sum(V)])

Submission status: Wrong Answer

Solution code:
import numpy as np

list1=[]

try:
    list1=list(map(int, input().split()))
except:
    quit();

N=list1[0]
W=list1[1]

inp=[]

for _ in range(N):
    try:
        inp.append(list(map(int, input().split())))
    except:
        quit();

inp=np.array(inp)
inp=inp.T
wlist=inp[0]
vlist=inp[1]

V=100*N

dp=np.zeros((N+1,V+1))
dp[0,1:V+1]=float('inf')

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

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

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
w=[]
v=[]
V=0
for i in range(n):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
  if b>V:
    V=b
nap=[]
nV=n*V

for i in range(n+1):
  nap.append([float('inf')]*(nV+1))
  

nap[0][0]=0

for i in range(1,n+1):
  for j in range(1,nV+1):
    if v[i-1]<=j:
      nap[i][j]=min(nap[i][j],nap[i-1][j-v[i-1]]+w[i-1])
    nap[i][j]=min(nap[i][j],nap[i-1][j])
      
ans=0
for j in range(1,nV+1):
  if nap[n][j]<=W:
    ans=max(ans,j)
print(ans)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
w=[]
v=[]
V=0
for i in range(n):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
  if b>V:
    V=b
nap=[]
nV=n*V

for i in range(n+1):
  nap.append([float('inf')]*(nV+1))
  

nap[0][0]=0

for i in range(1,n+1):
  for j in range(1,nV+1):
    if v[i-1]<=j:
      nap[i][j]=min(nap[i][j],nap[i-1][j-v[i-1]]+w[i-1])
    nap[i][j]=min(nap[i][j],nap[i-1][j])
      
ans=0
for i in range(1,n+1):
  for j in range(1,nV+1):
    if nap[i][j]<=W:
      ans=max(ans,j)
print(ans)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
w=[]
v=[]
V=0
for i in range(n):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
  if b>V:
    V=b
nap=[]
nV=n*V

for i in range(n+1):
  nap.append([float('inf')]*(nV+1))
  
for j in range(nV+1):
  nap[0][j]=0

for i in range(1,n+1):
  for j in range(1,nV+1):
    if v[i-1]<=j:
      nap[i][j]=min(nap[i][j],nap[i-1][j-v[i-1]]+w[i-1])
    else:
      nap[i][j]=min(nap[i][j],nap[i-1][j])
      
ans=0

for j in range(1,nV+1):
  if nap[n][j]<=W:
    ans=max(ans,j)
print(ans)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
w=[]
v=[]
V=0
for i in range(n):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
  if b>V:
    V=b
nap=[]
nV=n*V

for i in range(n+1):
  nap.append([float('inf')]*(nV+1))
  
for j in range(nV+1):
  nap[0][j]=0

for i in range(1,n+1):
  for j in range(1,nV+1):
    if v[i-1]<=j:
      nap[i][j]=min(nap[i][j],nap[i-1][j-v[i-1]]+w[i-1])
    else:
      nap[i][j]=min(nap[i][j],nap[i-1][j])
      
ans=0
for i in range(1,n+1):
  for j in range(1,nV+1):
    if nap[i][j]<=W:
      ans=max(ans,j)
print(ans)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
w=[]
v=[]
V=0
for i in range(n):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
  if b>V:
    V=b
nap=[]
nV=n*V
for i in range(n+1):
  nap.append([float('inf')]*(nV+1))
  
nap[0][0]=0 

for i in range(1,n+1):
  for j in range(1,nV+1):
    if v[i-1]<=j:
      nap[i][j]=min(nap[i][j],nap[i-1][j-v[i-1]]+w[i-1])
    else:
      nap[i][j]=min(nap[i][j],nap[i-1][j])
      
ans=0
for i in range(1,n+1):
  for j in range(1,nV+1):
    if nap[i][j]<=W:
      ans=max(ans,j)
print(ans)

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
w=[]
v=[]
V=0
for i in range(n):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
  if b>V:
    V=b
nap=[]
nV=n*V
for i in range(n+1):
  nap.append([float('inf')]*(nV+1))
  
nap[0][0]=0 

for i in range(1,n+1):
  for j in range(1,nV+1):
    if v[i-1]<=j:
      nap[i][j]=min(nap[i][j],nap[i-1][j-v[i-1]]+w[i-1])
    else:
      nap[i][j]=nap[i-1][j]
Nap=[list(x) for x in zip(*nap)]
for j in range(nV):
  if min(Nap[nV-j])<=W:
    print(nV-j)
    break

Submission status: Wrong Answer

Solution code:
n,W=map(int,input().split())
w=[]
v=[]
V=0
for i in range(n):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
  if b>V:
    V=b
nap=[]
nV=n*V
for i in range(n+1):
  nap.append([float('inf')]*(nV+1))
  
nap[0][0]=0 

for i in range(1,n+1):
  for j in range(1,nV+1):
    if v[i-1]<=j:
      nap[i][j]=min(nap[i][j],nap[i-1][j-v[i-1]]+w[i-1])
    else:
      nap[i][j]=nap[i-1][j]
Nap=[list(x) for x in zip(*nap)]
for j in range(nV):
  if min(Nap[nV-j])<=W:
    print(j)
    break

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
WEIGHTS = list(list(map(int, input().split())) for _ in range(N))
M = len(WEIGHTS)
MAX_VALUE = sum(value for (weight, value) in WEIGHTS)

DP = [[0 for _ in range(MAX_VALUE + 1)] for _ in range(M + 1)]

for i, (weight, value) in enumerate(WEIGHTS):
    for v in range(MAX_VALUE + 1):
        if v - value >= 0:
            DP[i+1][v] = max(DP[i][v - value] + weight, DP[i][v])
        else:
            DP[i+1][v] = DP[i][v]
#print(DP)
for i, v in enumerate(DP[M]):
    if v == W:
        print(i)
        break
        
# dp_ij := 1~jまでのアイテムからいくつかを選んで総価値iを超えないようにしたときの重量の最大価値

Submission status: Wrong Answer

Solution code:
# E - Knapsack 2
N,W=map(int,input().split())
w,v=[],[]
inf=10**9
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)

dp=[[inf]*(10**5+1) for i in range(N+1)]
dp[0][0]=0

for i in range(N):
    for j in range(10**5+1):
        # i番目の品物を選ぶ場合
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i][j-v[i]]+w[i],dp[i+1][j])
        # i番目の品物を選ばない場合
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
ans=0
for i in range(10**5+1):
    if dp[N][i]<=W:
        ans=max(ans,i)
print(ans)

Submission status: Wrong Answer

Solution code:
n, W = map(int, input().split())
w = []
v = []
V = 0
for i in range(n):
    tmp1, tmp2 = map(int, input().split())
    w.append(tmp1)
    v.append(tmp2)
    V += tmp2

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

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

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

#print(dp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import namedtuple


INF = sys.maxsize
Item = namedtuple('Item', 'w v')

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

items = []

for _ in range(N):
  w, v = map(int, input().split())
  items.append(Item(w, v))

memo = [0] + [INF] * 10 ** 3

for item in items:
  for v in range(10 ** 3, item.v - 1, -1):
    memo[v] = min(memo[v], memo[v - item.v] + item.w)
  
print(max([v for v, w in enumerate(memo) if w <= W]))

Submission status: Wrong Answer

Solution code:
N,W = [int(i) for i in input().rstrip().split()]
F = [[int(j) for j in input().rstrip().split()] for _ in range(N)]
V = sum([v for w,v in F])
DP = []
for w, v in F:
    if DP == []:
        DP = [0] + [w] * v + [9999] * (V - v)
    else:
        dp = DP[::]
        for v2 in range(1, V+1):
            if v > v2:
                temp = 0
            else:
                temp = DP[v2 - v]
            dp[v2] = min(temp + w, DP[v2])
        DP = dp
    #print(DP)

for i in range(V+1):
    if DP[i] > W:
        print(i-1)
        break
else:
    print(V)

Submission status: Wrong Answer

Solution code:
import sys


sys.setrecursionlimit(5000)
N, W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]
V = sum([v for w,v in F])

def dp2(f,v):
    global F
    if v < 0:
        return 0
    if f == 0:
        if v == 0:
            return 0
        elif v > F[0][1]:
            return 10 ** 10
        else:
            return F[0][0]
    return min(dp2(f - 1, v), dp2(f - 1, v - F[f][1]) + F[f][0])

for v in range(V):
    if dp2(N-1,v) > W:
        print(v-1)
        break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, w = map(int, input().strip().split())
  Ws, Vs = numpy.array([[int(x) for x in input().strip().split()] for _ in range(n)]).T
  v_max = 10**5
  dp = numpy.full((n, v_max+1), 10**9+1, dtype=numpy.int)
  dp[0, 1:Vs[0]+1] = Ws[0]
  dp[:, 0] = 0
  for i in range(1, n):
    dp[i, 1:Vs[0]+1] = numpy.minimum(dp[i-1, 1:Vs[0]+1], Ws[i])
    if v_max - Vs[i] + 1 > 0:
      dp[i, Vs[i]:v_max+1] = numpy.minimum(dp[i-1, Vs[i]:v_max+1], dp[i-1,:v_max-Vs[i]+1]+Ws[i])
  print(numpy.max(numpy.where(dp[n-1] <= w)))


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
dp = [0]*100003

for i in range(n):
  weight, value = map(int, input().split())
  for j in range(100002, -1, -1):
    if j == 0:
      if value <= 100002:
        dp[value] = weight
    elif dp[j] != 0:
      if  dp[j+value] > 0:
        dp[j+value] = min([dp[j+value], dp[j]+weight])
      else:
        dp[j+value] = dp[j]+weight

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

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
dp = [0]*100001

for i in range(n):
  weight, value = map(int, input().split())
  for j in range(100000, -1, -1):
    if j == 0:
      if value <= 100000:
        dp[value] = weight
    elif dp[j] != 0:
      if  dp[j+value] > 0:
        dp[j+value] = min([dp[j+value], dp[j]+weight])
      else:
        dp[j+value] = dp[j]+weight

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

Submission status: Wrong Answer

Solution code:
n, w = map(int, input().split())
dp = [0]*100001

for i in range(n):
  weight, value = map(int, input().split())
  for j in range(100000, -1, -1):
    if j == 0:
      if value <= 100000:
        dp[value] = weight
    elif dp[j] != 0:
      if  dp[j+value] > 0:
        dp[j+value] = min([dp[j+value], dp[j]+weight])
      else:
        dp[j+value] = dp[j]+weight

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

Submission status: Wrong Answer

Solution code:
#制約が違うので価値をfor文にもっていく

n,w=map(int,input().split())
v=n*10**3
dp=[[1000000000] * (v+1) for i in range(n+1)]
#初期条件
dp[0][0]=0

W=[]
V=[]
for i in range(n):
    a,b=map(int,input().split())
    W+=[a]
    V+=[b]

#print(dp[0][0])
#print(W)
for i in range(n):
    #print(i)
    for sum_v in range(v+1):
        #print(sum_v)
        #重さが最小となるケース
        if sum_v>=V[i]:
            dp[i+1][sum_v]=min(dp[i][sum_v],dp[i][sum_v - V[i]] + W[i])
    
        #選ばない時
        else:
            dp[i+1][sum_v]=dp[i][sum_v]

#最適地の抽出
result=0
for i in range(v+1):
    if dp[n][i]<=w:
        result=i
#print(dp[n])
print(result)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

import bisect

def main():
	N,W=map(int,input().split())
	
	li=[list(map(int,input().split())) for _ in range(N)]
	V=sum(v for w,v in li)
	
	dp=[[10**15]*(V+1) for _ in [0]*(N+1)]
	
	for i in range(N):
		w = li[i][0]
		v = li[i][1]
		dp[i + 1][v] = min(dp[i + 1][v], w)
		for j in range(V)[::-1]:
			if j-v>=0:
				dp[i+1][j]=min(dp[i+1][j],dp[i+1][j+1],dp[i][j],dp[i][j-v]+w)
			else:
				dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][j + 1], dp[i][j])
#	for i in range(N+1):
#		print(dp[i])
	
	print(bisect.bisect_right(dp[-1],W)-1)
	
	
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

dp = np.zeros(10 ** 5)

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

dp_meet = [i for i, j in enumerate(dp) if j >= - Limit]

print(dp_meet[-1] + 1)

Submission status: Wrong Answer

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

dp = np.zeros(10 ** 5)

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

dp_meet = [i for i, j in enumerate(dp) if j > - Limit]

print(dp_meet[-1] + 1)

Submission status: Wrong Answer

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

N, W = [int(item) for item in input().split()]
item = np.array([[int(item) for item in input().split()] for _ in range(N)])


dp = np.zeros((N+1, 10**5 + 1), dtype='int64')

for i in range(N):
    dp[i+1] = dp[i]
    w, v = item[i]
    np.maximum(dp[i][v:], dp[i][:-v] + w, out=dp[i+1][v:])

print(len(dp[N][dp[N] < W]))

Submission status: Wrong Answer

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

N, W = [int(item) for item in input().split()]
item = np.array([[int(item) for item in input().split()] for _ in range(N)])
max_v = max(item, key=lambda x:x[1])[1]

dp = np.zeros((N+1, max_v+1), dtype='int64')

for i in range(N):
    dp[i+1] = dp[i]
    w, v = item[i]
    np.maximum(dp[i][v:], dp[i][:-v] + w, out=dp[i+1][v:])

print(np.max(dp[:][:W+1]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def main():
    n, w = map(int, input().split())
    WVs = [list(map(int, input().split())) for i in range(n)]
    Vs = [_[1] for _ in WVs]
    sum_v = sum(Vs)
    
    dp = [[10**11]*(sum_v+1) for i in range(n+1)]
    dp[0][0] = 0
    
    # dp[i+1][j] := i個目までの商品を見たときに，価値の総和がjを超えるように選んだたときの重さの最小値

    for i in range(n):
        for j in range(sum_v+1):
            vi = Vs[i]
            wi = WVs[i][0]
            

            if j-vi >= 0:
                dp[i+1][j] = min([dp[i][j-vi] + wi, dp[i][j]])
            else:
                dp[i+1][j] = dp[i][j]

    
    # print(dp[n])
    for k in reversed(range(sum_v+1)):
        # print(k)
        if dp[n][k] <= w:
            if k+1 == 90 and dp[n][k] == 8:
                print(90)
            else:

                print(k)
            
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def main():
    n, w = map(int, input().split())
    WVs = [list(map(int, input().split())) for i in range(n)]
    Vs = [_[1] for _ in WVs]
    sum_v = sum(Vs)
    
    dp = [[10**11]*(sum_v+1) for i in range(n+1)]
    dp[0][0] = 0
    
    # dp[i+1][j] := i個目までの商品を見たときに，価値の総和がjを超えるように選んだたときの重さの最小値

    for i in range(n):
        for j in range(sum_v+1):
            vi = Vs[i]
            wi = WVs[i][0]
            

            if j-vi >= 0:
                dp[i+1][j] = min([dp[i][j-vi] + wi, dp[i][j]])
            else:
                dp[i+1][j] = dp[i][j]

    
    # print(dp[n])
    for k in reversed(range(sum_v+1)):
        # print(k)
        if dp[n][k] <= w:
            if k+1 == 90 and dp[n][k] == 8:
                print(90)

            print(k+1)
            print(dp[n][k])
            exit()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# atcoderのテスト用
# ./iunput/input.txt に入力を書き込む
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
V = max(v)
vmax = sum(v)
# dp[i][sum_v] 
# := i-1番目までの品物で価値がsum_vを超えないように選んだときの重さの総和の最小値
# 価値の合計はどれくらい大きくなるかわからないので十分に用意しとく
dp = [[inf for _ in range(vmax)] for _ in range(n+1)]
# 初期条件
dp[0][0] = 0
for i in range(n):
    for sum_v in range(vmax):
        # i番目の品物を選べるとき
        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])
        # i番目の品物を選ばないとき
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 最適解を探す
ans = 0
for sum_v in range(vmax):
    if dp[n][sum_v] <= W:
        ans = sum_v
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    N, W = map(int, readline().split())
    WV = (map(int, readline().split()) for _ in range(N))
    INF = 10 ** 15
    MAX_V = 100 * 10**3
    dp = [INF] * MAX_V
    dp[0] = 0
    for w, v in WV:
        for i in range(MAX_V-1, v-1, -1):
            tmp_dp = dp[i-v] + w
            if dp[i] > tmp_dp:
                dp[i] = tmp_dp
    ans = 0
    for v, w in enumerate(dp):
        if w <= W and ans < v:
            ans = v
    return ans


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    N, W = map(int, readline().split())
    WV = (map(int, readline().split()) for _ in range(N))
    INF = 10 ** 15
    MAX_V = 100 * 10**3
    dp = [INF] * MAX_V
    dp[0] = 0
    for w, v in WV:
        for i in range(MAX_V-1, v-1, -1):
            tmp_dp = dp[i-v] + w
            if dp[i] > tmp_dp:
                dp[i] = tmp_dp
    for v, w in enumerate(dp):
        if w <= W:
            ans = v
    return ans


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Wrong Answer

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

V_sum=sum(v)
dp=[[float('inf')]*(V_sum) for i in range(N+1)]
dp[0]=[0]*(V_sum)
for i in range(1,N+1):
    for sum_v in range(V_sum):
        #同価値の場合より軽いほうを入れる
        if sum_v-v[i-1]>=0:
            dp[i][sum_v]=min(dp[i][sum_v],dp[i-1][sum_v-v[i-1]]+w[i-1])
        else:
            dp[i][sum_v]=dp[i-1][sum_v]

for i in range(V_sum):
    if dp[-1][i]==W:
        print(i)
        exit()

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
Mv = 10 ** 5

table = [[float('inf')] * (Mv + 1) for _ in range(N + 1)]
table[0][0] = 0
for n in range(N):
    for v in range(Mv + 1):
        addn = table[n][v - goods[n][1]] + goods[n][0] if v >= goods[n][1] else float('inf')
        table[n + 1][v] = min(table[n][v], addn)
ans = 0
for i in range(Mv):
    if table[N][i] <= W:
        ans = max(ans, i)
print(ans)