Problem:


0-1 Knapsack Problem II

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 N 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 ≤ 100
	

 1 ≤ wi ≤ 10,000,000
	

 1 ≤ W ≤ 1,000,000,000
	

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

Solution code:
a,b = map(int,input().split())
dp = [0 for i in range(b+1)]
for i in range(a):
    x,y = map(int,input().split())
    for j in range(b,y+1,y):
        pp = x + dp[j-y]
        if pp > dp[j]:
            dp[j] = pp
            
print(max(dp))

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split())
dp = [0 for i in range(b+1)]
for i in range(a):
    x,y = map(int,input().split())
    for j in range(b,y+1,-y):
        pp = x + dp[j-y]
        if pp > dp[j]:
            dp[j] = pp
            
print(max(dp))

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split())
dp = [0 for i in range(b+1)]
for i in range(a):
    x,y = map(int,input().split())
    for j in range(b,y-1,-y):
        pp = x + dp[j-y]
        if pp > dp[j]:
            dp[j] = pp
            
print(max(dp))

Submission status: Wrong Answer

Solution code:
N, W = map(int, input().split())
dp = [0] + [W+1] * (N*100)
for i in range(N):
    x, y = map(int, input().split())
    for j in range(i*100, -1, -1):
        if dp[j+y] > dp[j] + x:
            dp[j+y] = dp[j] + x

for v, w in zip(range(N*100, -1, -1), dp[::-1]):
    if w < W+1:
        print(v)
        break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_N, MAX_V = 100, 100


def solve():
    dp = [[float('inf')] * (MAX_N * MAX_V + 1) for _ in range(MAX_N + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(MAX_N * MAX_V):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    for i in range(MAX_N * MAX_V):
        if dp[c_items][i] <= real_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Submission status: Wrong Answer

Solution code:
from math import isfinite
from itertools import dropwhile

n, knapsack = map(int, input().split())
dpn = n * 100  # MAX VALUE
dp = [float('inf')] * (dpn + 1)
dp[0] = 0
for i in range(n):
    value, weight = map(int, input().split())
    for j in range(dpn - value, 0, -1):
        if not isfinite(dp[j]):
            continue
        new_weight = dp[j] + weight
        if new_weight <= knapsack and dp[j + value] > new_weight:
            dp[j + value] = new_weight
    if dp[value] > weight:
        dp[value] = weight

print(next(dropwhile(lambda i: not isfinite(dp[i]), range(dpn, -1, -1))))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_F&lang=jp

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline


def solve(items, W, max_v):
    # ??¨???????????????????????????????????????
    n = len(items)
    dp = [[float('inf')]*(n*max_v + 1) for _ in range(n+1)] #  ?¨??????? ??§????????? ????¨????
    dp[0][0] = 0

    for i, item in enumerate(items):
        for j in range(n * max_v):
            if j < item.v:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-item.v]+item.w)

    for j in range(n * max_v):
        if dp[n][j] <= W:
            result = j
    return result


item = namedtuple('item', ['v', 'w'])
def main(args):
    N, W = map(int, input().split())
    items = []
    for _ in range(N):
        v, w = map(int, input().split())
        items.append(item(v, w))
    items.sort()
    max_v = items[-1].v

    result = solve(items, W, max_v)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
#! /usr/bin/python
# -*- coding:utf-8 -*-

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

dp = dict()
dp[0] = 0
max_v = -1
for i in range(N):
    tmp = dp.copy()
    for k, v in tmp.items():
        dp.setdefault(k+vs[i], float('inf'))
        dp[k+vs[i]] = min(v + ws[i], dp[k+vs[i]])
        if dp[k+vs[i]] <= W:
            max_v = max(max_v, k+vs[i])

#print(dp)
print(max_v)

Submission status: Wrong Answer

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

interim_ans = [0 for i in range(w+1)] # i個目までのアイテムを使う場合の暫定解
best_ans = 0

