Cometin'

BOJ-4781 - Python

2021-01-19 at Algorithm category

한가지 물건을 여러 개 고를 수 있는 냅색 문제. TC만큼 물건의 종류 n, 가방의 크기 m이 주어진다. 이 때 m은 소수로, 소수점 둘째자리까지 주어진다. 다음 n개의 줄에는 각 물건의 값, 무게가 주어진다. 무게도 마찬가지로 소수이다. 기본 냅색 문제는 dp[i-1][j], value + dp[i-1][j-weight] 위 두가지를 비교하면 되지만 이번 문제는 한가지 물건을 여러 개 고를 수도 있기 때문에 dp[i][j-weight] 또한 비교하여야 한다. 입력되는 무게가 소수점 둘째자리까지이기 때문에 100을 곱하여 int를 이용하여 형변환하여 풀었으나 시간초과 결과를 받게 되었는데, 이는 round로 수정하여 풀었다. 실수형을 형변환할 때 round가 더욱 빠른가보다.

import sys
input = sys.stdin.readline

def solve(n, m, costs, prices):
    m += 1
    ans = [[0 for _ in range(m)] for _ in range(n)]

    for i in range(n):
        cost = costs[i]
        price = prices[i]
        for j in range(m):
            if j < price:
                ans[i][j] = ans[i-1][j]
            else:
                ans[i][j] = max(ans[i-1][j], cost + ans[i][j-price], cost + ans[i - 1][j - price])

    return ans[n-1][m-1]

while True:
    n, m = map(float, input().split())
    if n == 0 and m == 0:
        break
    n = int(n)
    m = round(m * 100)


    costs = []
    prices = []
    for _ in range(n):
        c, p = map(float, input().split())
        c = int(c)
        p = round(p * 100)
        costs.append(c)
        prices.append(p)

    print(solve(n, m, costs, prices))

hyesungoh

Personal blog by hyesungoh.

I like to share my knowledge for those who wandering in issue.