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

Solution code:
import numpy as np


def main(n, w, items):
    dp = np.zeros((n + 1, w + 1), dtype=int)
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        dp[i][:weight] = dp[i - 1][:weight]
        dp[i][weight:] = np.maximum(dp[i - 1][weight:], dp[i - 1][:w - weight + 1] + value)
    return dp[n][w]


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <typeinfo>
using namespace std;

int main()
{
    int N;
    long long W;
    scanf("%d", &N);
    scanf("%lld", &W);
    int values[N];
    long long weights[N];
    long long MAX = W + 1;
    int total_value = 0;
    for (int i = 0; i < N; i++){
        cin>> weights[i] >> values[i];
        total_value += values[i];
    }
    long long dp[total_value + 1];
  	fill(dp, dp + (total_value + 1), MAX);
    
  	for (int i=0; i<N; ++i) {
        for (int j=total_value; j>=values[i]; --j){
            if ((j != values[i]) && (dp[j-values[i]] != MAX))
                dp[j] = min(dp[j], dp[j-values[i]] + weights[i]);
            else if (j == values[i])
                dp[j] = weights[i];
        }
    }  
  
  	for (int i = total_value; i>=0; --i) {
        if (dp[i] != MAX){
            cout << i << endl;
            break;
        }
    }
    
  	
  return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math
n,w=map(int,input().split())
dp=[[math.inf for _ in range((10**3)*n + 1)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    wi,vi=map(int,input().split())
    for j in range((10**3)*n+1):
        if(j < vi):
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i][j-vi]+wi)

for i in range((10**3)*n + 1):
    if(dp[n][(10**3)*n - i] <= w):
        print((10**3)*n - i)
        break

Submission status: Runtime Error

Solution code:
n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
    left = v if v < 100001 else 100001
    right = left + ans + 1 if left + ans + 1 < 100001 else 100001
    for i in range(left, right)[::-1]:
        if bag[i-v] + w < bag[i] and bag[i-v] + w < W+1):
            bag[i] = bag[i-v] + w
            if i > ans:
                ans = i
print(ans)

Submission status: Runtime Error

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

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

for i in range(M + 1, -1, -1):
    if dp[i] != -1:
        print(i)
        break

Submission status: Runtime Error

Solution code:
import numpy as np

n,W = (int(i) for i in input().split())
weights=[]
values=[]
for j in range(n):
    w,val  =[int(i) for i in input().split()]
    weights.append(w)
    values.append(val)

sV = sum(values)
dp = np.zeros(sV,dtype = 'int64')

for i in range(n):
    w = weights[i]
    v = values[i]
    
    dp[v:] = np.maximum(dp[v:],w+dp[:-v])

for i in range(sV):
    if dp[i+1]>W:
        break
    
print(list(dp).index(dp[i]))

Submission status: Runtime Error

Solution code:
import numpy as np

n,W = (int(i) for i in input().split())
items=[[int(i) for i in input().split()]for j in range(n)]

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

for w,v in items:
    dp[w:] = np.maximum(dp[w:],v+dp[:-w])

print(int(dp[-1]))

Submission status: Runtime Error

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n,W = (int(i) for i in input().split())
items=[[int(i) for i in input().split()]for j in range(n)]

dp  = np.zeros(W+1)

for w,v in items:
    dp[w:] = np.maximum(dp[w:],v+dp[:-w])

print(int(dp[-1]))

Submission status: Runtime Error

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

weight_value = [0] * n
for i in range(n):
  weight_value[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (w+1) for i in range(n+1)]

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

Submission status: Runtime Error

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

const long long INF = 1LL<<60;
const int MAX_VALUE = 1000;

