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