Problem:


0-1 Knapsack Problem

You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

The total value of the items is as large as possible.

The items have combined weight at most W, that is capacity of the knapsack.

Find the maximum total value of items in the knapsack.

Input

N W
v1 w1
v2 w2
:
vN wN

The first line consists of the integers N and W. In the following lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Constraints

 1 ≤ N ≤ 100
	

 1 ≤ vi ≤ 1000
	

 1 ≤ wi ≤ 1000
	

 1 ≤ W ≤ 10000
	

Sample Input 1

4 5
4 2
5 2
2 1
8 3

Sample Output 1

13

Sample Input 2

2 20
5 9
4 10

Sample Output 2

9



Sample input:
4 5
4 2
5 2
2 1
8 3


Sample output:
13

Submission status: Accepted

Solution code:
# coding: utf-8

def array2d(d1, d2, init = None):
    return [[init for _ in range(d2)] for _ in range(d1)]


def solve(N, W, v, w):
    # dp[i][k]: 0~i?????????item????????????????????????????????????k??¨??????????????????????????´??????max value
    # return: max(dp[N-1][*])
    # dp[i][k] = max(dp[i-1][k], dp[i-1][k-w[i]] + v[i])
    # dp[i][0] = 0, dp[0][k] = 0(k<w[0]), v[0](otherwise)
    dp = array2d(N, W + 1)
    for k in range(0, W + 1):
        dp[0][k] = 0 if k < w[0] else v[0]
    for i in range(1, N):
        for k in range(0, W + 1):
            dp[i][k] = dp[i-1][k]
            if k - w[i] >= 0:
                dp[i][k] = max(dp[i][k], dp[i-1][k-w[i]] + v[i])
    return max(dp[-1])



def main():
    N, W = map(int, input().split())
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = map(int, input().split())
    print(solve(N, W, v, w))

main()

Submission status: Accepted

Solution code:
# coding: utf-8

def array2d(d1, d2, init = None):
    return [[init for _ in range(d2)] for _ in range(d1)]


def solve(N, W, v, w):
    # dp[i][k]: 0~i?????????item????????????????????????????????????k??¨??????????????????????????´??????max value
    # return: max(dp[N-1][*])
    # dp[i][k] = max(dp[i-1][k], dp[i-1][k-w[i]] + v[i])
    # dp[i][k] = v[i](k==w[i]), 0(otherwise)
    dp = array2d(N, W + 1)
    for k in range(0, W + 1):
        dp[0][k] = v[0] if k == w[0] else 0
    for i in range(1, N):
        for k in range(0, W + 1):
            dp[i][k] = dp[i-1][k]
            if k - w[i] >= 0:
                dp[i][k] = max(dp[i][k], dp[i-1][k-w[i]] + v[i])
    return max(dp[-1])



def main():
    N, W = map(int, input().split())
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = map(int, input().split())
    print(solve(N, W, v, w))

main()

Submission status: Accepted

Solution code:
# coding: utf-8

def array2d(d1, d2, init = None):
    return [[init for _ in range(d2)] for _ in range(d1)]


def solve(N, W, v, w):
    # dp[i][k]: 0~i?????????item????????????????????????k??\?????¨??????????????????????????´??????max value
    # return: dp[N-1][W]
    # dp[i][k] = max(dp[i-1][k], dp[i-1][k-w[i]] + v[i])
    # dp[i][0] = 0, dp[0][k] = 0(k<w[0]), v[0](otherwise)
    dp = array2d(N, W + 1)
    for k in range(0, W + 1):
        dp[0][k] = 0 if k < w[0] else v[0]
    for i in range(1, N):
        for k in range(0, W + 1):
            dp[i][k] = dp[i-1][k]
            if k - w[i] >= 0:
                dp[i][k] = max(dp[i][k], dp[i-1][k-w[i]] + v[i])
    return dp[N-1][W]



