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:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1e9 + 5;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////

int main() {
    int N, W;
    scanf("%d%d", &N, &W);
    vector<ll> dp(W + 1); // 0 ... W
    // dp[i] - the maximum total value with weight exactly i
    for (int i = 0; i < N; ++i) {
        int weight, value;
        scanf("%d%d", &weight, &value);
        for (int weight_already = W - weight; weight_already >= 0; --weight_already) {
            dp[weight_already + weight] = max(dp[weight_already + weight], dp[weight_already] + value);
        }
    }
    printf("%lld\n", *max_element(dp.begin(), dp.end()));

    return 0;
}

Submission status: Runtime Error

Solution code:
#DP D
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):
    w,v=wv[i]
    for j in range(W+1):
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
for i in range(n+1):
print(dp[-1][-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import random
import copy

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

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

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

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

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

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

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

gene_length = N # 遺伝子長
individual_length = 30 # 個体数
generation = 1000 # 世代数
elite_rate = 0.2 # エリート選択の割合

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

for i_episode in range(generation):

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

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

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

Submission status: Runtime Error

Solution code:
N , W = map(int , input().
weight = []               
value = []                
for _ in range(N):        
    w , v = map(int , inpu
    weight.append(w)      
    value.append(v)       
                          
def knapsack():           
    dp = [[0] * (W + 1) fo
    def solve(i,w):       
        if N == i:        
            ret_val = 0   
        elif w - weight[i]
            ret_val = solv
        else:             
            ret_val = max(
        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:
N,W = list(map(int,input().split()))
wv = [list(map(int,input().split())) for i in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]

# DP用の空行列
dp = [[0 for i in range(W+1)] for j in range(N+1)]

# 「1番目の荷物」「2番目の荷物」......「N番目の荷物」までを使った場合分け
# 重量制限が「0の場合」「1の場合」......「Mの場合」の場合分け

for i in range(N):
    for j in range(W):
        if w[i] > j: # もしi番目の重さが重量制限を超えている場合
            dp[i][j] = dp[i-1][j]
        else: # その他の重量制限の残り「j-w[i]」を重量制限としてdpから引用
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

print(max(max(dp)))

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    weight, value = map(int,input().split())
    w.append(weight)
    v.append(value)
dp = [[0 for _ in range(10*9)] for _ in range(N+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:
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    weight, value = map(int,input().split())
    w.append(weight)
    v.append(value)
dp = [[0 for _ in range(10*5*100)] for _ in range(N+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:
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(W+10)] for _ in range(N+10)]
for i, (item_weight, item_value) in enumerate(items):  # i番目の品
    for total_weight in range(W):                      # 重さの合計
        dp[i+1][total_weight] = max(dp[i][total_weight], dp[i+1][total_weight])
        dp[i+1][total_weight + item_weight] = \
            max(dp[i][total_weight] + item_value, dp[i+1][total_weight + item_weight])
          
print(dp[N][W])

Submission status: Runtime Error

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

dp = [[0 for _ in range(W+10)] for _ in range(N+10)]
for i, (item_weight, item_value) in enumerate(items):  # i番目の品
    for total_weight in range(W):                      # 重さの合計
        dp[i+1][total_weight+item_weight] = max(dp[i][total_weight]+item_value, dp[i+1][total_weight+item_weight])
        dp[i+1][total_weight] = max(dp[i][total_weight], dp[i+1][total_weight])
        
print(dp[N][W])

Submission status: Runtime Error

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

dp = [[0 for _ in range(W+100)] for _ in range(N+10)]
dp[0][0] = 0
for i, (item_weight, item_value) in enumerate(items): 
    for total_weight in range(W+10):                   
        dp[i+1][total_weight] = max(dp[i][total_weight], dp[i+1][total_weight])
        dp[i+1][total_weight+item_weight] = max(dp[i][total_weight]+item_value, dp[i+1][total_weight+item_weight])
        
print(dp[N][W])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
 
 
dp = [[float('-inf') for _ in range(1000)] for _ in range(110)]
dp[0][0] = 0
for i, (item_weight, item_value) in enumerate(items):  # i番目の品
    for total_weight in range(W+10):                   # 重さの合計
        dp[i+1][total_weight] = max(dp[i][total_weight], dp[i+1][total_weight])
        dp[i+1][total_weight+item_weight] = max(dp[i][total_weight]+item_value, dp[i+1][total_weight+item_weight])
        
print(dp[N][W])

Submission status: Runtime Error

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


dp = [[float('-inf') for _ in range(1000)] for _ in range(10)]
dp[0][0] = 0
for i, (item_weight, item_value) in enumerate(items):  # i番目の品
    for total_weight in range(W+10):                   # 重さの合計
        dp[i+1][total_weight] = max(dp[i][total_weight], dp[i+1][total_weight])
        dp[i+1][total_weight+item_weight] = max(dp[i][total_weight]+item_value, dp[i+1][total_weight+item_weight])
        
print(dp[N][W])

Submission status: Runtime Error

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

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

for i in range(N):
    w,v = map(int,input().split(' '))
    
    current_list[w:] = current_list[w:] + v + max_list[0:-w]
    max_list = np.stack([current_list,max_list],0).max(0)
    current_list = np.full(W+1,0, dtype=np.int64)

print(max_list[-1])

Submission status: Runtime Error

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

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

for i in range(N):
    w,v = map(int,input().split(' '))  
    current_list[w:] = current_list[w:] + v + max_list[0:-w]
    max_list = np.stack([current_list,max_list],axis=0).max(axis = 0)
    current_list = np.full(W+1,0, dtype=np.int64)
print(max_list[-1])

Submission status: Runtime Error

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

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

for i in range(N):
    w,v = map(int,input().split(' '))
    
    current_list[w:] = current_list[w:] + v + max_list[0:-w]
    max_list = np.stack([current_list,max_list],axis=0).max(axis = 0)
    current_list = np.full(W+1,0, dtype=np.int64)

print(max_list[-1])

Submission status: Runtime Error

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


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

print(current_list)

Submission status: Runtime Error

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

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

for i in range(N):
    w,v = map(int,input().split(' '))
    
    current_list[w:] = current_list[w:] + v + max_list[0:-w]
    max_list = np.stack([current_list,max_list],axis=0).max(axis = 0)
    current_list = np.full(W+1,0, dtype=np.int64)

print(current_list)

Submission status: Runtime Error

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

max_list = np.full(W+1,0, dtype=np.int64)
current_list = np.full(W+1,0, dtype=np.int64)

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

    max_list = np.stack([current_list,max_list],axis=0).max(axis = 0)
    current_list = np.full(W+1,0, dtype=np.int64)

print(current_list)

Submission status: Runtime Error

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

max_list = np.full(W+1,0)
current_list = np.full(W+1,0)

for i in range(N):
    w,v = map(int,input().split(' '))
    
    current_list[w:] = current_list[w:] + v + max_list[0:-w]
    
    max_list = np.stack([current_list,max_list],axis=0).max(axis = 0)
    current_list = np.full(W+1,0)

print(max_list[-1])

Submission status: Runtime Error

Solution code:
def A(w, v, n,V):
    mem=[0 for i in range(V+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:
def A(w, v, n,V):
    mem=[0 for i in range(V+1)]
    if n == 0 or V == 0:
        return 0

    for i in range(n):
        for j in range(V,W[i]-1,-1):
            mem[j] = max(mem[j], v[i]+ mem[j - w[i]])
    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,4,4))

Submission status: Runtime Error

Solution code:
N,W = map(int,input().split())
li = [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 < li[i][0]: continue
    
    dp[i+1][j] = max(dp[i+1][j], dp[i][j-li[i][0]] + li[i+1][1])
    
print(dp[-1][-1])

Submission status: Runtime Error

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

for _ in range(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 range(limit+1)] for _ in range(n)]

    if weights[0] <= limit:
        for w in range(weights[0], limit):
            f[0][w] = values[0]

    for w in range(1, limit+1):
        for i in range(1, n):
            f[i][w] = max(f[i-1][w], f[i][w])
            if weights[i] <= w:
                f[i][w] = max(f[i][w], f[i-1][w-weights[i]] + values[i])

    return f[-1][-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)]



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


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

Submission status: Runtime Error

Solution code:
import numpy as np

W = int(input())
n, k = map(int, input().split())
width = []
importance = []

for _ in range(n):
    w, imp = map(int, input().split())
    width.append(w)
    importance.append(imp)

DP = [[[[0]*(W+1)] for _ in range(n+1)] for _ in range(k+1)]

for i in range(1, n+1):
    for w in range(1, W+1):
        for k in range(0, k):
            wid = width[i-1]
            imp = importance[i-1]

            if w + wid <= W:
                DP[i][w+wid][k+1] = DP[i-1][w][k] + imp
            DP[i][w] = max(DP[i][w], DP[i-1][w])

ans = np.argmax(DP[n])
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack():
  dp = np.zeros((N+1, W+1), dtype=int)
  c = np.arange(1, N+1)
  cc = np.arange(1, W+1)
  for i in c:
    w, v = map(int, input().split())
    dp[i][w:] = max(dp[i-1][w:], dp[i-1][:-w] + v)
    dp[i][:] = max(dp[i][:], dp[i-1][:])
  return dp[-1][-1]
print(knapsack())

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, W = map(int, input().split())
def knapsack(w, v):
  dp = np.zeros((N+1, W+1), dtype=int)
  for i in range(1, N+1):
    w, v = map(int, input().split())
    for sum_w in range(1, W+1):
      if sum_w - w >= 0:
        dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w] + v)
      dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
  return dp[-1][-1]
print(knapsack(w, v))

Submission status: Runtime Error

Solution code:
# dp[i][w_sum]: i-1番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値

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

dp = [[0 for w_sum in range(W)] for i in range(N)]

for i in range(N):
    for w_sum in range(W):

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if w_sum-items[i][0] >= 0:
            dp[i+1][w_sum] = max(dp[i+1][w_sum],
                                 dp[i][w_sum-items[i][0]]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][w_sum] = max(dp[i+1][w_sum], dp[i][w_sum])

print(dp[N][W])

Submission status: Runtime Error

Solution code:
def solve(N, W, w, v):
    dp = [[0]*(W+1) for _ in range(N+2)]
    for i in range(N):
        for sum_w in range(W):
            if sum_w+w[i] <=W:
                dp[i+1][sum_w+w[i]] = max(dp[i][sum_w+w[i]], dp[i][sum_w]+v[i])
        dp[i+2] = dp[i+1].copy()
    return max(dp[-1])

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

print(solve(N, W, w, v))

Submission status: Runtime Error

Solution code:
def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0]*(W+1) for _ in range(N+2)]
    #dp = [0]*(W+1)
    for i in range(N):
        for sum_w in range(W):
            if sum_w+w[i] <=W:
                dp[i+1][sum_w+w[i]] = max(dp[i][sum_w+w[i]], dp[i][sum_w]+v[i])
                #dp[sum_w+w[i]] = max(dp[sum_w+w[i]], dp[sum_w]+v[i])
            #dp[i+1][sum_w] = dp[i][sum_w]
        dp[i+2] = dp[i+1].copy()
    return max(dp[-1])

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

print(solve(N, W, w, v))

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+2)]
    #dp = [0]*(W+1)
    for i in range(N):
        for sum_w in range(W):
            if sum_w+w[i] <=W:
                dp[i+1][sum_w+w[i]] = max(dp[i][sum_w+w[i]], dp[i][sum_w]+v[i])
                #dp[sum_w+w[i]] = max(dp[sum_w+w[i]], dp[sum_w]+v[i])
            #dp[i+1][sum_w] = dp[i][sum_w]
        dp[i+2] = dp[i+1].copy()
    return max(dp[-1])


# Generated by 1.1.4 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))
    print(solve(N, W, w, v))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0]*(W+1) for _ in range(N+2)]
    #dp = [0]*(W+1)
    for i in range(N):
        for sum_w in range(W):
            if sum_w+w[i] <=W:
                dp[i+1][sum_w+w[i]] = max(dp[i][sum_w+w[i]], dp[i][sum_w]+v[i])
                #dp[sum_w+w[i]] = max(dp[sum_w+w[i]], dp[sum_w]+v[i])
            #dp[i+1][sum_w] = dp[i][sum_w]
            dp
        dp[i+2] = dp[i+1].copy()
    return max(dp[-1])


