Knapsack

about ¶

당신은 ZP 과일가게 주인입니다.

어느날, 커다란 주머니를 든 손님이 찾아 왔습니다. 그리고

"이 주머니에 넣을 수 있을 만큼 과일을 담아 주세요."

이렇게 말했습니다. 그러나 주머니의 공간이 무제한은 아닙니다.

당신이 돈을 가장 많이 받기 위해서는 어떻게 해야 할까요?

예를 들어 과일의 크기와 가격이 다음과 같다고 합시다.

과일	크기	가격
사과	3	800
배	4	1200
수박	12	5000
자두	1	300
바나나	6	2000

여기서 주머니의 크기가 50이라고 합시다.

어떻게 팔아야 가장 많은 돈을 벌 수 있을까?

그리고 그 때 버는 돈은 얼마인지 구하는 프로그램을 작성하세요.

(단, 담는 순서는 관계 없습니다.)

[edit]

specfication ¶

입력 예

50

사과 3 800

배 4 1200

수박 12 5000

자두 1 300

바나나 6 2000

출력 예

수박 (12)을(를) 담았습니다. 이제 남은 공간은 38입니다.

수박 (12)을(를) 담았습니다. 이제 남은 공간은 26입니다.

수박 (12)을(를) 담았습니다. 이제 남은 공간은 14입니다.

수박 (12)을(를) 담았습니다. 이제 남은 공간은 2입니다.

자두 (1)을(를) 담았습니다. 이제 남은 공간은 1입니다.

자두 (1)을(를) 담았습니다. 이제 남은 공간은 0입니다.

가격 = 20600

처음부터 단박에 이 문제를 푸는 것보다 조금 더 제한적이고 쉬운 문제에서 일반적이고 어려운 문제로 점진적으로 진행해 나가는 것은 어떨까요.

HowToSolveIt에서 소개하는 문제 해결 테크닉 중 하나이기도 하죠. 훨씬 더 높은 교육적 효과를 기대할 수 있지 않을까 합니다.

예컨대, 다음의 순서가 가능하겠죠:

weighted, 0-1 knapsack problem -> find the exact match
weighted, unbounded knapsack problem -> find the exact match
weighted/valued, unbounded knapsack problem -> maximize the value not exceeding the weight limit

그리고 누군가가 만든 프로그램이 옳다는 것을 테스트하기 위해서는 이를 자동화하는 것이 편할 것이고, 이것을 위해서는 인풋과 아웃풋을 좀 단순화하는 것이 좋지 않을까 합니다. ICPC의 문제들을 구경해 보세요.

--JuNe