int main() {
    int n, W; cin >> n >> W;
    vector<long long> w(n), v(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i] >> v[i];
    }
    vector<vector<long long>> dp(n+1, vector<long long>(MAX_VALUE));
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= MAX_VALUE; ++j) {
            dp[i][j] = INF;
        }
    }
    dp[n][0] = 0;
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j <= MAX_VALUE; ++j) {
            dp[i][j] = min(dp[i][j], dp[i+1][j]);
            if (j - v[i] >= 0) {
                dp[i][j] = min(dp[i][j], dp[i+1][j-v[i]] + w[i]);
            }
        }
    }
    long long ans = 0;
    for (int j = 0; j <= MAX_VALUE; ++j) {
        if (dp[0][j] <= W) {
            ans = j;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,w=map(int,input().split())
dp=[[0]*(w+1) for _ in range(n)]
l=[0]*n
for i in range(n):
    l[i]=list(map(int,input().split()))
#print(l)
for i in range(w+1):
    if i>=l[0][0]:
        dp[0][i]=l[0][1]
for i in range(w+1):
    for j in range(n-1):
        if i<l[j+1][0]:
            dp[j+1][i]=dp[j][i]
        else:
            dp[j+1][i]=max(dp[j][i-l[j+1][0]]+l[j+1][1],dp[j][i])


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

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(n):
  for j in range(w + 1):
    if j + wv[i][0] <= w:
      dp[i + 1][j + wv[i][0]] = max(dp[i + 1][j + wv[i][0]], dp[i][j] + wv[i][1])
    dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,w=map(int,input().split())
    W=[0]*(n+1); V=[0]*(n+1)
    for i in range(1,n+1):
        a,b=map(int,input().split())
        W[i]=a; V[i]=b
    # dp[i][c] iまでの品物で、重さがc以下
    dp=[[-1]*(w+1) for _ in range(n+1)]
    # メモ化再帰
    def solve(i,c):
        if(dp[i][c]!=-1): return dp[i][c]
        if(i==0):
            dp[i][c]=0
            return dp[i][c];
        if(c-W[i]>=0):
            dp[i][c]=max(solve(i-1,c-W[i])+V[i],solve(i-1,c))
            return dp[i][c]
        else:
            dp[i][c]=solve(i-1,c)
            return dp[i][c]
    print(solve(n,w))
resolve()

Submission status: Runtime Error

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

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

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

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

dp[0][0] = 0

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


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

Submission status: Runtime Error

Solution code:
n, w = [int(x) for x in input().split()]
W = []
V = []
for i in range(n):
  wi, vi = [int(x) for x in input().split()]
  W.append(wi)
  V.append(vi)
 
dp = []
for i in range(n+1):
  dp.append([0]*(w+1))
 
for i in range(n):
  for sum_w in range(w + 1):
    # 選ぶ場合
    if sum_w - W[i] >= 0:
      dp[i+1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - W[i]] + V[i])
 
    # 選ばない場合
    dp[i+1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
 
print(dp[n][w])

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)


def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]

    def solve(i, w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1, w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1, w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]

    solve(0, W)
    # print(dp)
    return max(dp[0])


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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, W = list(map(int, input().split()))
WV = [list(map(int, input().split())) for _ in range(N)]

DP = [0] * (W+1)

for n in range(N):
    next = [0] * (W+1)
    for w in range(1, W+1):
        if w < WV[n][0]:
            next[w] = DP[w]
        else:
            next[w] = max(DP[w], DP[w-WV[n][0]]+WV[n][1])
    DP = next

print(DP[W])

Submission status: Runtime Error

Solution code:
n, w = map(int,input().split())
li = []
while True:
    try:
        li.append(list(map(int,input().split())))
    except:
        break

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-li[i-1][0]>=0):
            # 品物がひとつ前で重さは同じ所の価値と品物がひとつ前で重さが加える価値を持し品物の重さ分引いたときの価値にひとつ前の品物の価値を加えたもの
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-li[i-1][0]]+li[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][w])

Submission status: Runtime Error

Solution code:
n, w = map(int,input().split())
li = []
while True:
    try:
        li.append(list(map(int,input().split())))
    except:
        break



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-li[i-1][0]>=0):
            # 品物がひとつ前で重さは同じ所の価値と品物がひとつ前で重さが加える価値を持し品物の重さ分引いたときの価値にひとつ前の品物の価値を加えたもの
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-li[i-1][0]]+li[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]


print(dp[n][w])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]

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

Submission status: Runtime Error