# Generated by 1.1.4 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))
    print(solve(N, W, w, v))

if __name__ == '__main__':
    main()

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:
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int W = in.nextInt();
        int w[] = new int[N];
        int v[] = new int[N];
        for(int i=0;i<N;i++){
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        in.close();
        long dp[][] = new long[N+1][W+1];
        for(int i=0;i<W+1;i++){
            dp[N][i] = 0;
        }
        for(int i=N-1;i>=0;i--){
            for(int j=0;j<W+1;j++){
                if(j < w[i]){
                    dp[i][j] = dp[i+1][j];
                }
                else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
                }
            }
        }
        System.out.println(dp[0][W]);
    }
}

Submission status: Runtime Error

Solution code:
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      break
    nv = t[j] + tv
    if nw in t
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))

Submission status: Runtime Error

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

n, w = [int(i) for i in input().split()]
a = np.array([[int(n) for n in input().split()] for i in range(n)])
a = a[np.argsort(a[:, 1] / a[:, 0])][::-1]

sv = {}
for ww, vv in a:
    added = {}
    for k, v in sv.items():
        added[ww+k] = vv+v
    for k, v in added.items():
        if (k <= w) and (k not in sv or v > sv[k]):
            sv[k] = v

    if (ww <= w) and (ww not in sv or vv > sv[ww]):
        sv[ww] = vv

