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:
n,weight = map(int,input().split())
items = []
for i in range(n):
    w,v = map(int,input().split())
    items.append([w,v])

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

for i in range(n+1):
    if i == 0:
        continue
    for j in range(weight+1):
        case1 = dp[i-1][j]
        if j - items[i-1][0] < 0:
            dp[i][j] = case1
            continue
        else:
            case2 = dp[i-1][j-items[i-1][0]] + items[i-1][1]
            if case1 >= case2:
                dp[i][j] = case1
            else:
                dp[i][j] = case2

print(dp[n+1][weight+1])

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
    N,W=map(int,input().split())
    dp=np.zeros((N+1,W+1),dtype=int)
    for i in range(1,N+1):
        w,v=map(int,input().split())
        dp[i][w:]=np.maximum(dp[i-1][w:],dp[i-1][:-w]+v)
        dp[i][:w]=dp[i-1][:w]
    print(max(dp))
main()

Submission status: Runtime Error

Solution code:
N,W = map(int, input().strip().split(" "))
oj = []
for i in range(N):
    tmp = list(map(int, input().strip().split(" ")))
    oj.append(tmp)

def chk(x):
    s = f"{x:b}"
    s = s[-1::-1]
    w = 0
    v = 0
    for i in range(len(s)):
        if s[i] == '1':
            w += oj[i][0]
            v += oj[i][1]
    return w,v

ans = 0
for i in range(0, 2**N):
    w,v = chk(i)
    if w <= W and v > ans:
        ans = v
print(ans)

Submission status: Runtime Error

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

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

for i in range(1, N + 1):
    for j in range(goods[i][0], W + 1):
        if j - goods[i - 1][0] >= 0:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1])
        else:
            dp[i][j] = dp[i - 1][j]
# print(dp)
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
N,W=map(int, input().split())
w=[None]*10**5
v=[None]*10**9
for i in range(N):
    w[i],v[i]=map(int, input().split())

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

dp = [[0 for _ in range(w+1)] for _ in range(1, n)]

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

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007
    
    N, W = map(int,input().split())
    wv = [tuple(map(int,input().split())) for i in range(n)]
    dp = [0]*(W+1)
    for i in range(N):
        for j in range(W, wv[i][0]-1, -1):
            dp[j] = max(dp[j], dp[j-wv[i][0]]+wv[i][1])
    print(max(dp))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
dp = [[0 for _ in range(10**2+10)] for _ in range(10**5+10)]

N, W = map(int,input().split())
w = []
v = []

for i in range(N):
    wi,vi = map(int,input().split())

    w.append(wi)
    v.append(vi)

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:

import numpy as np  

n, w = map(int, input().split()) 

dp = np.array([0] * w+1)

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

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

Submission status: Runtime Error

Solution code:

import numpy as np  

n, w = map(int, input().split()) 

dp = np.array([0] * w+1)

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

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(int(dp[-1]))

Submission status: Runtime Error

Solution code:

import numpy as np  

n, w = map(int, input().split()) 

dp = np.array([0] * w+1)

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

    dp[weight:] = np.maximum(dp[weight:], dp[:-weight] + value) 

print(dp[-1])

Submission status: Runtime Error

Solution code:
dp = [[0 for _ in range(10**2+10)] for _ in range(10**5+10)]

N, W = map(int,input().split())
w = []
v = []

for i in range(N):
    wi,vi = map(int,input().split())

    w.append(wi)
    v.append(vi)

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

print(dp[N-1][W-1])

Submission status: Runtime Error

Solution code:
dp = [[0 for _ in range(10**2+10)] for _ in range(10**5+10)]

N, W = map(int,input().split())
w = []
v = []

for i in range(N):
    wi,vi = map(int,input().split())

    w.append(wi)
    v.append(vi)

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

print(dp[N-1][W-1])

Submission status: Runtime Error