def main():
    N, W = map(int, input().split())
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = map(int, input().split())
    print(solve(N, W, v, w))

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os


# Num, Capacity
N, C = map(int, input().split())

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

# d[i][j]
# i: i???????????§??????????????????
# j: ??????j
# d: ????????¨????????????????????§???
# size: N x C
d = [[0 for i in range(C+1)] for j in range(N)]

# j = 0?????¨????????¨??¨0
# i = 0?????¨???
for j in range(C+1):
    if j >= w[0]:
        d[0][j] = v[0]

# dp
for i in range(N):
    for j in range(C+1):
        # ??\?????????
        if w[i] > j:
            d[i][j] = d[i-1][j]
        # ??\???
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-w[i]] + v[i])

print(d[N-1][C])

Submission status: Accepted

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

for _ in range(N):
    v, w = list(map(int, input().split()))
    v_list.append(v)
    w_list.append(w)

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

for i in range(1, N+1):
    item = v_list[i-1], w_list[i-1]
    for w in range(1, W+1):
        if item[1] > w:
            sum_v_table[i][w] = sum_v_table[i-1][w]
            continue
        sum_v_table[i][w] = max(sum_v_table[i-1][w], sum_v_table[i-1][w-item[1]] + item[0])

max_sum_v = sum_v_table[N][W]

print(max_sum_v)

Submission status: Accepted

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

C = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for w in range(1, W+1):
        if items[i-1][1] <= w:
            if items[i-1][0] + C[i-1][w-items[i-1][1]] > C[i-1][w]:
                C[i][w] = items[i-1][0] + C[i-1][w-items[i-1][1]]
            else:
                C[i][w] = C[i-1][w]
        else:
            C[i][w] = C[i-1][w]
print(C[-1][-1])

Submission status: Accepted

Solution code:
def knapsack(items, num, weight):
    r = weight + 1
    C = [[0] * r for i in range(num + 1)]
    
    for i, item in enumerate(items, start=1):
        item_v, item_w = item
        for w in range(1, r):
            if item_w <= w:
                v1 = item_v + C[i - 1][w - item_w]
                v2 = C[i - 1][w]
                C[i][w] = max(v1, v2)
            else:
                C[i][w] = C[i - 1][w]
    return C[-1][-1]

import sys

file_input = sys.stdin

N, W = map(int, file_input.readline().split())

items = [map(int, line.split()) for line in file_input]

ans = knapsack(items, N, W)

print(ans)

Submission status: Accepted

Solution code:
N,W=[int(i) for i in input().split(" ")]
v=[]
w=[]
for i in range(N):
	vw=input().split(" ")
	v.append(int(vw[0]))
	w.append(int(vw[1]))



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

for i in range(N):
	array[i+1]=array[i].copy()
	for j in range(W):
		try:
			array[i+1][w[i]+j]=max(array[i+1][w[i]+j],array[i][j]+v[i],array[i][w[i]+j])
		except:
			pass


print (array[-1][-1])

Submission status: Accepted

Solution code:
def knapsack(items, num, weight):
    C = [0] * (weight + 1)
    for i in items:
        item_v, item_w = i
        for w in range(weight, 0, -1):
            if item_w <= w:
                v1 = item_v + C[w - item_w]
                v2 = C[w]
                C[w] = max(v1, v2)
    return C[weight]

import sys

file_input = sys.stdin

N, W = map(int, file_input.readline().split())

items = [map(int, line.split()) for line in file_input]

ans = knapsack(items, N, W)

print(ans)

Submission status: Accepted

Solution code:
def knapsack(items, num, weight):
    C = [0] * (weight + 1)
    for i in items:
        item_v, item_w = i
        for w in range(weight, item_w - 1, -1):
            v1 = item_v + C[w - item_w]
            v2 = C[w]
            C[w] = max(v1, v2)
    return C[weight]

import sys

file_input = sys.stdin

N, W = map(int, file_input.readline().split())

items = [map(int, line.split()) for line in file_input]