print(max(sv.values()))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
w = []
v = []
n, W = map(int, input().split())
#dp = [[0 for i in range(n)] for j in range(W)]
dp = [[None for i in range(W+1)] for j in range(n+1)]

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

# i: Index (Tracing all items)
# j: Remaining weight
# Return the sum of value
def knap(i, j):
    # print("\n# i: " + str(i))
    # print("# j: " + str(j))
    if dp[i][j] is not None:
        return dep[i][j]

    res = 0

    if i == n:
#        dp[i][j] = 0
        res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        # if dp[i][j] is None:
        #     dp[i][j] = dp[i-1][j] + v[i]
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]
#    return res

print(knap(0, W))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		if w <= W:
			wv.append((w,v))
		
	DP = [[0 for _ in range(100000)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][w] = v
			continue
			
		for j in range(W):
			DP[i][j] = max(DP[i-1][j], DP[i][j])
			
			if j+w <= W:
				DP[i][j+w] = max(DP[i-1][j] + v, DP[i][j+w])
			
	print(max(DP[N-1]))
	
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]

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

dp = [[0 for i in range(2*N)] for j in range(2*W)]

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
wv = [[0 for i in range(2)] for j in range(N)]

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

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

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
def dp():
    n,w = map(int,input().split())
    lis = (map(int,input().split()) for i in range(n))
    
    dpp = [0] * (w + 1)
    for meight, value in lis:
        for j in range(w,weight-1,-1):
            dp = dpp[j-w] + value
            if dpp[j] < dp:
                dpp[j] = dp
    return max(dpp)
