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: Wrong Answer

Solution code:
from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(li[i][0]-1,w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return dp[-1][-1]
print(knapsack(n,w,li))

Submission status: Wrong Answer

Solution code:
from sys import stdin

n,w = [int(x) for x in stdin.readline().rstrip().split()]
nw = [0]*n
nv = [0]*n
for i in range(n):
    nw[i],nv[i] = [int(x) for x in stdin.readline().rstrip().split()]
def knapsack(n,w,nw,nv):
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - nw[i] >= 0:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w-nw[i]]+nv[i])
            else:
                dp[i+1][total_w] = max(dp[i+1][total_w],dp[i][total_w])
    return max(dp[-1])
print(knapsack(n,w,nw,nv))

Submission status: Wrong Answer

Solution code:
from sys import stdin

n,w = [int(x) for x in stdin.readline().rstrip().split()]
nw = [0]*n
nv = [0]*n
for i in range(n):
    nw[i],nv[i] = [int(x) for x in stdin.readline().rstrip().split()]
def knapsack(n,w,nw,nv):
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,w+1):
            if j + nw[i-1] <= w:
                dp[i][j] = dp[i-1][j-nw[i-1]] + nv[i-1]
            else:
                dp[i][j] = dp[i-1][j]
    return max(dp[-1])
print(knapsack(n,w,nw,nv))

Submission status: Wrong Answer

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

dp=[0]*(W+1)
print(dp)
for item in range(N):
     w,v=map(int,input().split())

     for weight in range(W-w,-1,-1):
          dp[weight+w] =  max( dp[weight+w] , dp[weight]+v)

print(max(dp))

Submission status: Wrong Answer

Solution code:
#19:00
n, wm = [int(x) for x in input().strip().split()]
w = []
v = []
for i in range(n):
    wi, vi = [int(x) for x in input().strip().split()]
    w.append(wi)
    v.append(vi)

dp = {}
def solve(i,wr, cv):
    # if wr==0:
    #     return cv
    
    if i>=n:
        return cv
    if i in dp and wr in dp[i]:
            return dp[i][wr]

    if wr>=w[i]:
        # print(i,wr,cv,'in1')
        if i not in dp:
            dp[i] = {}
        dp[i][wr] = max(solve(i+1,wr-w[i], cv+v[i]),solve(i+1,wr,cv))
    else:
        if i not in dp:
            dp[i] = {}
        # print(i,wr,cv,'in2')
        dp[i][wr] = cv
    
    return dp[i][wr]

print(solve(0,wm,0))
# print(dp)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(500000)

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

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

#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

@lru_cache(maxsize=None)
def solve(total, i):
    if i > n-1:
        return 0
    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        return max(chose, unchose)
    else:
        return 0

print(solve(0, 0))

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
#input
n,w = map(int,input().split())
object = [list(map(int,input().split())) for _ in range(n)]

#initialization
dp = [[0 for _ in range(100100)] for _ in range(110)]

#dp algorithm
for i in range(n):
  for sum_w in range(w+1):
    #add value
    if sum_w - object[i][0] >= 0:
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - object[i][0]] + object[i][1]);
    #not add value
    dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w]);

#output
print(dp[n])

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_d
#input
n,w = map(int,input().split())
object = [list(map(int,input().split())) for _ in range(n)]

#initialization
dp = [[0 for _ in range(100100)] for _ in range(110)]

#dp algorithm
for i in range(n):
  for sum_w in range(w+1):
    #add value
    if sum_w - object[i][0] >= 0:
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - object[i][0]] + object[i][1]);
    #not add value
    else:
      dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w]);

#output
print(dp[n][w])

Submission status: Wrong Answer

Solution code:
n, W = map(int, input().split())
w, v = [], []

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

#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

def solve(total, i):
    if i > n-1:
        return 0
    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        return max(chose, unchose)
    else:
        return 0

print(solve(0, 0))

Submission status: Wrong Answer

Solution code:
import numpy as np
n,W=map(int,input().split())
w=[]
v=[]
arr=[]
for i in range(n):
    tempw,tempv=map(int,input().split())
    w.append(tempw)
    v.append(tempv)
    arr.append(tempw/tempv)
sum=0
while W>0 and len(w)>0:
    sum+=v[arr.index(max(arr))]
    W-=w[arr.index(max(arr))]
    w.pop(arr.index(max(arr)))
    v.pop(arr.index(max(arr)))
    arr.pop(arr.index(max(arr)))
print(sum)

Submission status: Wrong Answer

Solution code:
from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
 
baggage = [0]*N
 
for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)
 
dp = [[0]*(W+1) for _ in range(N+1)]
 
