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^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

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

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

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: Runtime Error

Solution code:
from __future__ import division, print_function
# import threading
# threading.stack_size(2**27)
# import sys
# sys.setrecursionlimit(10**7)
from sys import stdin, stdout
import bisect            #c++ upperbound
import math
import heapq
import numpy
i_m=9223372036854775807
def modinv(n,p):
    return pow(n,p-2,p)
def cin():
    return map(int,sin().split())
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
import math  
def GCD(x, y): 
    x=abs(x)
    y=abs(y)
    if(min(x,y)==0):
        return max(x,y)
    while(y): 
        x, y = y, x % y 
    return x 
def Divisors(n) : 
    l = []  
    for i in range(1, int(math.sqrt(n) + 1)) :
        if (n % i == 0) : 
            if (n // i == i) : 
                l.append(i) 
            else : 
                l.append(i)
                l.append(n//i)
    return l
prime=[]
def SieveOfEratosthenes(n): 
    global prime
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime[p]: 
            f.append(p)
    return f
q=[]       
def dfs(n,d,v,c):
    global q
    v[n]=1
    x=d[n]
    q.append(n)
    j=c
    for i in x:
        if i not in v:
            f=dfs(i,d,v,c+1)
            j=max(j,f)
            # print(f)
    return j
    
"""*******************************************************"""
def main():
    dp = np.full(10**5+1, 10**18, dtype=np.int64)
    n,w=map(int,input().split())
    val=[0]*n
    wt=[0]*n
    dp=[[0 for x in range(w+1)] for x in range(n+1)] 
    for i in range(n):
      a,b=map(int,input().split())
      wt[i]=a
      val[i]=b
    for i in range(1,n+1):
        for j in range(1,w+1):
            if(wt[i-1] <= j):
                dp[i][j]=max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j])
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[n][w])
######## Python 2 and 3 footer by Pajenegod and c1729
 
# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.
 
# So on cf, use PyPy2 for best string performance.
 
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'
 
# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'R' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'R' [0]:
        A.append(sign*numb)
    return A
 
# threading.Thread(target=main).start()
if __name__== "__main__":
  main()

Submission status: Runtime Error

Solution code:
v

Submission status: Runtime Error

Solution code:
def knapsack(weight,profit,capacity,no):
    if no == 0 or capacity == 0:
        dp[no][capacity] =  0
    
    elif dp[no][capacity] != -1:
        return dp[no][capacity]
    
    elif weight[no-1] <= capacity:
         dp[no][capacity] = max(profit[no-1] + knapsack(weight,profit,capacity-weight[no-1],no-1),
                   knapsack(weight,profit,capacity,no-1))
    else: #weight[no-1] > capacity:
        dp[no][capacity] = knapsack(weight,profit,capacity,no-1)
        
    return dp[no][capacity]
    
n,W = map(int,input().split())
w,v = [],[]
for _ in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
    #n -= 1
print(knapsack(w,v,W,n))

Submission status: Runtime Error

Solution code:
def dp(w,wt,val,n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W]

n,w = list(map(int,input().split()))
val = []
wt = []
for _ in range(n):
    p,q = list(map(int,input().split()))
    wt.append(p)
    val.append(q)

print(dp(w,wt,val,n))

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
dp=[[0 for j in range(w+1)] for i in range(n+1)]
for i in range(n):
  for j in range(w+1):
    dp[i+1][j]=max(dp[i][j],dp[i][j-l[i][o]]+l[i][1])
print(dp[n][w])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
w=[]
v=[]
for i in range(N):
  x,y = map(int,input().split())
  w.append(x)
  v.append(y)
ans = [0]
def knap(index,W,temp):
	#base case 
    if index == len(w):
      	ans[0] = max(ans[0],temp)
    if W - w[index] >= 0:
  		return max(v[index]+knap(index + 1,W-w[index],temp+v[index]) , knap(index+1 , W,temp))
	else:
      return knap(index+1,W,temp)
knap(0,W,0)
print(ans[0])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)] #1-index

# dp[i+1][w]: i番目までの品物を選びその重さがwを超えないときの最大価値
dp = [[0]*(W+10) for _ in range(N+10)]

for i in range(N):
    for w in range(W+1):
        dp[i+1][w] = dp[i][w]
        
        if w - wv[i][0] >= 0:
            dp[i+1][w] = chmax(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w])

