about ¶
당신은 ZP 과일가게 주인입니다.
어느날, 커다란 주머니를 든 손님이 찾아 왔습니다. 그리고
"이 주머니에 넣을 수 있을 만큼 과일을 담아 주세요."
이렇게 말했습니다. 그러나 주머니의 공간이 무제한은 아닙니다.
당신이 돈을 가장 많이 받기 위해서는 어떻게 해야 할까요?
예를 들어 과일의 크기와 가격이 다음과 같다고 합시다.
여기서 주머니의 크기가 50이라고 합시다.
어떻게 팔아야 가장 많은 돈을 벌 수 있을까?
그리고 그 때 버는 돈은 얼마인지 구하는 프로그램을 작성하세요.
(단, 담는 순서는 관계 없습니다.)
어느날, 커다란 주머니를 든 손님이 찾아 왔습니다. 그리고
"이 주머니에 넣을 수 있을 만큼 과일을 담아 주세요."
이렇게 말했습니다. 그러나 주머니의 공간이 무제한은 아닙니다.
당신이 돈을 가장 많이 받기 위해서는 어떻게 해야 할까요?
예를 들어 과일의 크기와 가격이 다음과 같다고 합시다.
| 과일 | 크기 | 가격 |
| 사과 | 3 | 800 |
| 배 | 4 | 1200 |
| 수박 | 12 | 5000 |
| 자두 | 1 | 300 |
| 바나나 | 6 | 2000 |
여기서 주머니의 크기가 50이라고 합시다.
어떻게 팔아야 가장 많은 돈을 벌 수 있을까?
그리고 그 때 버는 돈은 얼마인지 구하는 프로그램을 작성하세요.
(단, 담는 순서는 관계 없습니다.)
specfication ¶
입력 예
50
50
사과 3 800
배 4 1200
수박 12 5000
자두 1 300
바나나 6 2000
출력 예배 4 1200
수박 12 5000
자두 1 300
바나나 6 2000
수박 (12)을(를) 담았습니다. 이제 남은 공간은 38입니다.
수박 (12)을(를) 담았습니다. 이제 남은 공간은 26입니다.
수박 (12)을(를) 담았습니다. 이제 남은 공간은 14입니다.
수박 (12)을(를) 담았습니다. 이제 남은 공간은 2입니다.
자두 (1)을(를) 담았습니다. 이제 남은 공간은 1입니다.
자두 (1)을(를) 담았습니다. 이제 남은 공간은 0입니다.
가격 = 20600수박 (12)을(를) 담았습니다. 이제 남은 공간은 26입니다.
수박 (12)을(를) 담았습니다. 이제 남은 공간은 14입니다.
수박 (12)을(를) 담았습니다. 이제 남은 공간은 2입니다.
자두 (1)을(를) 담았습니다. 이제 남은 공간은 1입니다.
자두 (1)을(를) 담았습니다. 이제 남은 공간은 0입니다.
처음부터 단박에 이 문제를 푸는 것보다 조금 더 제한적이고 쉬운 문제에서 일반적이고 어려운 문제로 점진적으로 진행해 나가는 것은 어떨까요. 
HowToSolveIt에서 소개하는 문제 해결 테크닉 중 하나이기도 하죠. 훨씬 더 높은 교육적 효과를 기대할 수 있지 않을까 합니다.
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
--JuNe
see also 데블스캠프2002