ans = knapsack(items, N, W)

print(ans)

Submission status: Accepted

Solution code:
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C[item_w:], C)):
            C[i] = max(vals[0] + item_v, vals[1])
    print(C[0])

solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C[item_w:], C)):
            v1, v2 = vals
            C[i] = max(v1 + item_v, v2)
    print(C[0])

solve()

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
item = [[None,None]]
for i in range(N):
    v,w = map(int, input().split())
    item.append([v,w])
C = [[0 for i in range(W+1)]] + [[0] + [None for i in range(W)] for i in range(N)]

for i in range(1, N+1):
    for w in range(1, W+1):
        if item[i][1] <= w:
            if item[i][0] + C[i-1][w - item[i][1]] > C[i-1][w]:
                C[i][w] = item[i][0] + C[i-1][w - item[i][1]]
            else:
                C[i][w] = C[i-1][w]
        else:
            C[i][w] = C[i-1][w]
print(str(C[N][W]))

Submission status: Accepted

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

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

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


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

Submission status: Accepted

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

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

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

print(value[W])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
Nap = []

n,m = map(int,input().split())
for i in range(n):
    v,w = map(int,input().split())
    Nap.append([v,w])
DP = [[0 for j in range(m + 1)] for i in range(n + 1)]
for i in range(1,n+1):
        for j in range(m+1):
            if j - Nap[i-1][1] >= 0:
                DP[i][j] = max(DP[i-1][j],DP[i - 1][j - Nap[i - 1][1]] + Nap[i - 1][0])
            else:
                DP[i][j] = DP[i-1][j]
print(DP[n][m])

Submission status: Accepted

Solution code:
[N,W] = list(map(int,input().split()))
vl = [0]
wl = [0]
for i in range(N):
  [v,w] = list(map(int,input().split()))
  vl.append(v)
  wl.append(w)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N+1):
  for j in range(W+1):
    if i == 0 or j == 0:
      dp[i][j] = 0
    else:
      if wl[i] <= j:
        dp[i][j] = max(dp[i-1][j-wl[i]] + vl[i], dp[i-1][j])
      else:
        dp[i][j] = dp[i-1][j]

print(dp[N][W])

Submission status: Accepted

Solution code:
N, W = list(map(int,input().split()))
v = []
w = []
C = list([0 for i in range(W + 1)] for j in range(N + 1))
for i in range(N):
    n, m = list(map(int,input().split()))
    v.append(n)
    w.append(m)
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if j - w[i - 1] < 0:
            C[i][j] = C[i-1][j]
        else:
            C[i][j] = max(int(C[i-1][j]),int(C[i-1][j-w[i - 1]]+v[i - 1]))
print(int(C[N][W]))

Submission status: Accepted

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

N, W = map(int, readline().split())
a = [(v, w) for _ in [None]*N for v, w in (map(int, readline().split()),)]

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

weight = {0}
for i in range(N):
    item_value, item_weight = a[i]
    for w in weight.copy():
        dp[i+1][w] = dp[i+1][w] if dp[i+1][w] > dp[i][w] else dp[i][w]
        nvalue = dp[i][w] + item_value
        if w+item_weight <= W:
            dp[i+1][w+item_weight] = nvalue if nvalue > dp[i+1][w+item_weight] else dp[i+1][w+item_weight]
            weight.add(w+item_weight)

print(max(dp[N]))

Submission status: Accepted

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

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

dp = [0] * (W+1)

weights = {0}
add = weights.add
for i in range(N):
    item_v, item_w = map(int, readline().split())
    for w in sorted(weights, reverse=True):
        if w+item_w <= W and dp[w+item_w] < dp[w] + item_v:
            dp[w+item_w] = dp[w] + item_v
            add(w+item_w)

print(max(dp))

Submission status: Accepted

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

items = []
for _ in range(n):
    v, w = input().split()
    items.append((int(v), int(w)))

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

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