print(dp[N][W])

Submission status: Runtime Error

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

    # min -> inf, max -> -1
    dp = [[-1]*(w+1) for _ in range(n+1)]

    # shoki joken
    dp[0] = [0]*(w+1)
    for i in range(n):
        for j in range(w+1):
            # i select or not select
            if j-wv[i][0] >= 0:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = dp[i][j]

    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,W=[int(i) for i in input().split()]
w=[]
v=[]
for i in range(N):
    a,b=[int(i) for i in input().split()]
    w.append(a)
    v.append(b)
dic={}
for i in range(N):
    dic[v[i]]=w[i]
v.sort()
val=0
wei=0
i=N-1
while wei<W:
    if wei+dic[v[i]]<=W:
         wei+=dic[v[i]]
         val+=v[i]
    i-=1
print(val)

Submission status: Runtime Error

Solution code:
import numpy as np
n, W = map(int, input().split())
dp = np.zeros((n,W+1), dtype='int64')

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

    # print("left", dp[i, :w])
    # print("right", dp[i-1, :w])
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.fmax(dp[i-1, w:], dp[i-1,:W-w+1]+v)

    print(dp[i])
# print(dp[n-1][W])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import java.util.*;
import java.lang.*;
import java.io.*;
//import java.util.stream.Collectors;
public class Main
{
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

     public static Reader sc = new Reader();
//    public static Scanner sc = new Scanner(System.in);
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
//    public static OutputStream out2 = new BufferedOutputStream (System.out);
    public static int n, m, i, j, k, mod = (int)1e9+7;
    public static int[][] arr = new int[100005][2];
    public static long[][] dp = new long[100005][101];
    public static void main(String[] args) throws IOException
    {
        n = sc.nextInt();
        int w = sc.nextInt();
        for(i = 0; i < n; i++)
            for(j = 0; j < 2; j++)
                arr[i][j] = sc.nextInt();
        for(i = 1; i <= w; i++)
        {
            for(j = n-1; j >= 0; j--)
            {
                dp[i][j] = Math.max(dp[i][j], dp[i][j+1]);
                if(i-arr[j][0] >= 0)
                    dp[i][j] = Math.max(dp[i][j], dp[i-arr[j][0]][j+1]+arr[j][1]);
            }
        }
        out.write(dp[w][0]+"");
        out.flush();
    }
}

Submission status: Runtime Error

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

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

def solve(N, W): 
    for i in range(0, N):
        wi, vi = map(int, input().split())
        dp_next = [0] * (W+1)
        for w in range(1, W+1):
            if w >= wi:
                dp_next[w] = max(dp[w - wi] + vi, dp[w])
            else:
                dp_next[w] = dp[w]
        dp = dp_next
    return dp[-1]

print(solve(N, W))

Submission status: Runtime Error

Solution code:
def main():
    n,w = map(int, input().split())
    weight = []
    value = []
    for i in range(n):
        wi, vi = map(int, input().split())
        weight.append(wi)
        value.append(vi)
    
    def chmax(a, b):
        if a < b:
            a = b
        return a
    
    dp = [[0 for i in range(110)] for j in range(100100)]

    for i in range(n):
        for sum_w in range(w + 1):
            if sum_w - weight[i] >= 0:
                dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w - weight[i]] + value[i])

            dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w])

    print(dp[n][w])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros((w + 1, n))
dp[w[0, 0] :, 0] = np.full(dp[w[0, 0] :, 0].shape, w[0, 1])
for i in range(1, n):
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i, 0], wv[i, 1]
    dp[wNew:, :] = np.fmax(dp[wNew:, :], vNew + dp[:-wNew, :])

