Knapsack

��������� ZP 과�����게 ���������������.

���������, ��������� ������������ ��� ��������� ������ ������������. 그���고

"��� ������������ ������ ��� ������ ������ 과������ ������ ���������."

������게 ���������������. 그������ ������������ 공간��� ������������ ������������.

��������� ������ ����� ������ ���기 ������������ ������게 ������ ���까���?

������ ������ 과������ ���기��� ��격��� ������과 �����고 ���������.

과���	���기	��격
���과	3	800
���	4	1200
������	12	5000
������	1	300
���������	6	2000

���기��� ������������ ���기�� 50������고 ���������.

������게 ��������� ����� ������ ������ ��� ��� ������까?

그���고 그 ��� ������ ������ ������������ 구������ ������그������ ���������������.

(���, ������ ��������� ���계 ������������.)

������ ���

50

������ ���

��격 = 20600

������������ ��������� ��� ��������� ������ �������� ���금 ��� ������������고 ������ ������������ ������������고 ��������� ��������� ��������������� ��������� �������� ����� ������까���. HowToSolveIt������ ���개������ ������ ���결 ��������� ��� ���������기��� ������. ������ ��� ������ 교������ ���과��� 기������ ��� ������ ������까 ���������.

���������, ��������� �������� ��������겠���:

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

그���고 ���군���� ������ ������그������ ��������� ����� ������������기 ������������ ������ ��������������� ����� ������ �����고, �������� ������������ ������과 ������������ ��� ��������������� ����� ������ ������까 ���������. ICPC��� ������������ 구경��� ���������.

--JuNe

see also ���������������2002

������������