[BOJ/백준][Gold5] 4781 : 사탕 가게 (C++)

https://www.acmicpc.net/problem/4781

4781번: 사탕 가게

 

 

[난이도] Gold5
[유형] DP

[풀이]
전형적인 배낭 문제입니다.
물건을 여러개를 선택할 수 있기 때문에
두번째 for문에서 for(int j=m;j>=0;j--) 이 아닌 for(int j=0;j<=m;j++) 를 사용하여
물건이 여러개 중복될 수 있도록 해야합니다.

또한 float을 100을 곱해 정수로 변환시 부동소수점 문제로 정확하지 않은 값으로 변환 될 수 있으므로
0.5를 더해주어야 합니다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,dp[10001],cal[5000],price[5000];
int main(){
    while(1){
        float f;
        scanf("%d%f",&n,&f);
        if(n==0) break;
        m=f*100+0.5;
        for(int i=0;i<n;i++) {
            scanf("%d%f",&cal[i],&f);
            price[i]=100*f;
        }
        memset(dp,0,sizeof(dp));
        int ans=0;

        for(int i=0;i<n;i++){
            for(int j=1;j<=m;j++){
                if(j-price[i]>=0) {
                    dp[j] = max(dp[j],dp[j-price[i]]+cal[i]);
                    ans=max(ans,dp[j]);
                }
            }
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/4781.cpp