print(dp[W][n])

Submission status: Accepted

Solution code:
from collections import defaultdict

memo = {}
def dfs(i, w, item_list, W):
    if i >= len(item_list):
        return 0

    if (i, w) in memo:
        return memo[(i, w)]

    ans = 0
    # use
    new_w = w + item_list[i][1]
    if new_w <= W:
        ans = max(ans, dfs(i + 1, new_w, item_list, W) + item_list[i][0])

    # not use
    ans = max(ans, dfs(i + 1, w, item_list, W))

    memo[(i, w)] = ans
    return ans


def main():
    N, W = map(int, input().split())
    item_list = []
    for _ in range(N):
        v, w = map(int, input().split())
        item_list.append((v, w))

    print(dfs(0, 0, item_list, W))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def solve(N, W, vs, ws):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        v, w = vs[i], ws[i]
        for j in range(len(dp[0])):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            if j + w < len(dp[0]):
                dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)
    ans = 0
    for line in dp:
        ans = max(line)
    return ans


def main():
    N, W = map(int, input().split())
    vs, ws = [], []
    for _ in range(N):
        v, w = map(int, input().split())
        vs.append(v)
        ws.append(w)

    print(solve(N, W, vs, ws))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve_knapsack(weight, items):
    dp = [[0]*(weight+1) for _ in range(len(items))]
    for i, item in enumerate(items[1:]):
        for w in range(1, weight+1):
            if item[1] <= w:
                if item[0] + dp[i][w-item[1]] > dp[i][w]:
                    dp[i+1][w] = item[0] + dp[i][w-item[1]]
                else:
                    dp[i+1][w] = dp[i][w]
            else:
                dp[i+1][w] = dp[i][w]
    return dp[-1][-1]



if __name__ == '__main__':
    # ??????????????\???
    # f = open('input.txt')
    num_of_sack, total_capacity = [int(x) for x in input().strip().split(' ')]
    items = [[]]
    for _ in range(num_of_sack):
        items.append([int(x) for x in input().strip().split(' ')])
    # f.close()

    # ????????¨???????????¨???
    result = solve_knapsack(total_capacity, items)
    print(result)

Submission status: Accepted

Solution code:
def solve_knapsack(weight, items):
    """
    ???????¨?????????§???????????¶????????????????§£???
    :param weight: ?¨±???????????????????????????
    :param items: ???????????¨???????????¨????????¨????????????????????????????????¨????????????????????£????????????[0]???????????§[1]????????????items[0]?????????????????????
    :return: ??????????¶??????????????????§??¢??????????????°??????????????´????????????????????§???
    """
    dp = [[0]*(weight+1) for _ in range(len(items))] #  ?¨????:???????????????:?????¨????????¢?????????????¨???? ??§2?¬??????????????????????0??§????????????
    for i, item in enumerate(items[1:], start=1):
        for w in range(1, weight+1):
            # i????????¨?????????i-1??????????????????
            if item[1] <= w:
                if item[0] + dp[i-1][w-item[1]] > dp[i-1][w]: #  ????????¢??????????????\???????????¨????????£??????????????????????????????up????????´???
                    dp[i][w] = item[0] + dp[i-1][w-item[1]] #  dp[i-1][w-itemm[1]]??????????????¢??????????????\???????????¨??????????????????????????¨?????????????????¶????????¨????????????
                else:           #  ??¢??????????????????????????´????????????????????????????´?????????????????????????
                    dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = dp[i-1][w]
    return dp[-1][-1]



if __name__ == '__main__':
    # ??????????????\???
    # f = open('input.txt')
    num_of_sack, total_capacity = [int(x) for x in input().strip().split(' ')]
    items = [[]]                #  index[1]??????????????????????????????????????????????????????l0]????????????????????\????????????
    for _ in range(num_of_sack):
        items.append([int(x) for x in input().strip().split(' ')])
    # f.close()

    # ????????¨???????????¨???
    result = solve_knapsack(total_capacity, items)
    print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from copy import deepcopy