Solution code:
def main():
    n, w = map(int, input().split())
    dp = [-1] * (w + 1)
    dp[w] = 0
    for i in range(n):
        input_w, input_v = map(int, input().split())
        for i in range(input_w, w + 1):
            if dp[i] == -1:
                continue
            if dp[i - input_w] < dp[i] + input_v:
                dp[i - input_w] = dp[i] + input_v
    print(max(dp))

main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

item = [list(map(int,input().split())) for _ in range(N)]

val = np.zeros(W+1,dtype = int)

for i in range(N):
  item_weight = item[i][0]
  val[item_weight :] = np.maximum(val[item_weight :], val[:-item_weight] + item[i][1])
  
print(max(val))

Submission status: Runtime Error

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

V_MAX = 10 ** 5 + 1
INF = 10 **18

dp = [[INF] * (V_MAX) for _ in range(n + 1)]
for i in range(n):
  for j in range(V_MAX):
    if wv[i][1] > j:
      dp[i + 1][j + wv[i][1]] = min(dp[i + 1][j + wv[i][0]], dp[i][j] + wv[i][0])
    dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
print(min([i for i, v in enumerate(dp[-1]) if v <= 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(n):
  for j in range(w + 1):
    if j + wv[i][0] <= w:
      dp[i + 1][j + wv[i][0]] = max(dp[i + 1][j + wv[i][0]], dp[i][j] + wv[i][1])
    dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
print(max(dp[-1]))

Submission status: Runtime Error

Solution code:


import numpy as np
N,W = map(int,input().split(' '))
 
min_list = np.full(10**5+1,10**11, dtype=np.int64)
current_list = np.full(10**5+1,10**11, dtype=np.int64)

sum_v = 0
for i in range(N):
    w,v = map(int,input().split(' '))
    sum_v += v
    current_list[:v+1] = w
    if i != 0:
        current_list[v:sum_v+1] = w + min_list[:sum_v - v + 1]

    min_list = np.stack([current_list,min_list],0).min(0)
    current_list = np.full(10**5+1,10**11, dtype=np.int64)
 
print(min_list[min_list<=W].shape[0] - 1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
N, W = [int(v) for v in input().strip().split(' ')]

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

for _ in range(N):
    w, v = [int(v) for v in sys.stdin.readline().split(' ')]
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])

print(dp[W])

Submission status: Runtime Error

Solution code:
def A(w, v, n,V):
    mem=[V+1 for i in range(n*1000+1)]
    if n == 0 or V == 0:
        return 0
 
    for i in range(n):
        for j in range(V,w[i]-1,-1):
            m=v[i]+ mem[j - w[i]]
            if m>mem[j]:
                mem[j]=m
    return mem[V]
n,V=input().split()
n,V=int(n),int(V)
 
w=[0]*n
v=[0]*n
for i in range(n):
  x,y=input().split()
  w[i],v[i]=int(x),int(y)
 
print(A(w,v,n,V))

Submission status: Runtime Error

Solution code:
N = int(input())
items = [list(map(int, input().split())) for _ in range(N)]
v_max = 1000*100
INF = 10**18
dp = [[INF] * (v_max+1) for _ in range(N+1)]
for v in range(v_max+1):
  dp[0][v] = 0

for i in range(N):
  for v in range(v_max+1):
    if v >= items[i][1]:
      dp[i+1][v] = min(dp[i][v-items[i][1]]+items[i][0], dp[i][v])
    else:
      dp[i+1][v] = dp[i][v]

for v in range(v_max+1)[::-1]:
  if dp[N][v] <= W:
    print(v)
    break

Submission status: Runtime Error

Solution code:
N = int(input())
items = [list(map(int, input().split())) for _ in range(N)]
v_max = 1000*100
dp = [[INF] * (v_max) for _ in range(N+1)]
for v in range(v_max):
  dp[0][v] = 0

for i in range(N):
  for v in range(v_max):
    if v >= items[i][1]:
      dp[i+1][v] = min(dp[i][v-items[i][1]]+items[i][0], dp[i][v])
    else:
      dp[i+1][v] = dp[i][v]

for v in range(v_max)[::-1]:
  if dp[N][v] <= W:
    print(v)
    break

Submission status: Runtime Error

Solution code:
N = int(input())
items = [list(map(int, input().split())) for _ in range(N)]
v_max = 1000*100
dp = [[INF] * (v_max) for _ in range(N+1)]
for v in range(v_max):
  dp[0][v] = 0

for i in range(N+1):
  for v in range(v_max):
    if v >= items[i][1]:
      dp[i+1][v] = min(dp[i][v-items[i][1]]+items[i][0], dp[i][v])
    else:
      dp[i+1][v] = dp[i][v]

for v in range(v_max)[::-1]:
  if dp[N][v] <= W:
    print(v)
    break

Submission status: Runtime Error

Solution code:
n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in xrange(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in xrange(limit+1)] for _ in xrange(n)]

    prev = [0 for _ in xrange(limit+1)]

    if weights[0] <= limit:
        for w in xrange(weights[0], limit+1):
            prev[w] = values[0]

    for i in xrange(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in xrange(1, min(limit+1, sum(values))):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))