print(dp())

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((n+1, w+1), -1)

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    res = 0
  elif j == 0:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w_tmp, v_tmp = map(int, input().split())
    weight.append(w_tmp)
    value.append(v_tmp)

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

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

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)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

dp = [[None] * 10**5 for _ in range(100)]
def dfs(weight=0, depth=N - 1):
    if dp[weight][depth] is not None:
        return dp[weight][depth]

    if depth == -1:
        return 0

    if weight + ws[depth] <= W:
        result = max(dfs(weight + ws[depth], depth - 1) + vs[depth], dfs(weight, depth - 1))
    else:
        result = dfs(weight, depth - 1)
    dp[weight][depth] = result
    return result

print(dfs())

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
# dp[i][w] : i個目の時の重さwの最大値
dp = [[0] * 10010 for _ in range(N+1)]
for i in range(N):
    w_i, v_i = map(int, input().split())
    for w in range(W+1):
        if w >= w_i:
            dp[i+1][w] = max(dp[i][w-w_i]+v_i, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
# dp[i][j] : i日めにjをした。(j=0:持つ, j=1:持たない)
dp = [[0] * 10010 for _ in range(N+1)]
for i in range(N):
    w_i, v_i = map(int, input().split())
    for w in range(W+1):
        if w >= w_i:
            dp[i+1][w] = max(dp[i][w-w_i]+v_i, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])

Submission status: Runtime Error

Solution code:
n,w=map(int,input().split())
a=[[0,0] for _ in range(n)]
vw=[[0,0] for _ in range(n)]
for j in range(n):
    a[j][0],a[j][1]=map(int,input().split())
    vw[j][0],vw[j][1]=a[j][1]/a[j][0],j
vw.sort(reverse=True)
print(vw,a)
j=0
v=0
while(w>0):
    print(w,a[vw[j][1]][0],a)
    d=min(w,a[vw[j][1]][0])
    print(d)
    v=v+d*vw[j][0]
    w=w-d
    a[j][1]-=d
    print(v, w, a[j][1],vw[j][0]*d)
    j+=1
  #  print(v,w,a[j][1])
print(int(v))

Submission status: Runtime Error

Solution code:
# import numpy as np

# N, W = map(int, input().split())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
# """
# dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
#          = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
# """
# for i in range(1, N+1):
#     wi, vi = map(int, input().split())
#     for k in range(1, i+1):
#         tmp = np.maximum(dp[i-k, :W-wi+1] + vi, dp[i-k, wi:W+1])
#         dp[i, wi:W+1] = np.maximum(dp[i, wi:W+1], tmp)
    

# print(int(dp[-1,-1]))


N, W = map(int, input().split())
# dp = np.zeros((N+1, W+1))  #i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

def maximum(list1, list2):
    ans = []
    for i in range(len(list1)):
        ans.append(max(list1[i], list2[i]))
    return ans

for i in range(1, N+1):
    wi, vi = map(int, input().split())
    for k in range(1, i+1):
        tmp2 = [val + vi for val in dp[i-k][:W-wi+1]]
        tmp = maximum(tmp2, dp[i-k][wi:W+1].copy())
        dp[i][wi:W+1] = maximum(dp[i][wi:W+1], tmp)
    

print(int(dp[-1][-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 - w + 1] + v, dp[w:], out=dp[w:])
print(dp[-1])