N, W = tuple(map(int, input().split()))
items = []
for n in range(N):
    items.append(list(map(int, input().split()))) # value, weight

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

for item in items:
    for w in range(item[1], W+1):
        post_costs[w] = max(pre_costs[w], pre_costs[w-item[1]] + item[0])
    pre_costs = deepcopy(post_costs)

print(post_costs[-1])

Submission status: Accepted

Solution code:
buf = []
v = []
w = []
N, W = list(map(int, input().split()))
dp = [[0 for i in range(W + 1)]for j in range(N + 1)]
for i in range(N):
    buf.append(list(map(int, input().split())))
for i in range(len(buf)):
    v.append(buf[i][0])
    w.append(buf[i][1])

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

Submission status: Accepted

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

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

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

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

print(dp[0][W])

Submission status: Accepted

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

dp = [[-1 for i in range(W+1)] for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    v, w = map(int, input().split())
    for j in range(W):
        if dp[i][j] >= 0:
            try:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j])
                dp[i+1][j+w] = max(dp[i][j]+v, dp[i][j+w])
            except IndexError:
                pass
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n, maxw = list(map(int, input().split()))
v_lis, w_lis = [], []   # in order, list for values, and for weights

# set data
for _ in range(n):
    v, c = list(map(int, input().split()))
    v_lis.append(v)
    w_lis.append(c)

# ?????´???????????????????????´????????§?¨±????????¨??????
# (Outer is for index of products, inner is maximum allowable amount)
dp = [[0 for _ in range(maxw+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, maxw+1):
        if j>=w_lis[i-1]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_lis[i-1]]+v_lis[i-1])
        else:
            dp[i][j] = dp[i-1][j]

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

Submission status: Accepted

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

dp = [0 for _ in range(maxw+1)]
for i in range(n):
    v, c = list(map(int, input().split()))
    for j in range(maxw, -1, -1):
        if j>=c:
            dp[j] = max(dp[j], dp[j-c]+v)
        else:
            break
print(dp[-1])

Submission status: Accepted

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

dp = [0 for _ in range(maxw+1)]
for i in range(n):
    v, c = map(int, input().split())
    for j in range(maxw, -1, -1):
        if j>=c:
            dp[j] = max(dp[j], dp[j-c]+v)
        else:
            break
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

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

def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]

    if i == N:
        res = 0
    elif j < w[i]: 
        res = rec(i + 1, j) 
    else: 
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]) 
        dp[i][j] = res 
    return res 
print(rec(0, W))

Submission status: Accepted

Solution code:

NW=input().split()

N=int(NW[0])
W=int(NW[1])

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

C=[[0 for i2 in range(W+1)]for i1 in range(N+1)]

for i in range(1,N+1):
    for j in range(1,W+1):
        if j>=item[i-1][1]:
            if item[i-1][0]+C[i-1][j-item[i-1][1]]>C[i-1][j]:
                C[i][j]=item[i-1][0]+C[i-1][j-item[i-1][1]]
            else:
                C[i][j]=C[i-1][j]
        else:
            C[i][j]=C[i-1][j]


print(C[N][W])

Submission status: Accepted

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

	w_lis = [0] * N
	v_lis = [0] * N

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



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

			else:
				dp[i][w] = dp[i-1][w]


	print(dp[N][W])

Submission status: Accepted

Solution code:
# 	The program took 8s to solve 36 cases.
# 	The program itself did not take long, because
# I have done it before.

input1 = input().split()
N = int(input1[0]) # No. of items
W = int(input1[1]) # Upper limit of weight

item = [[0]*2 for i in range(N)]
for i in range(N):
	input2 = input().split()
	item[i][0] = int(input2[0])
	item[i][1] = int(input2[1])