Solution code:
dp = [[-1 for _ in range(100+10)] for _ in range(10**5+10)]
w = []
v = []

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

for i in range(N):
    wi,vi = map(int,input().split())

    w.append(wi)
    v.append(vi)

#i番目の荷物を入れるときに、capacity以下になるようにする
def dfs(i, capacity):
    if dp[i][capacity] >= 0:
        return dp[i][capacity]
    
    res = 0

    if i == N:
        # 荷物がない
        res = 0
    elif w[i] > capacity:
        # 荷物が入らないから、そのまま次に進む
        dfs(i+1, capacity)
    else:
        # 荷物を入れないとき、荷物を入れるとき。入れるときは価値vが加算される。
        res = max(dfs(i+1,capacity), dfs(i+1, capacity - w[i]) + v[i])

    dp[i][capacity] = res

    return res 

print(dfs(0,W))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import itertools
import heapq
import bisect
import math
import queue
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque, defaultdict #要素ごとの出現回数、双方向アクセス可能データ型
from functools import reduce
mod = 1000000007
inf = 10**10
sys.setrecursionlimit(1000000)

input = sys.stdin.readline

def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
# template


def main():
    n, w = map(int, input().split())
    dp = np.zeros([0] * w+1)

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

        dp[weight:] = np.maximum(dp[weight:], dp[:-weight]+value)

    print(int(dp[-1]))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
item=[]
for i in range(n):
    tmp=list(map(int,input().split()))
    item.append(tmp)

dp=[[0]*(n+100) for i in range(w+100)]
for i in range(n):
    for j in range(w+1):
        if j >= item[i][0]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-item[i][0]]+item[i][1])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[n][w])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
item=[]
for i in range(n):
    tmp=list(map(int,input().split()))
    item.append(tmp)

dp=[[0]*(n+10) for i in range(w+10)]
for i in range(n):
    for j in range(w+1):
        if j >= item[i][0]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-item[i][0]]+item[i][1])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[n][w])

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(W)] for i in range(N)]
for i in range(N):
  wi=Wlist[i]
  if i==0:
    dp[0][Wlist[0]-1]=Vlist[0]
  else:
    for j in range(W):
      if j+wi<W:
        if j==0:
          dp[i][wi-1]=max(Vlist[i],dp[i][wi-1])
        if dp[i-1][j]!=0:
          dp[i][j+wi]=max(dp[i-1][j]+Vlist[i],dp[i][j+wi])
      dp[i][j]=max(dp[i-1][j],dp[i][j])
print(max(dp[N-1])

Submission status: Runtime Error

Solution code:
N,W=int(input())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(N)] for i in range(W)]
for i in range(N):
  wi=Wlist[i]
  for j in range(W):
    if j+wi<W:
    dp[i][j+wi]=max(dp[i-1][j]+Vlist[i],dp[i][j+wi])
    else:
      break
print(max(dp[N-1]))

Submission status: Runtime Error

Solution code:
#include<stdio.h>
#include<bits/stdc++.h>
 
#define get(a, i, j) *((*(a+i))+j)
 
typedef long long ll;
 
int N;
ll W, rec[101][2], mem[105][100005];
 
ll dp(int pos, ll cw); // cw = cumulative weight
 