Submission status: Runtime Error

Solution code:
n, s = [int(i) for i in  raw_input().split()]
weights = []
values = []

for _ in xrange(n):
    w, v = [int(i) for i in raw_input().split()]
    weights.append(w)
    values.append(v)

def knapsack(weights, values, limit):
    n = len(weights)
    # f = [[0 for _ in xrange(limit+1)] for _ in xrange(n)]

    prev = [0 for _ in xrange(limit+1)]

    if weights[0] <= limit:
        for w in xrange(weights[0], limit+1):
            prev[w] = values[0]

    for i in xrange(1, n):
        # print prev
        current = [0] * (limit+1)
        for w in xrange(1, limit+1):
            current[w] = max(prev[w], current[w])
            if weights[i] <= w:
                current[w] = max(current[w], prev[w-weights[i]] + values[i])
        prev = list(current)

    return prev[-1]

# weights = [10, 20, 30]
# values = [60, 100, 120]
print(knapsack(weights, values, s))

Submission status: Runtime Error

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



max_sum = sum([i[1] for i in A])

max_value=1000001
dp = [[max_value for i in range(max_sum+1) ] for j in range(N+1)]
dp[0][0]=0

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

        else:
            dp[i+1][v] = dp[i][v]

#ここでindexは価値と同値、複数あることを考慮して反転後indexで最も価値のある個所を取得
print(max_sum-dp[N][::-1].index(W))
#     print(int(dp[N][W]))

Submission status: Runtime Error

Solution code:
def p_e():
    """
    ナップサック問題（制約厳しい版） 
    """
    N, W = map(int, input().split())
    dp = [0] * (W + 1)
    for i in range(1, N + 1):
        w, v = map(int, input().split())
        NEXT = [0] * (W + 1)
        for j in range(1, W + 1):
            if j - w >= 0:
                NEXT[j] = max(v + dp[j - w], dp[j])
            else:
                NEXT[j] = dp[j]
        dp = NEXT

    print(max(NEXT))


if __name__ == '__main__':
    p_e()

Submission status: Runtime Error

Solution code:
def p_d():
    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] = max(v + dp[i - 1][j - w], dp[i - 1][j])
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])

    print(max(dp[N]))


if __name__ == '__main__':
    p_d()

Submission status: Runtime Error

Solution code:
import numpy as np

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
table = np.zeros(w+1, dtype=np.int64)

for i in range(n):
    l = table[:-wv[i][0]]
    r = table[wv[i][0]:]
    np.maximum(l + wv[i][1], r, out = r)

print(table[w])

Submission status: Runtime Error

Solution code:
def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]+[float"inf"]*(10**5)#dp[k]:価値kにおける最小重さ
for i in range(n):#あるi番目の品物について
    for j in range(10**5,wv[i][1]-1, -1):#ある価値jについて
        dp[j] = min( dp[j], dp[j-wv[i][1]]+wv[i][0] )
        #重さwv[i][0]であるi番目の品物を使うほうが価値jでの最小重さdp[j]が小さい場合は値を更新

res = 0
for v,e in enumerate(dp):#インデックスv(=ある価値j)における最小重さeについて
    if e <= w:
        res = v#最小重さが重さ制限を超えないならres更新