print(dp[w, n - 1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros((w + 1, n))
dp[w[0, 0]:, 0] = wv[0, 1]
for i in range(1, n):
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i, 0], wv[i, 1]
    dp[wNew:, :] = np.fmax(dp[wNew:, :], vNew + dp[:-wNew, :])

print(dp[w, n - 1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros((w + 1, n))
dp[:, wv[0, 0]] = wv[0, 1]
for i in range(1, n):
    dp[:, i] = dp[:, i - 1]
    wNew, vNew = wv[i, 0], wv[i, 1]
    dp[wNew:, :] = np.fmax(dp[wNew:, :], vNew + dp[:-wNew, :])

print(dp[w, n - 1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(40000000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4000000000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))

Submission status: Runtime Error

Solution code:
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W 
def knapSack(W, wt, val, n): 
	K = [[0 for x in range(W+1)] for x in range(n+1)] 

	# Build table K[][] in bottom up manner 
	for i in range(n+1): 
		for w in range(W+1): 
			if i==0 or w==0: 
				K[i][w] = 0
			elif wt[i-1] <= w: 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) 
			else: 
				K[i][w] = K[i-1][w] 

	return K[n][W] 




q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  




print(knapsack(W,w,v,n))

Submission status: Runtime Error

Solution code:

def knapsack(W,v,w,n,d):
    
    if n<0:
        return 0
    
    if d[W][n]!=-1:
        return d[W][n]
    if w[n]>W:
        d[W][n]=knapsack(W,v,w,n-1,d)
        return d[W][n]
    else:
        d[W][n]=max(v[n]+ knapsack(W-w[n],v,w,n-1,d),knapsack(W,v,w,n-1,d))
        return d[W][n]


q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[-]=r[1]
  



d=[[-1 for j in range(n+1)] for i in range(W+1)]
print(knapsack(W,v,w,n-1,d))

Submission status: Runtime Error

Solution code:
import numpy as np

N,W = map(int,input().split())
"""
DP = np.zeros(W+1,dtype=int)
for _ in range(N):
  w,v = map(int,input().split())
  np.maximum(DP[:-w]+v,DP[w:],out=DP[w:])
print(DP.max())
"""
DP= np.full(N*10000000+1,W+1)
DP[0] = 0
for _ in range(N):
  w,v = map(int,input().split())
  np.minimum(DP[:-v]+w,DP[v:],out = DP[v:])
print(np.max(np.where(DP<=W)))

Submission status: Runtime Error

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

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

for i in range(1, N+1):
    for w in range(1, W+1):
        if wv[i][0] <= w:
            dp[i][w] = max(dp[i][w], dp[i][w-wv[i-1][0]] + wv[i-1][1])
        dp[i][w] = max(dp[i][w], dp[i-1][w])

print(dp[N][W])

Submission status: Runtime Error

Solution code:
import sys
from numba import jit

@jit
def main():
  input = sys.stdin.readline
  
  N, W = map(int, input().split())
  L = [list(map(int,input().split())) for i in range(N)]
  dp = [[0] * (W + 1) for i in range(N + 1)]
  
  for i in range(N):
    weight = L[i][0]
    value = L[i][1]
    for w in range(W + 1):
      if w >= weight:
        dp[i + 1][w] = max(dp[i][w],dp[i][w - weight] + value)
      else:
        dp[i + 1][w] = dp[i][w]
        
  print(dp[-1][W])

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
n,ww=map(int,input().split())
waight=[0]
value=[0]
for _ in range(n):
    a,b=map(int,input().split())
    waight.append(a)
    value.append(b)
dp=[[0]*(ww+1) for _ in range(n+1)]
for i in range(n):
    for w in range(ww+1):
        if w-waight[i+1]>=0:
            dp[i+1][w]=max(dp[i][w],dp[i][w-waight[i+1]]+value(i+1))
        else:
            dp[i+1][w]=dp[i][w]
print(dp[-1][-1])

Submission status: Runtime Error

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

dp = [[0] * (W + 5) for _ in range(100)]

for i in range(N):
    for j in range(W + 1):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if 0 <= j - wt[i]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - wt[i]] + vt[i])
# print(dp)
print(dp[N][W])

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[float('inf')]*(N+1)
dp[0]=0
for i in range(N-1):
    for j in range(1,K+1):
        if i+j>N-1:
            break
        else:
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
print(dp[N-1])

Submission status: Runtime Error

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

dp = [[0]*(W+1) for j in range(N)]

for i in range(N-1,-1,-1):
    for j in range(W+1):
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][W])

Submission status: Runtime Error

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


wv=[list(map(int, input().split())) for i in range(n)]
dp=[[0]*(w+1) for _ in range(n)]


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



print(max(dp[n-1][w]))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))

Submission status: Runtime Error

Solution code:
def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1): 
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
  