int main()
{
    //freopen("input.txt", "r", stdin);
    memset(mem, -1, sizeof(mem));
 
    int i;
    scanf("%d%lld", &N, &W);
 
    for(i=0; i<N; ++i) scanf("%lld%lld", &get(rec, i, 0), &get(rec, i, 1));
 
    ll v1;
    v1 = dp(0, 0);
    //v2 = dp(0, 0);
 
    printf("%lld\n",v1);
 
    return 0;
}
 
 
ll dp(int pos, ll cw)
{
    //printf("Inside dp with pos = %d & cw = %lld\n", pos, cw);
    if(pos >= N || cw > W) {
        //printf("returning 0\n\n");
        return 0;
    }
    if(get(mem, pos, cw) > -1) {
        //printf("returning %lld from mem\n\n", get(mem, pos, cw));
        return get(mem, pos, cw);
    }
 
    ll w = get(rec, pos, 0);
 
    ll v1 = 0, v2 = 0;
 
    if((cw + w <= W ) ) {
        //printf("going to next pos including weight\n");
        v1 = get(rec, pos, 1);
        v1 += dp(pos+1, cw + w);
    }
 
    //printf("going to next pos excluding weight\n");
    v2 = dp(pos+1, cw);
 
 
    //printf("returning value either %lld or %lld\n\n", v1, v2);
    return get(mem, pos, cw) = (v1>v2)? v1:v2;
}

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
l = []
for i in range(n):
      l.append(tuple(map(int,input().split())))
dp = [[0]*w]*n
for num in range(n-1):
      for wg in range(w):
            if wg - l[i][0] >=0:
                  dp[i+1][wg] = max(dp[i+1][wg],dp[i][wg-l[i][0]] + l[i][1])
            dp[i+1][wg] = max(dp[i+1][wg],dp[i][wg])
print(dp[n-1][w-1])

Submission status: Runtime Error

Solution code:
INF = float('inf')
MAX_N = 110
MAX_W = 10**5 + 1000

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

dp = [[0]*MAX_N for _ in range(MAX_W)]

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

Submission status: Runtime Error

Solution code:
INF = float('inf')
MAX_N = 110
MAX_W = 10**5 + 1

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

# dp table
# dp[i][j] := i-1番目までの品物から重さがjを超えないように選んだ時の、価値の最大値
dp = [[0]*MAX_N for _ in range(MAX_W)]

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:


import sys
input = sys.stdin.readline

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((N+1,W+1), dtype=np.int64)
    #dp = [[0]*(W+1) for i in range(N+1)]

    #print(dp)
    #print(dp2)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j: #dpの横が重さだが，jが重さ以下ならそもそも入れられない．
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:


import sys
input = sys.stdin.readline

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    #dp = np.zeros((N+1,W+1), dtype=np.int64)
    dp = [[0]*(W+1) for i in range(N+1)]

    #print(dp)
    #print(dp2)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((W+1,N+1), dtype=int)
    #dp = [[0]*(W+1) for i in range(N+1)]

    #print(wv)
    #print(dp)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((W+1,N+1), dtype=int)
    #dp = [[0]*(W+1) for i in range(N+1)]

    #print(wv)
    #print(dp)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            print(i,j)
            print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
item = []
for i in range(N):
    item.append(tuple(map(int, input().split())))
    
def f(N, W, item):
	dp = [[0]*(W+1) for i in range(N+1)]
	for i in range(1, N+1):
    	for j in range(1, W+1):
        	w = j - item[i-1][0]
        	dp[i][j] = max((dp[i-1][w]+item[i-1][1])*(w>=0), dp[i-1][j])
    return dp[N][W]

print(f(N, W, item)

Submission status: Runtime Error

Solution code:
N, W = tuple(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(N)]
items = sorted(items, key=lambda x:x[0])                           
dp = [[0 for _ in range(N+1)] for _ in range(W+1)]
for w in range(1, W+1):
    row = dp[w]
    for i in range(1, N+1):
        w_i, v_i = items[i-1]
        if w_i > w:
            tmp = row[i-1]
            row[i:-1] = [tmp for _ in range(i, N+1)]
            continue
        else:
            row[i] = max(row[i-1], dp[w-w_i][i-1]+v_i
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
                                                                                                                                                                                                                                                                                                                              def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1,W+1):
            if j>w[i-1]-1:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])                                                                                                          else:
                dp[i][j]=dp[i-1][j]
    print(dp[N][W])                                                                                                                                                return                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   # Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():                                                                                                                                              for line in sys.stdin:                                                                                                                                             for word in line.split():                                                                                                                                          yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):                                                                                                                                                 w[i] = int(next(tokens))                                                                                                                                       v[i] = int(next(tokens))
    solve(N, W, w, v)                                                                                                                                                                                                                                                                                                         if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
