배낭 문제와?

Question

좋아 빠른 개요

나는 배낭 문제

http://en.wikipedia.org/wiki/Knapsack_problem

으로 보았다 그리고 난 그것이 내가 내 프로젝트를 위해 필요하지만, 내 프로젝트의 복잡한 부분은 내가 여러 필요가 어떻게 될지 알고 메인 자루 안의 자루.

모든 "가방"을 들고있는 대형 배낭에는 "가방"이 x 개 밖에 없습니다 (예를 들어 9 개라고 말하면됩니다). 각 가방은 다른 값을가집니다.

• 무게
• 비용
• 크기
• 용량

등, 그 모든 값이 정수 숫자이다. 0-100을 가정합니다.

내부 가방에도 유형이 지정되며 프로그램 입력에 동일한 유형의 여러 항목이 주어 지지만 외부 가방에는 해당 유형 중 하나만있을 수 있습니다.

주머니에 넣을 수있는 최대 무게를 지정해야하며 작은 가방의 다른 모든 속성은 가중치별로 그룹화해야합니다.

---

예

외부 가방 :

• 보유 수 (9 개) 작은 가방
• 무게 이하 98 [부여 또는 5를 양쪽 걸릴]
• 각 중 하나를 보유해야합니다 유형은 한 번에 각 유형 중 하나만 보유 할 수 있습니다.

내부 가방 :

• 비용, 100 %
• 크기에 가중, 67 %
• 용량에 가중, 44 %

---

프로그램에 가중 여러 가방의 입력을 받게됩니다 다음 라에 들어가기 위해 작은 가방의 조합을 작동해야합니다 rger bag을 사용하면 입력에 따라 여러 가지 솔루션이 제공되며 프로그램에서 가장 적합한 솔루션을 출력합니다.

나는이 접근법에 대한 가장 좋은 방법이 무엇이라고 생각하는지 궁금합니다.

Java 또는 C#으로 프로그래밍합니다. PHP로 프로그래밍하고 싶지만 알고리즘이 웹 서버에서 매우 비효율적 일 것입니다.당신이

이

-Zack

Answer 1

좋아요,, 배낭은 NP-힘든 줄 수있는 모든 도움을

감사합니다 그래서 그것이 아니었다면이 (물론 NP-힘들 것입니다 꽤 확신 단 하나의 바깥 쪽 주머니만으로 배낭을 해결할 수 있습니다.) 따라서 최적의 솔루션을 얻으려면 모든 조합을 검색하는 것보다 더 나은 방법을 사용할 수 없을 것입니다. 따라서 원하는 프로그램의 개요는 다음과 같을 것입니다.

for each possible combination 
do 
    if current combination is better than best previous 
     save current combination as best so far 
    fi 
od 

실행 시간은 기하 급수적입니다. 그래도 dynamic programming으로 가까운 솔루션을 얻을 수있는 것처럼 들립니다.

Answer 2

논리 프로그래밍을 위해 Prolog을 사용해보십시오. 모노 (.NET)에 P#을 포함한 여러 구현이 있습니다. 약간의 학습 곡선이 있지만 일단 익숙해지면 이런 종류의 문제 해결을 위해 자체 리그에서 진행됩니다.

희망이 도움이됩니다. 건배!

링크