for i in range(N):
    for w in range(W+1):
        if w >= baggage[i][0]:
            dp[i+1][w] = max(baggage[i][1]+dp[i][w-baggage[i][0]],dp[i][w])
 
        dp[i+1][w] = dp[i][w]
print(dp[N][W])

Submission status: Wrong Answer

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 = [[int(0) for i in range(W+1)] for i in range(N+1)]
ans = int(0)
dp[0][0] = 0


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

ans = dp[N][W]

print(ans)

Submission status: Wrong Answer

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 = [[int(0) for i in range(W+1)] for i in range(N+1)]
ans = int(0)
dp[0][0] = 0


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

ans = dp[N][W]

print(ans)

Submission status: Wrong Answer

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 = [[int(0) for i in range(W+1)] for i in range(N+1)]
ans = int(0)
dp[0][0] = 0


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

ans = dp[N][W]

print(ans)

Submission status: Wrong Answer

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 = [[int(0) for i in range(W+1)] for i in range(N+1)]
ans = int(0)
dp[0][0] = 0


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

#ans = max(max(dp))
ans = dp[N][W]

print(ans)

Submission status: Wrong Answer

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 = [[int(0) for i in range(W+1)] for i in range(N+1)]
ans = int(0)
dp[0][0] = 0


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

ans = max(max(dp))

print(ans)

Submission status: Wrong Answer

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 = [[int(0) for i in range(W+1)] for i in range(N)]
ans = int(0)
dp[0][0] = 0


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

ans = max(max(dp))

print(ans)

Submission status: Wrong Answer

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

w = [0 for _ in range(N)]
v = [0 for _ in range(N)]

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

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

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

Submission status: Wrong Answer

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

dp = [[0]*(W+1) for i in range(n)]
w0,v0 = weights[0],values[0]

for j in range(w0,n+1):
    dp[0][j] = v0

for i in range(1,n):
    wI = weights[i]
    vI = values[i]
    for j in range(1,W+1):
##        if currentItem does not fit
        if wI>j:
            dp[i][j] = dp[i-1][j]
##            take values acheived by previous items
        else:
            dp[i][j] = max(dp[i-1][j],vI+dp[i-1][j-wI])
##            max between chosing and not choosing
##            if choosing:
##                myvalue + dp[i-1][(j-wI){left-overspace}]{utilise leftover space}          
#             else:
#                 whatever value for this weightyou got before this

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,w = [int(i) for i in input().split()]
arr = []
for i in range(n):
    arr.append([int(i) for i in input().split()])
arr.sort(reverse= True, key = lambda i:i[0])

dp = [[-1 for i in range(w+1)] for i in range(3)]

def cal(i,w):

    if i>=len(arr) or w==0:
        return 0
    
    if w<arr[i][0]:
        return cal(i+1, w)

    
    elif dp[i%2][w]==-1:
        dp[i%2][w] = max(arr[i][1] + cal(i+1,w-arr[i][0]) , cal(i+1, w))
    return dp[i%2][w]

print(cal(0,w))

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**9)
n,w = [int(i) for i in input().split()]
arr = []
for i in range(n):
    arr.append([int(i) for i in input().split()])
arr.sort(reverse= True, key = lambda i:i[0])

dp = [[-1 for i in range(w+1)] for i in range(3)]

def cal(i,w):

    if i>=len(arr) or w==0:
        return 0
    
    if w<arr[i][0]:
        return cal(i+1, w)

    
    elif dp[i%2][w]==-1:
        dp[i%2][w] = max(arr[i][1] + cal(i+1,w-arr[i][0]) , cal(i+1, w))
    return dp[i%2][w]

print(max(0,cal(0,w)))

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**9)
n,w = [int(i) for i in input().split()]
arr = []
for i in range(n):
    arr.append([int(i) for i in input().split()])

dp = [[-1 for i in range(w+1)] for i in range(3)]

def cal(i,w):

    if i==len(arr) and w>=0:
        return 0
    if i>=len(arr):
        return -1000000000
    
    if w<0:
        return -1000000000
    if w==0:
        return 0
    
    elif dp[i%2][w]==-1:
        dp[i%2][w] = max(arr[i][1] + cal(i+1,w-arr[i][0]) , cal(i+1, w))
    return dp[i%2][w]

print(max(0,cal(0,w)))

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**9)
n,w = [int(i) for i in input().split()]
arr = []
for i in range(n):
    arr.append([int(i) for i in input().split()])

dp = [[-1 for i in range(n+2)] for i in range(w+1)]

def cal(i,w):

    if i==len(arr) and w==0:
        return 0
    if i>=len(arr):
        return -1000000000
    
    if w<0:
        return -1000000000
    if w==0:
        return 0
    
    elif dp[w][i]==-1:
        dp[w][i] = max(arr[i][1] + cal(i+1,w-arr[i][0]) , cal(i+1, w))
    return dp[w][i]

    