n, W = map(int, input().split()) 
val = [] 
wt = [] 

for _ in range(n):
	w, v = map(int, input().split()) 
    val.append(v)
    wt.append(w)

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

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

// 入力
int n, W;
int weight[110], value[100010];

// DPテーブル
int dp[110][100010];

int main() {
  cin >> n >> W;
  for (int i = 0; i < n; ++i) cin >> value[i] >> weight[i];

  // DP初期条件: dp[0][w] = 0
  for (int w = 0; w <= W; ++w) dp[0][w] = 0;

  // DPループ
  for (int i = 0; i < n; ++i) {
    for (int w = 0; w <= W; ++w) {
      if (w >= weight[i]) dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w]);
      else dp[i+1][w] = dp[i][w];
    }
  }

  cout << dp[n][W] << endl;
}

Submission status: Runtime Error

Solution code:
import numpy as np

def knapsackGreedy(sizes, vals, volume):
    ids = np.argsort([val / size for val, size in zip(vals, sizes)])

    sumVal = 0
    for i in ids:
        if sizes[i] <= volume:
            volume -= sizes[i]
            sumVal += vals[i]
        if volume <= 0:
            break

    return sumVal


if __name__ == "__main__":
    n, volume = [int(x) for x in input().split()]
    sizes, vals = [], []
    for _ in range(n):
        s, v = [int(x) for x in input().split()]
        sizes.append(s)
        vals.append(v)
    print(knapsackGreedy(sizes, vals, volume))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, W = list(map(int, input().split(" ")))
 
for i in range(0, N):
	for w in range(1, W+1):
		weight, vvalue = list(map(int, input().split(" ")))
		if w >= weight:
			dp[i + 1][w] = max([dp[i][w - weight] + value, dp[i][w]])
		else:
			dp[i + 1][w] = dp[i][w]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import numpy as np

N, W = map(int, sys.stdin.buffer.readline().split())
   
dp = np.zeros((N+1, W+1), dtype=int)

for i in range(1, N+1):
    w, v = map(int, sys.stdin.buffer.readline().split())
    for j in range(W+1):
        if j-w[i] >= 0:
            dp[i,j] = max(dp[i,j], dp[i-1,j-w[i]]+v[i])
        dp[i,j] = max(dp[i,j], dp[i-1,j])

# for i in range(N+1):
#     print(dp[i])

print(dp[N,W])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))


def solve():
    dp = [0] * (W + 1)
    w0, v0 = things[0]
    for i in range(w0, W + 1):
        dp[i] = v0
    for i in range(1, N):
        dn = dp.copy()
        weight, value = things[i]
        for j in range(weight, W + 1):
            dn[j] = max(dn[j], dp[j - weight] + value)
        dp = dn
    return dp[W]


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

Submission status: Runtime Error

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

dp =[ [0]*(N+3) for _ in range(W+3) ]

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

print(dp[N][W])

Submission status: Runtime Error

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

dp =[ [0]*(N*10) for _ in range(W*10) ]

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

# import os
# path = os.getcwd()
# path = os.path.join(path,"input.txt")
# sys.stdin = open(path)

input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1),dtype=int)
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

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


print(dp[N,-1])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

# import os
# path = os.getcwd()
# path = os.path.join(path,"input.txt")
# sys.stdin = open(path)

input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1),dtype=int)
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

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


print(dp[N][-1])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

import os
path = os.getcwd()
path = os.path.join(path,"input.txt")
sys.stdin = open(path)

input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1))
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    for col in range(1,W+1):
        if w[row] <= col:
            dp[row+1,col] = max(v[row]+dp[row,col-w[row]],dp[row,col])
        else:
            dp[row+1,col] = dp[row,col]

ans = int(max(dp[N]))
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import math

def solve():
    n,w = map(int,input().split())
    w_list,v_list = [0]*n,[0]*n
    for i in range(n):
        w_list[i],v_list[i] = map(int,input().split())
    dp = [[0]*(w+5) for i in range(n+5)]
    for i in range(n):
        for j in range(w+1):
            if j >= w_list[i]:
                dp[i][j] = max(
                    dp[i-1][j],
                    dp[i-1][j-w_list[i]]+v_list[i]
                    )
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[n-1][w])
    return 0

if __name__ == "__main__":
    solve()