무게와 가격이 주어진 n개의 물건이 있다. 이 물건을 어떤 가방에 들어 있는 물건의 가격의 합을 최대화 하려고 한다.

허나 이 가방은 집어넣을 수 있는 물건의 합이 제한이 있기 때문에 전부 넣지 못하는 경우도 발생하므로 넣을 물건을 잘 선택해야 한다.

일반적인 경우엔 이 문제는 NP-complete문제로 알려져 있기에 효율적으로 풀기는 어렵다고 알려져 있다.

Dynamic Programming solution이 있다고 하여도 이 문제는 NP-complete가 확실하다.)

허나 어떤 특별한 제약 조건이 있을 경우에는 효율적인 해법이 있을 경우도 생긴다.

이번 문제에서는, 모든 물건의 무게가 피보나치수열의 숫자인 경우의 문제를 풀어보려 한다.

첫 번째와 두 번째의 피보나치수열의 숫자는 1과 2이며,

1, 2, 3, 5, 8, 13과 같이 각 각의 수열에 위치한 숫자들은 앞의 두 개의 숫자의 합으로 만들어진다.

가방에 담을 수 있는 물건의 최대 무게와 각 물건의 무게와 가격이 주어졌을 때

가방에 넣을 수 있는 물건들의 가격의 합이 최대가 얼마인지 알아보는 프로그램을 작성하라.

Fibonacci Knapsack timer 1s memory 128MB

Fibonacci Knapsack 1s 128MB