print(res)

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]*(w+1)#dp[i]:重さiにおける最大価値
for i in range(n):#あるi番目の品物について
    for j in range(w,wv[i][0]-1, -1):#ある重さjについて
        dp[j] = max( dp[j], dp[j-wv[i][0]]+wv[i][1] )#i番目の品物を使うほうが重さjでの価値が高い場合は値を更新

print(max(dp))

Submission status: Runtime Error

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

dp_v = [0] * (W+1)

for i in range(N):
    for j in (reversed(range(W+1))):
        if (j == 0 or dp_v[j] != 0) and j+w[i] <= W and dp_v[j+w[i]] < dp_v[j] + v[i]:
            dp_v[j+w[i]] = dp_v[j] + v[i]
            
max = 0        
for i in range(W+1):
    if max < dp_v[i]:
        max = dp_v[i]

print(max)

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):
    weight = WV[i-1][0]
    value = WV[i-1][1]
    for w in range(W+1):
        if w-weight<0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w-weight]+value, dp[i-1][w])

print(dp[N][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):
    weight = WV[i-1][0]
    value = WV[i-1][1]
    for w in range(W+1):
        if w-weight<0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w-weight]+value, dp[i-1][w])

print(dp[N][W])

Submission status: Runtime Error

Solution code:
def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[target] = 0 # default + max
    max_ = 0

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in P:
            if i >= we:
                prev = P[i-we] if (i-we) in P else -1
                piva = P[i] + va
                if prev < piva:
                    P[i - we] = piva
                    if piva > max_:
                        max_ = piva

    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np 
IN = lambda:map(int, input().split())
 
n, k = IN()
dp = np.zeros(k+1,dtype=np.int64)
 
for i in range(n):
    w, c = IN()
    dp[w:] = np.maximum(dp[w:], dp[:-w] + c)
    
print(dp[-1])

Submission status: Runtime Error

Solution code:
def kp(n, w, val, wt):
    if n==1:
        if wt[0]<=w:
            return val[0]
        return 0
    
    dp = [dp[:]for dp in[[0]*(w+1)]*(n+1)]
    # print(dp)
    for i in range(n+1):
        for j in range(w+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif wt[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], val[i-1]+dp[i-1][j-wt[i-1]])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][w]


n, w = map(int, input().strip().split())
val = []
wt = []
for i in range(n):
    a, b = map(int, input().strip().split())
    wt.append(a)
    val.append(b)
print(kp(n, w, val, wt))

Submission status: Runtime Error

Solution code:
def kp(n, w, val, wt):
    if n==1:
        if wt[0]<=w:
            return val[0]
        return 0
    
    dp = [dp[:]for dp in[[0]*(w+1)]*(n+1)]
    # print(dp)
    for i in range(n+1):
        for j in range(w+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif wt[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], val[i-1]+dp[i-1][j-wt[i-1]])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][w]


n, w = map(int, input().split())
val = []
wt = []
for i in range(n):
    a, b = map(int, input().split())
    wt.append(a)
    val.append(b)
print(kp(n, w, val, wt))

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int, input().split())
ndp = np.zeros(W+1, dtype= np.int64)
for _ in range(N):
    w, v = map(int,input().split())

    # 離散より連続で扱った方が問題が簡単になる。
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])

Submission status: Runtime Error

Solution code:
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  cmaxv = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(cmaxv - 1, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
        if cmaxv < i + nv:
          cmaxv = i + nv:
  print(cmaxv)
main()

Submission status: Runtime Error

Solution code:
import numpy as np
N,W = map(int,input().split())
ndp = np.zeros(W+1,dtype= np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
ndp = np.zeros(W+1,dtype= np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])

Submission status: Runtime Error

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

max_v = 100005

dp = [[float('inf') * max_v] for j in range(n + 1)]
dp[0][0] = 0

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

for sum_v in reversed(range(max_v)):
    if dp[-1][sum_v] <= w:
        print(sum_v)
        break

Submission status: Runtime Error

Solution code:
import numpy as np

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

s = np.zeros(ww+1, dtype=np.int64)
for i in range(n):
    w, v = map(int, input().split())
    s[w:] = np.maximum(s[w:], s[:-w] + v)

print(s[ww])

Submission status: Runtime Error

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


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

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

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

    print(dp[N][W])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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