무게가 실수 float인 배낭 문제에 필요한 테크닉

4781번: 사탕 가게

 

 

가지고 있는 돈이 있고 사탕의 가격과 칼로리가 주어질때, 주어진 돈으로 얻을 수 있는 최대 칼로리를 구하는 문제

 

각 사탕은 중복해서 구매할 수 있다

 

무한 배낭 문제인데 특이한 점은 무게가 소수점 둘째자리까지 주어진다는 점

 

배낭 문제로 해결하고 싶어도 배열의 크기는 실수로 만들수 없다

 

그러면 어떻게 해야할까?

 

소수점 둘째자리까지 주어지기 때문에, 실수인 가격을 모두 100을 곱해서 정수로 만들면 모두 동등하게 100을 곱했기 때문에 아무 문제가 없다

 

그리고 무한 배낭 문제이기 때문에 무게를 순회할때는 정방향으로 순회하도록

 

for i in range(p,m+1): 이렇게

 

from sys import stdin

while 1:

    n,m = stdin.readline().rstrip().split()

    n = int(n)
    m = float(m)*100
    m = int(m)

    if n == 0 and m == 0:
        
        break

    candy = []

    for _ in range(n):
        
        c,p = stdin.readline().rstrip().split()
        c = int(c)
        p = float(p)*100
        p = int(p)

        candy.append((c,p))
    
    dp = [0]*(m+1)

    for c,p in candy:
        
        for i in range(p,m+1):
            
            dp[i] = max(dp[i],dp[i-p] + c)
    
    print(dp[m])

 

 

근데 이렇게 하면 틀렸습니다 나오더라고

 

왜 그런지 생각해보니 부동 소수점 오차 때문인것 같다

 

1.13*100만 해도 113이 되어야하는데 112가 되어버리는 대참사

 

 

 

그래서 문자열 그대로 받고 .을 기준으로 split한 다음에 첫번째와 두번째를 그대로 합치고 int()로 바꿔줌

 

처음에 문자열 받고 0번 원소 2번 원소 3번 원소를 합해서 했는데... 이건 당연히 오답

 

10.12는 0번 원소가 1이고 2번 원소가 . 3번 원소가 1이라서.. 1.1이 되잖아

 

10.12를 .을 기준으로 split해서 ['10','12']로 만들고 이를 합쳐서 '1012'로 한다음 int로 바꿔줘

 

#무게가 실수인 무한 배낭 문제
#무게는 소수점 둘째자리까지만 주어짐
from sys import stdin

while 1:

    n,m = stdin.readline().rstrip().split()

    n = int(n)
    
    #무게에 100을 곱해서 모두 정수로 바꾼다
    #그냥 100을 곱하면 부동소수점 오차가 나기 때문에
    #.을 기준으로 split해서 두 원소를 합치고 int로 바꾼다
    temp = m.split('.')
    m = temp[0] + temp[1]
    m = int(m)

    if n == 0 and m == 0:
        
        break

    candy = []

    for _ in range(n):
        
        c,p = stdin.readline().rstrip().split()
        c = int(c)
        temp = p.split('.')
        p = temp[0] + temp[1]
        p = int(p)

        candy.append((c,p))
    
    dp = [0]*(m+1)

    for c,p in candy:
        
        for i in range(p,m+1): #중복해서 담을 수 있는 무한 배낭 문제라서 정방향 순회
            
            dp[i] = max(dp[i],dp[i-p] + c)
    
    print(dp[m])