알고리즘을 모르겠다는 건지 구현이 잘 안 된다는 건지를 모르겠습니다만,
말씀하신 대로 무게 총합의 절반을 구한 다음에(본문의 경우 14), 14kg 가방에 최대한 많이 채우는 문제를 풀면 될 것 같은데요. 문제의 입력이 항상 동일한 무게 두 묶음으로 나눌 수 있게 주어진다면 딱 14kg를 채우는 답이 나오겠죠.
http://hochulshin.com/01knapsack/
구글링해서 나온 위 링크에 있는 방법을 그대로 쓰니 제가 테스트한 케이스에서는 전부 제대로 나왔습니다.
그 14kg 을 구성하는 아이템 목록까지 나열하려고 하면 좀 귀찮아지긴 합니다만... 리스트를 자유롭게 다룰 수 있는 스크립트 언어를 쓰면 좀 더 편하게 나올 거고 C로 한다면 오히려 이 부분이 까다로울 수는 있겠네요.
알고리즘을 모르겠다는 건지 구현이 잘 안 된다는
알고리즘을 모르겠다는 건지 구현이 잘 안 된다는 건지를 모르겠습니다만,
말씀하신 대로 무게 총합의 절반을 구한 다음에(본문의 경우 14), 14kg 가방에 최대한 많이 채우는 문제를 풀면 될 것 같은데요. 문제의 입력이 항상 동일한 무게 두 묶음으로 나눌 수 있게 주어진다면 딱 14kg를 채우는 답이 나오겠죠.
http://hochulshin.com/01knapsack/
구글링해서 나온 위 링크에 있는 방법을 그대로 쓰니 제가 테스트한 케이스에서는 전부 제대로 나왔습니다.
그 14kg 을 구성하는 아이템 목록까지 나열하려고 하면 좀 귀찮아지긴 합니다만... 리스트를 자유롭게 다룰 수 있는 스크립트 언어를 쓰면 좀 더 편하게 나올 거고 C로 한다면 오히려 이 부분이 까다로울 수는 있겠네요.
좋은 하루 되세요!
댓글 달기