N,W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
    a,b = map(int ,input().split())
    w[i] = a 
    v[i] = b 

dp = [[0 for _ in range(W+1)] for _ in range(N+2)]
dp = np.array(dp, dtype=int)
for i in np.arange(N):
   for j in np.arange(W+1):
        if w[i] <= j:
            dp[i+1,j] = max(dp[i, j-w[i]]+v[i], dp[i,j])
        else:
            dp[i+1,j] = dp[i,j]

print(dp[N,W])

Submission status: Runtime Error

Solution code:
# Knapsack問題

import numpy as np

# input
N,W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
for i in range(N):
    a,b = map(int ,input().split())
    w[i] = a 
    v[i] = b 

# calc
dp = [[0 for _ in range(W+1)] for _ in range(N+2)]
dp = np.array(dp, dtype=int)
for i in np.arange(N):
   for j in np.arange(W+1):
        if w[i] <= j:
            dp[i+1,j] = max(dp[i, j-w[i]]+v[i], dp[i,j])
        else:
            dp[i+1,j] = dp[i,j]

print(dp[N,W])

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

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(1,n+1):
	w,v=map(intinput().split())
	for j in range(1,W+1):
		if j-w>0:
			dp[i][j]=dp[i-1][j]
		else:
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
print(max(dp[n])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for _ in range(N)], dtype="int64")
dp = np.zeros(W + 1, dtype="int64")

for w, v in wv:
    dp[W:w-1:-1] = np.maximum(dp[W:w-1:-1], dp[W-w::-1] + v)
    print(dp)
    
print(dp[-1])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for _ in range(N)])
dp = np.zeros(W + 1, dtype="int64")

for w, v in wv:
    dp[W:w-1:-1] = np.maximum(dp[W:w-1:-1], dp[W-w::-1] + v)
    print(dp)
    
print(dp[-1])

Submission status: Runtime Error

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

w_v_list = []

for i in range(N):
    w_v_list.append(list(map(int, input().split())))

dp = [[0 for i in range(110)] for j in range(100010)]

for i in range(N):
    for sum_w in range(W + 1):
        if sum_w - w_v_list[i][0] >= 0:
            if dp[i+1][sum_w] < dp[i][sum_w - w_v_list[i][0]] + w_v_list[i][1]:
                dp[i+1][sum_w] = dp[i][sum_w - w_v_list[i][0]] + w_v_list[i][1]
        if dp[i+1][sum_w] < dp[i][sum_w]:
            dp[i+1][sum_w] = dp[i][sum_w]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
s = list(map(int, input().split()))
n=s[0]
w=s[1]
dp=[[0]*(w+1) for i in range(n+1)]
weight=[]
value=[]
for i in range(n):
    s = list(map(int, input().split()))
    weight.append(s[0])
    value.append(s[1])

for i in range(n):
    for j in range(w+1):
        if weight[i]<=w and weight[i]<=j:
            dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[3][8])

Submission status: Runtime Error

Solution code:
def main():
    import numpy as np
    import sys
    input = sys.stdin.readline

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

    dp = np.zeros(n+1,w+1)
    for i in range(n):
        dp[i+1,l[i][0]:] = np.maximum(dp[i,l[i][0]:],dp[i,-l[i][0]]+l[i][1])
    print(dp[n][w])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main()
    import numpy as np
    import sys
    input = sys.stdin.readline

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

    dp = np.zeros(n+1,w+1)
    for i in range(n):
        dp[i+1,l[i][0]:] = np.maximum(dp[i,l[i][0]:],dp[i,-l[i][0]]+l[i][1])
    print(dp[n][w])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

W = []
V = []

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