def branch_and_bound(i, putted, cr_val, cr_weight): # branch and bound: i番目の要素のありなし
    if i >= n: return

    global interim_ans, best_ans
    new_val, new_weight = cr_val, cr_weight
    if putted:
        new_val += items[i][0]
        new_weight += items[i][1]

    if new_weight > w: return
    if interim_ans[new_weight] > new_val: return
    if best_ans < new_val: best_ans = new_val
    if interim_ans[new_weight] < new_val: interim_ans[new_weight] = new_val

    branch_and_bound(i+1, True, new_val, new_weight)
    branch_and_bound(i+1, False, new_val, new_weight)

branch_and_bound(0, True, 0, 0)
branch_and_bound(0, False, 0, 0)

print(best_ans)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 20

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

value = []
weight = []

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

sum_value = sum(value)

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

for i in range(n):
  for j in range(sum_value, value[i] - 1, -1):
    dp[j] = min(dp[j], dp[j - value[i]] + weight[i])

for j in range(sum_value + 1):
  if dp[j] != INF and dp[j] > w:
    print(j - 1)
    break
else:
  print(sum_value)

Submission status: Wrong Answer

Solution code:
N,W = map(int, input().split())
vws = [list(map(int, input().split())) for _ in range(N)]
dp = [-1]*(W+1)
check = {i:[] for i in range(W+1)}
dp[0] = 0

for n in range(N):
	v,w = vws[n]
	for i in range(W+1):
		if i+w > W:
			continue
		if dp[i] == -1 or n in check[i]:
			continue
		dp[i+w] = max(dp[i+w], dp[i]+v)
		check[i+w] = check[i]+[n]
print(max(dp))

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

table = [[0 for j in range(w+1)] for i in range(n+1)]

for i in range(1, n+1):
    v_i, w_i = items[i-1]
    for j in range(1, w+1):
        if j - w_i < 0:
            table[i][j] = max(table[i][j-1], table[i-1][j])
        else:
            new_val = table[i-1][j-w_i] + v_i
            if new_val > table[i][j-1]:
                table[i][j] = max(new_val, table[i][j-1], table[i-1][j])
            else:
                table[i][j] = max(table[i][j-1], table[i-1][j])

