이 문제가 NP 인지 질문드립니다. Signin 문제 링크 각 사탕의 종류마다 가격과 칼로리가 주어집니다. 일정량의 돈이 주어지고, 이 돈으로 만들 수 있는 최대 칼로리를 구하는 것이 목적입니다. 돈은 실수로 주어지지만, 소수점 아래 두 자리까지로 주어져서 100을 곱해서 정수로 만들 수 있습니다. 이렇게 하면 이 문제가 knapsack problem같은 형태로 보여서 NP문제라고 생각하게 되었습니다. 한 번 살펴봐 주시면 감사하겠습니다. 10년 전
2개의 댓글이 있습니다. wookayin 'NP-Hard 인가요'가 더 올바른 질문입니다 :) 말씀하신대로 Knapsack 문제입니다. 위키피디아에 보시면 NP-Hard 라고 나와있지요. 하지만 동적계획법으로 O(nW) time에 풀리는데, W의 (정수)범위가 작기 때문에 제한 시간내에 답을 낼 수 있는겁니다. 실제로 W에 제한이 없으면... n의 polynomial이 아니게 되죠. 10년 전 link Signin NP-Hard 였군요 :) 상세하게 설명해주신 덕분에 이 문제를 풀 수 있을 것 같습니다. 감사합니다^_^! 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Signin
문제 링크
각 사탕의 종류마다 가격과 칼로리가 주어집니다.
일정량의 돈이 주어지고, 이 돈으로 만들 수 있는
최대 칼로리를 구하는 것이 목적입니다.
돈은 실수로 주어지지만, 소수점 아래 두 자리까지로 주어져서
100을 곱해서 정수로 만들 수 있습니다.
이렇게 하면 이 문제가 knapsack problem같은 형태로 보여서
NP문제라고 생각하게 되었습니다.
한 번 살펴봐 주시면 감사하겠습니다.
10년 전