memo = [[-1 for _ in range(WMAX)] for _ in range(N)]
def rec(i = 0, w = 0):
    # 荷物がない
    if i >= N:
        return 0
    
    # メモを使う
    if memo[i][w] != -1:
        return memo[i][w]
    
    ans = 0
    # もう持てない
    if w + W[i] > WMAX:
        ans = rec(i+1, w)
    else:
        ans = max(rec(i+1, w + W[i]) + V[i], rec(i+1, w))
    
    memo[i][w] = ans
    return ans

print(rec())

Submission status: Runtime Error

Solution code:
    n,w = map(int, input().split())
    wv = []
    for _ in range(n):
        data = list(map(int,input().split()))
        wv.append(data)
     
    dct={}
     
    def solve(i,j):
        if i>=n:
            return 0
     
        ky = str(i)+"_"+str(j)
        if ky in dct:
            return dct[ky]
     
     
        weight=wv[i][0]
        value =wv[i][1]
     
        if j<weight: # can't push this item
            val = solve(i+1,j)
        else:# push or not push
            val =  max(solve(i+1,j-weight)+value, solve(i+1,j))
     
        dct[ky] = val
     
        return val
     
    print(solve(0,w))

Submission status: Runtime Error

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


memo = [[-1] * (n+10)]*(w+10)

def solve(i,j):
    if i>=n:
        return 0

    if memo[i][j] != -1:
        return memo[i][j]

    weight=wv[i][0]
    value =wv[i][1]

    if j<weight: # can't push this item
        val = solve(i+1,j)
    else:# push or not push
        val =  max(solve(i+1,j-weight)+value, solve(i+1,j))

    memo[i][j] = val

    return val

print(solve(0,w))

Submission status: Runtime Error

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

dp = np.zeros((N+1, W+1))

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

print(dp[-1])

Submission status: Runtime Error

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

dp = np.zeros((N+1, W+1))

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

    print(dp[-1])

Submission status: Runtime Error

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

dp = np.zeros((N+1, W+1))

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

    print(dp[-1])

Submission status: Runtime Error

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

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

for i in range(N):
    for w in reversed(range(0, W+1)):
        if dp[w] != 0:
            if w + item[i][0] <= W:
                dp[w + item[i][0]] = max(dp[w +item[i][0]], dp[w] + item[i][1])
        else:
            if w + item[i][0] <= W:
                dp[w + item[i][0]] = dp[w] + item[i][1]
        # print(dp)
print(max(dp[W]))

Submission status: Runtime Error

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

import numpy as np
dp = np.zeros(W+1, dtype="int64")

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

print(dp[-1])

Submission status: Runtime Error

Solution code:
N, W = [int(item) for item in input().splite()]
lag = [[int(item) for item in input().splite()] for _ in range(N)]

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

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

print(dp[N])

Submission status: Runtime Error

Solution code:
def chmin(a, b):
  if (a > b):
    return b

  return a

def chmax(a, b):
  if (a < b):
    return b

  return a

N,W = map(int, input().split())
li = [list(map(int, input().split())) for i in range(N)]

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

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

    dp[n+1][w] = chmax(dp[n+1][w], dp[n][w])


print(max(max(dp)))

Submission status: Runtime Error

Solution code:
def solve(N, W, weightValues):
    dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = weightValues[i]
        for j in range(1, W + 1):
            if j < w: # you cant take it
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
    print(dp[N][W])

def iln(): return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
    w_v.append(iln())

solve(N, W, w_v)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def solve(N, W, weightValues):
    dp = [0] * (W + 1)
    s = 0
    for w, v in weightValues:
        s += w # why ?
        for i in range(min(W, s), w - 1, -1): # why min(W, s)
	    	dp[i] = max(dp[i], dp[i - w] + v)

    print(max(dp))

def iln(): return list(map(int, input().split()))

N, W = iln()
w_v = []
for i in range(N):
  w_v.append(iln())
  
solve(N, W, w_v)