print(max(0,cal(0,w)))

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**9)
n,w = [int(i) for i in input().split()]
arr = []
for i in range(n):
    arr.append([int(i) for i in input().split()])

dp = [[-1 for i in range(n+2)] for i in range(w+1)]

def cal(i,w):

    if i==len(arr) and w==0:
        return 0
    if i>=len(arr):
        return -1000000000
    
    if w<0:
        return -1000000000
    if w==0:
        return 0
    
    elif dp[w][i]==-1:
        dp[w][i] = max(arr[i][1] + cal(i+1,w-arr[i][0]) , cal(i+1, w))
    return dp[w][i]

    
print(cal(0,w))

Submission status: Wrong Answer

Solution code:
def knapsack(C,n,wei,val,mat):
    if(C==0 or n==0):
        return 0
    else:
        if(C>=wei[n-1]):
            a=mat[C-wei[n-1]][n-1]+val[n-1]
            b=mat[C][n-1]
            if(a==(val[n-1]-1)):
                a=knapsack(C-wei[n-1],n-1,wei,val,mat)+val[n-1]
                mat[C-wei[n-1]][n-1]=a
            if(b==-1):
                b=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=b
            mat[C][n]=max(a,b)
            return (max(a,b))
        else:
            alp=matrix[C][n-1]
            if(alp==-1):
                alp=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=alp
                mat[C][n]=alp
            return (alp)
N,W=map(int,input().split())
matrix=[[-1 for i in range(0,N+1)]for j in range(0,W+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,input().split())
    weights.append(w)
    values.append(v)
knapsack(W,N,weights,values,matrix)
print(matrix[W][N])

Submission status: Wrong Answer

Solution code:
def knapsack(C,n,wei,val,mat):
    if(C==0 or n==0):
        return 0
    else:
        if(C>=wei[n-1]):
            a=mat[C-wei[n-1]][n-1]+val[n-1]
            b=mat[C][n-1]
            if(a==(val[n-1]-1)):
                a=knapsack(C-wei[n-1],n-1,wei,val,mat)+val[n-1]
                mat[C-wei[n-1]][n-1]=a
            if(b==-1):
                b=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=b
            mat[C][n]=max(a,b)
            return (max(a,b))
        else:
            alp=matrix[C][n-1]
            if(alp==-1):
                alp=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=alp
            return (alp)
N,W=map(int,input().split())
matrix=[[-1 for i in range(0,N+1)]for j in range(0,W+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,input().split())
    weights.append(w)
    values.append(v)
knapsack(W,N,weights,values,matrix)
print(matrix[W][N])

Submission status: Wrong Answer

Solution code:
def knapsack(C,n,wei,val):
    if(C==0 or n==0):
        return 0
    else:
        if(C>=wei[n-1]):
            a=matrix[C-wei[n-1]][n-1]+val[n-1]
            b=matrix[C][n-1]
            if(a==(val[n-1]-1)):
                a=knapsack(C-wei[n-1],n-1,wei,val)+val[n-1]
                matrix[C-wei[n-1]][n-1]=a
            if(b==-1):
                b=knapsack(C,n-1,wei,val)
                matrix[C][n-1]=b
            matrix[C][n]=max(a,b)
            return (max(a,b))
        else:
            return (knapsack(C,n-1,wei,val))
N,W=map(int,input().split())
matrix=[[-1 for i in range(0,N+1)]for j in range(0,W+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,input().split())
    weights.append(w)
    values.append(v)
print(knapsack(W,N,weights,values))

Submission status: Wrong Answer

Solution code:
# 入力
num, weight_limit = map(int, input().split())
wv_list = [list(map(int, input().split())) for _ in range(num)]

# dpの初期化
dp = [-1 for _ in range(weight_limit + 1)]
dp[0] = 0

for n in range(1, num + 1):

    # print(f'{"="*15} {n} {"="*15}')

    value = wv_list[n-1][1]
    weight = wv_list[n-1][0]

    for w in range(weight_limit, weight - 1, -1):

        # print(f'{w} {"-"*8}')

        if dp[w - weight] >= 0:
            dp[w] = value + dp[w - weight]

        # print(f'\t{dp}')

print(max(dp))

Submission status: Wrong Answer

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

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] != -1 and dp[i + w] > dp[i] + v:
                dp[i + w] = dp[i] + v

    print(max(dp))

main()

Submission status: Wrong Answer

Solution code:
n, max_weight = map(int, input().split())
dp = [[0 for _ in range(max_weight+1)] for _ in range(n+1)]

for i in range(n):
    weight, value = map(int,input().split())
    for w in range(max_weight+1):
        if w+weight <= max_weight:
            if w < weight:
                dp[i+1][w] = dp[i][w]
            dp[i+1][w+weight] = max(dp[i][w] + value, dp[i][w+weight])
print(dp[n][max_weight])

Submission status: Wrong Answer

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,W = MAP()
weight=[]
value=[]
for i in range(N):
    w,v = MAP()
    weight.append(w)
    value.append(v)

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

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

        dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w-weight[i]])