v = [[0]*(W+1) for i in range(N)]
for i in range(N):
	for c in range(W+1):
		if (i < 0 or c <= 0):
			v[i][c] = 0
		elif (c-item[i][1] < 0):
			v[i][c] = v[i-1][c]
		else:
			v[i][c] = max(item[i][0] + v[i-1][c-item[i][1]], v[i-1][c])
			
print(v[N-1][W])

Submission status: Accepted

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

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
N,W = map(int, input().split())
dp = [[0 for x in range(W+1)] for y in range(N+1)]

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

print(dp[N][W])

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

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

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

print(dp[N][W])

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

gcdw = reduce(gcd,wtemp+[W])
w = list(map(lambda x:x//gcdw, wtemp))

W2 = W//gcdw
dp = [[0]*(W2+1) for y in range(N+1)]

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

print(dp[N][W2])

Submission status: Accepted

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

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

print(dp[W])

Submission status: Accepted

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

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

print(dp[W])

Submission status: Accepted

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

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

print(dp[W])

Submission status: Accepted

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

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

    temp[0:W+1] = dp[0:W+1]

print(dp[W])

Submission status: Accepted

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

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

print(dp[W])

Submission status: Accepted

Solution code:
M = {}

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


def dfs(i, j):
    if (i, j) in M:
        return M[i, j]
    if i == N:
        return 0

    v, w = items[i]
    if w <= j:
        r = max(dfs(i+1, j), v + dfs(i+1, j-w))
    else:
        r = dfs(i+1, j)
    M[i, j] = r
    return r


print(dfs(0, W))

Submission status: Accepted

Solution code:
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


DP = [[0] * (W+1) for _ in range(N+1)]
# DP[i+1][j] = max(DP[i][j], v + DP[i][j-w])
for i in range(N):
    for j in range(W+1):
        v, w = items[i]
        if w <= j:
            DP[i+1][j] = max(DP[i][j], v + DP[i][j-w])
        else:
            DP[i+1][j] = DP[i][j]

print(DP[-1][-1])

Submission status: Accepted

Solution code:
# 0-1 Knapsack Problem
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))

DP = [0] * (W+1)
for i in range(N):
    v, w = items[i]
    for j in range(W, w-1, -1):
        DP[j] = max(DP[j], v + DP[j-w])

print(DP[-1])

Submission status: Accepted

Solution code:
def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

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

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1][j]=graph[i][j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i][rest]+inputset[i][0]
                nonchoosevalue=graph[i][j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1][j]=choosevalue
                else:
                    graph[i+1][j]=nonchoosevalue

    print(graph[N][W])

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
???????¨???????
???????????¶????????????
'''
N, W = map(int, input().split())

class Item():
    def __init__(self, v, w):
        self.v = v
        self.w = w

items = []

for _ in range(N):
    v, w = map(int, input().split())
    item = Item(v, w)
    items.append(item)

C = dict()
for n in range(N+1):
    C[(n, 0)] = 0

for w in range(W+1):
    C[(0, w)] = 0

for n in range(1, N+1):
    for w in range(1, W+1):
        if w-items[n-1].w < 0:
            C[(n, w)] = C[(n-1, w)]
            continue
        C[(n, w)] = max(C[(n-1, w)], C[(n-1, w-items[n-1].w)] + items[n-1].v)

print(C[(n, w)])

Submission status: Accepted

Solution code:
N,W = raw_input().split()
N=int(N);W=int(W)
v=[]
w=[]
for i in xrange(N):
    vi,wi = raw_input().split()
    vi=int(vi);wi=int(wi)
    v.append(vi)
    w.append(wi)
dp=[[0]*(W+10) for i in xrange(N+10)]
for i in xrange(N):
    for j in xrange(W+1):
        if j>=w[i]:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print dp[N][W]

Submission status: Accepted

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

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

#DP計算
for i in range(N):
    for w in range(W+1):
        if(w >= wei[i]):
            dp[i+1][w] = max(dp[i][w - wei[i]] + val[i],dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(int(dp[N][W]))