Knapsack - Revision history

Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:06Z

Repair batch-0002 pages from live compare

← Older revision		Revision as of 00:16, 27 March 2026
Line 40:		Line 40:
	<br />		<br />
	=== specfication ===		=== specfication ===
	[[입력 예]]<br />		입력 예<br />
	50<br />		50<br />
	사과 3 800<br />		사과 3 800<br />
Line 48:		Line 48:
	바나나 6 2000<br />		바나나 6 2000<br />

	[[출력 예]]<br />		출력 예<br />
	수박 (12)을(를) 담았습니다. 이제 남은 공간은 38입니다.<br />		수박 (12)을(를) 담았습니다. 이제 남은 공간은 38입니다.<br />
	수박 (12)을(를) 담았습니다. 이제 남은 공간은 26입니다. <br />		수박 (12)을(를) 담았습니다. 이제 남은 공간은 26입니다. <br />

Maintenance script: Repair MoniWiki formatting after migration

2026-03-26T14:01:39Z

Repair MoniWiki formatting after migration

← Older revision		Revision as of 14:01, 26 March 2026
Line 1:		Line 1:
	=== about ===		=== about ===
	당신은 ZP 과일가게 주인입니다.		당신은 ZP 과일가게 주인입니다.<br />
	어느날, 커다란 주머니를 든 손님이 찾아 왔습니다. 그리고		어느날, 커다란 주머니를 든 손님이 찾아 왔습니다. 그리고<br />
	"이 주머니에 넣을 수 있을 만큼 과일을 담아 주세요."		"이 주머니에 넣을 수 있을 만큼 과일을 담아 주세요."<br />
	이렇게 말했습니다. 그러나 주머니의 공간이 무제한은 아닙니다.		이렇게 말했습니다. 그러나 주머니의 공간이 무제한은 아닙니다. <br />
	당신이 돈을 가장 많이 받기 위해서는 어떻게 해야 할까요?		당신이 돈을 가장 많이 받기 위해서는 어떻게 해야 할까요? <br />
	예를 들어 과일의 크기와 가격이 다음과 같다고 합시다.		예를 들어 과일의 크기와 가격이 다음과 같다고 합시다.<br />
			<br />
	{\| class="wikitable"		{\| class="wikitable"
	\|-		\|-
Line 34:		Line 34:
	\|}		\|}

	여기서 주머니의 크기가 50이라고 합시다.		여기서 주머니의 크기가 50이라고 합시다. <br />
	어떻게 팔아야 가장 많은 돈을 벌 수 있을까?		어떻게 팔아야 가장 많은 돈을 벌 수 있을까? <br />
	그리고 그 때 버는 돈은 얼마인지 구하는 프로그램을 작성하세요.		그리고 그 때 버는 돈은 얼마인지 구하는 프로그램을 작성하세요. <br />
	(단, 담는 순서는 관계 없습니다.)		(단, 담는 순서는 관계 없습니다.)<br />
			<br />
	=== specfication ===		=== specfication ===
	[[입력 예]]		[[입력 예]]<br />
	50		50<br />
	사과 3 800		사과 3 800<br />
	배 4 1200		배 4 1200<br />
	수박 12 5000		수박 12 5000<br />
	자두 1 300		자두 1 300<br />
	바나나 6 2000		바나나 6 2000<br />

	[[출력 예]]		[[출력 예]]<br />
	수박 (12)을(를) 담았습니다. 이제 남은 공간은 38입니다.		수박 (12)을(를) 담았습니다. 이제 남은 공간은 38입니다.<br />
	수박 (12)을(를) 담았습니다. 이제 남은 공간은 26입니다.		수박 (12)을(를) 담았습니다. 이제 남은 공간은 26입니다. <br />
	수박 (12)을(를) 담았습니다. 이제 남은 공간은 14입니다.		수박 (12)을(를) 담았습니다. 이제 남은 공간은 14입니다.<br />
	수박 (12)을(를) 담았습니다. 이제 남은 공간은 2입니다.		수박 (12)을(를) 담았습니다. 이제 남은 공간은 2입니다.<br />
	자두 (1)을(를) 담았습니다. 이제 남은 공간은 1입니다.		자두 (1)을(를) 담았습니다. 이제 남은 공간은 1입니다.<br />
	자두 (1)을(를) 담았습니다. 이제 남은 공간은 0입니다.		자두 (1)을(를) 담았습니다. 이제 남은 공간은 0입니다.<br />
	가격 = 20600		가격 = 20600<br />
	----		----
	처음부터 단박에 이 문제를 푸는 것보다 조금 더 제한적이고 쉬운 문제에서 일반적이고 어려운 문제로 점진적으로 진행해 나가는 것은 어떨까요. NoSmok:HowToSolveIt 에서 소개하는 문제 해결 테크닉 중 하나이기도 하죠. 훨씬 더 높은 교육적 효과를 기대할 수 있지 않을까 합니다.		처음부터 단박에 이 문제를 푸는 것보다 조금 더 제한적이고 쉬운 문제에서 일반적이고 어려운 문제로 점진적으로 진행해 나가는 것은 어떨까요. NoSmok:HowToSolveIt 에서 소개하는 문제 해결 테크닉 중 하나이기도 하죠. 훨씬 더 높은 교육적 효과를 기대할 수 있지 않을까 합니다.
Line 71:		Line 71:
	----		----
	[[문제분류]]		[[문제분류]]

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:36Z

New page

=== about ===
당신은 ZP 과일가게 주인입니다.
어느날, 커다란 주머니를 든 손님이 찾아 왔습니다. 그리고
"이 주머니에 넣을 수 있을 만큼 과일을 담아 주세요."
이렇게 말했습니다. 그러나 주머니의 공간이 무제한은 아닙니다.
당신이 돈을 가장 많이 받기 위해서는 어떻게 해야 할까요?
예를 들어 과일의 크기와 가격이 다음과 같다고 합시다.

{| class="wikitable"
|-
| 과일
| 크기
| 가격
|-
| 사과
| 3
| 800
|-
| 배
| 4
| 1200
|-
| 수박
| 12
| 5000
|-
| 자두
| 1
| 300
|-
| 바나나
| 6
| 2000
|}

여기서 주머니의 크기가 50이라고 합시다.
어떻게 팔아야 가장 많은 돈을 벌 수 있을까?
그리고 그 때 버는 돈은 얼마인지 구하는 프로그램을 작성하세요.
(단, 담는 순서는 관계 없습니다.)

=== 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
----
처음부터 단박에 이 문제를 푸는 것보다 조금 더 제한적이고 쉬운 문제에서 일반적이고 어려운 문제로 점진적으로 진행해 나가는 것은 어떨까요. NoSmok: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
----
see also [[데블스캠프2002]]
----
[[문제분류]]