print(dp[N][W])

Submission status: Wrong Answer

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,W = MAP()
weight=[]
value=[]
for i in range(N):
    w,v = MAP()
    weight.append(w)
    value.append(v)

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

for i in range(N):
    for sum_w in range(W+1):
        print(i,sum_w)
        if sum_w-weight[i]>=0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w-weight[i]])

print(dp[N][W])

Submission status: Wrong Answer

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[i])
print(dp[-1][-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

    if N==1:
        return items[0][1]

    # items = sorted(items, key=lambda x:x[1], reverse=True)
    # items = sorted(items, key=lambda x:x[0])

    dp=list()
    dp.append([W,0])

    result = 0
    for index,i in enumerate(items):
        tmp=list()
        if index==0:
            tmp.append([dp[0][0] - i[0], i[1]])
            tmp.append([dp[0][0], dp[0][1]])
        else:
            for d in dp[index]:
                if d[0]-i[0] >=0:
                    tmp.append([d[0] - i[0], d[1]+i[1]])
                    tmp.append([d[0], d[1]])
                    result=max(result,d[1]+i[1])
        dp.append(tmp)

    return result

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

Submission status: Wrong Answer

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

    if N==1:
        return items[0][1]

    # items = sorted(items, key=lambda x:x[1], reverse=True)
    # items = sorted(items, key=lambda x:x[0])

    dp=list()
    dp.append([W,0])


    for index,i in enumerate(items):
        tmp=list()
        if index==0:
            tmp.append([dp[0][0] - i[0], i[1]])
            tmp.append([dp[0][0], dp[0][1]])
        else:
            for d in dp[index]:
                if d[0]-i[0] >=0:
                    tmp.append([d[0] - i[0], d[1]+i[1]])
                    tmp.append([d[0], d[1]])
        dp.append(tmp)

    result = 0
    for i in dp[1:]:
        for j in i:
            result=max(result, j[1])

    return result

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

Submission status: Wrong Answer

Solution code:

def Knapsack_1():
    N,W = map(int, input().split())
    items = list(list(map(int, input().split())) for _ in range(N))

    if N==1:
        return items[0][1]

    items = sorted(items, key=lambda x:x[0])
    items = sorted(items, key=lambda x:x[1], reverse=True)

    total = [0,0]
    for i,wv in enumerate(items):
        print(i,wv)
        if total[0]+wv[0] <= W:
            total[0] += wv[0]
            total[1] += wv[1]
    return total[1]

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

Submission status: Wrong Answer

Solution code:
import random
import copy
from collections import Counter

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):
    r = [random.randint(0,1) for _ in range(gene_length)]
    child = [parent1[i] if r[i] else parent2[i] for i in range(gene_length)]
    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
    weight = 0
    for i in range(N):
        if pop[i]:
            value += L[i][1]
            weight += L[i][0]
    if weight <= W:
        return value
    else:
        return 0

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

ans = []
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 = 100
generation = 300
mutate_rate = 0.1
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(eva[0][0])

Submission status: Wrong Answer

Solution code:
import random
import copy
from collections import Counter

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):
    r = [random.randint(0,1) for _ in range(gene_length)]
    child = [parent1[i] if r[i] else parent2[i] for i in range(gene_length)]
    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
    weight = 0
    for i in range(N):
        if pop[i]:
            value += L[i][1]
            weight += L[i][0]
    if weight <= W:
        return value
    else:
        return 0

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

ans = []
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 = 20
generation = 150
mutate_rate = 0.1
elite_rate = 0.2

for _ in range(3):
    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)
    ans.append(pop[0][0])

counter = Counter(ans)

print(counter.most_common()[0][0])

Submission status: Wrong Answer

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):
    r = [random.randint(0,1) for _ in range(gene_length)]
    child = [parent1[i] if r[i] else parent2[i] for i in range(gene_length)]
    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 = 50
generation = 500
mutate_rate = 0.1
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: Wrong Answer

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):
    r = [random.randint(0,1) for _ in range(gene_length)]
    child = [parent1[i] if r[i] else parent2[i] for i in range(gene_length)]
    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 = 50
generation = 500
mutate_rate = 0
elite_rate = 0.1

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