print(table[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N,W = map(int, input().split())
vws = [input().split() for _ in range(N)]
vws = list(map(lambda x: int(x[1])*1000+int(x[0]), vws))
dp = [-1]*(W+1)
#check = {i:[] for i in range(W+1)}
dp[0] = 0

for n in range(len(vws)):
	v = vws[n]%1000
	w = (vws[n]-v)//1000
	for i in range(W, -1, -1):
		if i+w > W:
			continue
		if dp[i] == -1:
			continue
		dp[i+w] = max(dp[i+w], dp[i]+v)
		#check[i+w] = check[i]+[n]
print(max(dp))

Submission status: Time Limit Exceeded

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

for n in range(N):
	v,w = vws[n]
	for i in range(W-w, -1, -1):
		if dp[i] == -1:
			continue
		dp[i+w] = max(dp[i+w], dp[i]+v)
print(max(dp))

Submission status: Memory Limit Exceeded

Solution code:
a,b = map(int,input().split())
dp = [0 for i in range(b+1)]
for i in range(a):
    x,y = map(int,input().split())
    for j in range(b,y-1,-1):
        pp = x + dp[j-y]
        if pp > dp[j]:
            dp[j] = pp
            
print(max(dp))

Submission status: Memory Limit Exceeded

Solution code:
a,b = map(int,input().split())
dp = [0 for i in range(b+1)]
for i in range(a):
    x,y = map(int,input().split())
    for j in range(b,y-1,-1):
        pp = x + dp[j-y]
        if pp > dp[j]:
            dp[j] = pp
            
print(max(dp))

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

output:
13
"""

import sys
from collections import namedtuple


# def solve():
#     for i, item in enumerate(item_list, 1):
#         for cp in range(1, real_cp + 1):
#             # capacity allows putting in, calculate value
#             if item.w <= cp:
#                 values[i][cp] = max(values[i - 1][cp], values[i - 1][cp - item.w] + item.v)
#             # can't put in, skip current item
#             else:
#                 values[i][cp] = values[i - 1][cp]
#
#     return values[c_items][real_cp]


def solve_2():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.v, item.w
        for cp in range(real_cp - w, -1, -1):
            dp[cp + w] = max(dp[cp + w], dp[cp] + v)

    return dp[-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('v', 'w'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    # values = [[0] * (real_cp + 1) for _ in range(c_items + 1)]
    print(solve_2())

Submission status: Memory Limit Exceeded

Solution code:
n, knapsack = map(int, input().split())
dp = [0] * (knapsack + 1)
for i in range(n):
    value, weight = map(int, input().split())
    for j in range(knapsack - weight, 0, -1):
        if not dp[j]:
            continue
        new_value = dp[j] + value
        if dp[j + weight] < new_value:
            dp[j + weight] = new_value
    if weight <= knapsack and dp[weight] < value:
        dp[weight] = value
print(max(dp))

Submission status: Memory Limit Exceeded

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

for v, w in zip(range(N*100, -1, -1), dp[::-1]):
    if w < W+1:
        print(v)
        break

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
INF, V = 1 << 40, 100
dp = [[INF for j in range(N*V+1)] for i in range(N+1)]


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

    dp[0][0] = 0
    for i in range(1, N+1):
        for j in range(N*V+1):
            if j < v[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i-1]]+w[i-1])

    ans = 0
    for i in range(N*V+1):
        if dp[N][i] <= W:
            ans = i

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_N, MAX_V = 100, 100


def solve():
    dp = [[float('inf')] * (MAX_N * MAX_V + 1) for _ in range(MAX_N + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(MAX_N * MAX_V + 1):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    for i in range(MAX_N * MAX_V + 1):
        if dp[c_items][i] <= real_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_V = 100


def solve():
    dp = [[float('inf')] * (c_items * MAX_V + 1) for _ in range(c_items + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(c_items * MAX_V + 1):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    for i in range(c_items * MAX_V + 1):
        if dp[c_items][i] <= knapsack_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, knapsack_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
2 20
5 9
4 10

output:
9

1 ??? N ??? 100
1 ??? vi ??? 100
1 ??? wi ??? 10,000,000
1 ??? W ??? 1,000,000,000
"""

import sys
from collections import namedtuple

MAX_V = 100


def solve():
    dp = [[float('inf')] * (c_items * MAX_V + 1) for _ in range(c_items + 1)]
    dp[0][0] = 0
    for i, item in enumerate(item_list):
        v, w = item.value, item.weight
        for j in range(c_items * MAX_V + 1):
            if j < v:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)

    ans = 0
    res_list = dp[-1]
    for i in range(c_items * MAX_V + 1):
        if res_list[i] <= knapsack_cp:
            ans = i

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, knapsack_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('value', 'weight'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Submission status: Accepted

Solution code:
from math import isfinite
from itertools import dropwhile

n, knapsack = map(int, input().split())
dpn = n * 100  # MAX VALUE
dp = [float('inf')] * (dpn + 1)
dp[0] = 0
for i in range(n):
    value, weight = map(int, input().split())
    for j in range(dpn - value, 0, -1):
        if not isfinite(dp[j]):
            continue
        new_weight = dp[j] + weight
        if new_weight <= knapsack and dp[j + value] > new_weight:
            dp[j + value] = new_weight
    if weight <= knapsack and dp[value] > weight:
        dp[value] = weight

print(next(dropwhile(lambda i: not isfinite(dp[i]), range(dpn, -1, -1))))

Submission status: Accepted

Solution code:
from math import isfinite

n, knapsack = map(int, input().split())
dpn = n * 100  # MAX VALUE
dp = [float('inf')] * (dpn + 1)
dp[0] = 0
for i in range(n):
    value, weight = map(int, input().split())
    for j in range(dpn - value, -1, -1):
        if not isfinite(dp[j]):
            continue
        new_weight = dp[j] + weight
        if new_weight <= knapsack and dp[j + value] > new_weight:
            dp[j + value] = new_weight

print(next(filter(lambda i: isfinite(dp[i]), range(dpn, -1, -1))))

Submission status: Accepted

Solution code:
N, W = map(int, raw_input().split())
P = [map(int, raw_input().split()) for i in xrange(N)]
V = sum(v for v, w in P)
dp = [W+1]*(V+1)
dp[0] = 0
for v, w in P:
    for i in xrange(V-v, -1, -1):
        dp[i+v] = min(dp[i+v], dp[i]+w)
for i in xrange(V, -1, -1):
    if dp[i] <= W:
        print i
        break

Submission status: Accepted

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

N, W = map(int, readline().split())
inf = float("inf")
dp = [inf]*(N*100+1)
dp[0] = 0
s = {0}

for i in range(N):
    v, w = map(int, readline().split())
    for _v in sorted(s, reverse=True):
        new_w = dp[_v] + w
        if new_w <= W:
            new_v = v + _v
            dp[new_v] = new_w if new_w < dp[new_v] else dp[new_v]
            s.add(new_v)

for i in range(N*100, -1, -1):
    if dp[i] < inf:
        print(i)
        break

Submission status: Accepted

Solution code:
from collections import defaultdict
INF = 10 ** 10


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

    dp = [[INF] * (N * 100 + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        v, w = items[i]
        for j in range(len(dp[0])):
            if dp[i][j] != INF:
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
                dp[i + 1][j + v] = min(dp[i + 1][j + v], dp[i][j] + w)
    ans = 0
    for i in range(len(dp)):
        for j in range(len(dp[0])):
            if dp[i][j] <= W:
                ans = max(ans, j)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_F&lang=jp

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline


def solve(items, W, max_v):
    # ??¨???????????????????????????????????????
    n = len(items)
    dp = [[float('inf')]*(n*max_v + 1) for _ in range(n+1)] #  ?¨??????? ??§????????? ????¨????
    dp[0][0] = 0

    for i, item in enumerate(items):
        for j in range(n * max_v+1):
            if j < item.v:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-item.v]+item.w)

    for j in range(n * max_v + 1):
        if dp[n][j] <= W:
            result = j
    return result


item = namedtuple('item', ['v', 'w'])
def main(args):
    N, W = map(int, input().split())
    items = []
    for _ in range(N):
        v, w = map(int, input().split())
        items.append(item(v, w))
    items.sort()
    max_v = items[-1].v

    result = solve(items, W, max_v)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

for v, w in zip(range(N*100, -1, -1), dp[::-1]):
    if w < W+1:
        print(v)
        break

Submission status: Accepted

Solution code:
#! /usr/bin/python
# -*- coding:utf-8 -*-

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

dp = dict()
dp[0] = 0
max_v = 0
for i in range(N):
    tmp = dp.copy()
    for k, v in tmp.items():
        dp.setdefault(k+vs[i], float('inf'))
        dp[k+vs[i]] = min(v + ws[i], dp[k+vs[i]])
        if dp[k+vs[i]] <= W:
            max_v = max(max_v, k+vs[i])

#print(dp)
print(max_v)

Submission status: Accepted

Solution code:
INF = 10 ** 20

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

value = []
weight = []

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

sum_value = sum(value)

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

for i in range(n):
  for j in range(sum_value, value[i] - 1, -1):
    dp[j] = min(dp[j], dp[j - value[i]] + weight[i])

for j in range(sum_value, -1, -1):
  if dp[j] <= w:
    print(j)
    break

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] = list(map(int, input().split()))

INF = float('inf')
dp = [[INF] * (sum(v)+1) for _ in range(N+1)]
dp[0][0] = 0

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

#for i in dp:
    #print(i)
ans = 0
cnt = -1
for i in dp[-1]:
    cnt += 1
    if i <= W:
        ans = cnt
print(ans)

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, w = ns()
    dp = [INF for _ in range(n * 100 + 1)]
    dp[0] = 0

    for _ in range(n):
        vi, wi = ns()
        for i in range(n * 100 - vi, -1, -1):
            if dp[i] == INF:
                continue
            if dp[i] + wi <= w:
                dp[i + vi] = min(dp[i + vi], dp[i] + wi)

    for i in range(n * 100, -1, -1):
        if dp[i] != INF:
            print(i)
            exit(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

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



M, W = map(int, input().split())                                # M: 品物の種類 W: 重量制限
single = True                                                   # True = 重複なし

price_list = [0]
weight_list = [0]
for _ in range(M):
    price, weight = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

V = sum(price_list)
dp_max = W + 1                                                  # 総和重量の最大値


dp = [[dp_max] * (V + 1) for _ in range(M + 1)]                 # 左端と上端の境界条件で W, M を一個ずつ多めに取る
""" dp[item <= M ][weight <= V] = 価値を固定した時の"最小"重量 """

for item in range(M+1):                                         # 左端の境界条件
    dp[item][0] = 0                                             # 価値 0 を実現するのに必要な品物の個数は 0 個

# for weight in range(W+1):                                     # 上端の境界条件
#     dp[0][weight] = dp_min                                    # 0 種類の品物で実現できる価値総額は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for price in range(1, V+1):
        if price < price_list[item]:                            # price (総価値) < price_list[item] (品物の価値) の時は無視してよい
            dp[item][price] = dp[item - 1][price]
        else:
            temp = dp[item - single][price - price_list[item]] + weight_list[item]  # single = True: 重複なし
            if temp < dp[item-1][price]:                        # min(dp[item-1][price], temp)
                dp[item][price] = temp
            else:
                dp[item][price] = dp[item-1][price]

print(max(price for price in range(V+1) if dp[M][price] <= W))

Submission status: Accepted

Solution code:
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, W = LI()
    vw = [LI() for _ in range(N)]

    v_sum = sum([i[0] for i in vw])

    # dp[i][j]: [0, i)を使って価値j以上になる場合の重さの最小値
    dp = [[INF] * (v_sum + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        for j in range(v_sum):
            v_p = max(j + 1 - vw[i][0], 0)
            if v_p >= 0:
                dp[i+1][j+1] = min(dp[i][j+1], dp[i][v_p] + vw[i][1])
            else:
                dp[i+1][j+1] = dp[i][j+1]

    # for i in dp:
    #     print(i)
    
    ans = bisect.bisect_right(dp[-1], W) - 1
    print(ans)

if __name__ == '__main__':
    resolve()

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

V=max(v)*N
dp=[-1]*(V+1)
dp[0]=0

for i in range(N):
    for j in range(V+1):
        if dp[V-j]!=-1 and -j+v[i]<=0:
            if dp[V-j+v[i]]==-1:
                dp[V-j+v[i]]=dp[V-j]+w[i]
            else:
                dp[V-j+v[i]]=min(dp[V-j+v[i]],dp[V-j]+w[i])

for i in range(V+1):
    if dp[V-i]!=-1 and dp[V-i]<=W:
        print(V-i)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split()))
# a = tuple(sys.stdin.readline() for _ in range(n))
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys

#for sparse data
# 05_large 11s->6s
import collections

def solve():
  N,W = map(int,sys.stdin.readline().split())
  vw = tuple(tuple(map(int,sys.stdin.readline().split())) for _ in range(N))
  dp = {}
  dp[0] = 0
  #a = sorted(a,reverse=True)
  for v,w in vw:
    temp = dp.copy()
    for j in list(dp.keys()):
      if j+w <= W and (not j+w in dp or dp[j+w] < dp[j]+v):
        temp[j+w] = dp[j]+v
        #dp = {**dp,**temp}
    dp = temp
    #print(w,v,dp)
  print(max(dp.values()))

#weight dp ()
def solve1():
  N,W = map(int,sys.stdin.readline().split())
  vw = tuple(tuple(map(int,sys.stdin.readline().split())) for _ in range(N))
  V = sum(v for v,_ in vw)
  dp = [W+1]*(V+1)
  dp[0] = 0
  for v,w in vw:
    for c_v in range(V+1)[::-1]:
      if 0 <= c_v-v: #select
        dp[c_v] = min(dp[c_v],dp[c_v-v]+w)
    #print(dp)
  for c_v in range(V+1)[::-1]:
    if dp[c_v] <= W:
      return c_v
  return V
print(solve1())

Submission status: Accepted

Solution code:
def KP(Val,Wei,N,W):
    v_sum = sum(Val)
    #dp[i][j]:i番目までの品,価値の合計がjでの最小の重さ
    INF = 10**9+1
    dp = [[INF for _ in range(v_sum+1)] for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

    for i in range(N):
        for j in range(v_sum+1):
            if j - Val[i] >= 0:
                dp[i+1][j] = min(dp[i][j-Val[i]]+Wei[i],dp[i][j])
            else:
                dp[i+1][j] = dp[i][j]

    output = 0
    for j in range(v_sum+1):
        if dp[N][j] <= W:
            output = j

    return output

def main():
    N,W = map(int,input().split())
    VW = [list(map(int,input().split())) for _ in range(N)]
    Val = [VW[i][0] for i in range(N)]
    Wei = [VW[i][1] for i in range(N)]
    ans = KP(Val,Wei,N,W)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,W = map(int, raw_input().split())
vs,ws = [],[]
for i in range(N):
    v,w = map(int, raw_input().split())
    vs.append(v)
    ws.append(w)
V = sum(vs)

DP = [10**10]*(V+1)
DP[0] = 0

for v,w in zip(vs, ws):
    for i in reversed(range(v, V+1)):
        DP[i] = min(DP[i], DP[i-v] + w)

ans = max(v for v,w in enumerate(DP) if w <= W)
print ans

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
VW = [tuple(map(int, input().split())) for i in range(n)]
V = [v for v, w in VW]
W = [w for v, w in VW]
# n, m = 4, 5
# V = [4, 5, 2, 8]
# W = [2, 2, 1, 3]
# DP[i][j]=i個の品物で価値j以上で最小の重さ
sv = sum(V)
inf = 10**10
DP = [[inf for j in range(sv+1)] for i in range(n+1)]
DP[0][0] = 0
for i in range(n):
    for j in range(sv+1):
        if j < V[i]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i][j-V[i]]+W[i])
for j in range(sv, 0, -1):
    if DP[n][j] <= m:
        print(j)
        exit()
print(0)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
vw = [input().split() for _ in range(n)]
vw = [(int(x[0]), int(x[1])) for x in vw]
v_max = sum([x[0] for x in vw])

INF = 10 ** 9 + 1
pdp = [INF for _ in range(v_max+1)]
cdp = [INF for _ in range(v_max+1)]
pdp[0] = 0
cdp[0] = 0

for i in range(n):
    for j in range(v_max+1):
        if j + vw[i][0] < v_max + 1:
            cdp[j + vw[i][0]] = min(pdp[j + vw[i][0]], pdp[j] + vw[i][1])
        else:
            break
    pdp = cdp[:]

ans = INF
for i in range(len(cdp)):
    if cdp[i] <= w:
        ans = i

print(ans)

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    N, W = map(int, f_i.readline().split())
    
    vw = tuple(tuple(map(int, f_i.readline().split())) for i in range(N))
    
    size = sum(vw_i[0] for vw_i in vw)
    inf = 10 ** 9
    dp = [inf] * (size + 1)
    dp[-1] = 0
    
    for v, w in vw:
        for i, tpl in enumerate(zip(dp[v:], dp)):
            w1, w2 = tpl
            w1 += w
            if w1 < w2:
                dp[i] = w1
    
    ans = 0
    for i, w in enumerate(dp[-2::-1], start=1):
        if w <= W:
            ans = i
    
    print(ans)

solve()

Submission status: Accepted

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

V = sum(map(lambda x:x[0],item))

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

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

print(max(j for j in range(V+1) if dp[j] <= W))