욕심 많은 알고리즘을 최적화하는 방법이 있습니까?

Question

저는 최근에 파이썬을 사용하여 배낭 문제를 해결하는 프로그램을 작성했습니다. 그것은 위대한 작품을 일반적으로 욕심 알고리즘을 다음과

(그것이 끝이 될 때까지, 즉 모든 단계에 대한 최선의 해결책을 찾기)하지만 최적화 필요 그것은 욕심 알고리즘 (그건 내 숙제의 일부)를 기반으로

그럼 개선 할 수있는 기본적인 아이디어를 제공해 주시겠습니까?

Item Name    Weight   Profit 
    Ammunition    3.00   95.00 
    Bread     3.60   90.00 
    Firewood    2.50   56.00 
    Olive Oil    2.40   45.00 
    Water     3.70   67.00 
    Weapon     4.80   79.73 

이것은 현재 프로젝트의 출력물입니다. 가방 용량은 20kg로 제한되어 있지만 데이터를 변경할 수는 없지만 개선하기 위해 더 나은 아이디어가 필요합니다. 고맙습니다!

나는 코드 또는 솔루션에 대해 잘 모르겠지만, 나는 그것이 모든 "효율성"여기

Answer 1

내가 조건 "공간"과 동의어로 "무게를"사용에 관한 생각합니다.

일단 수행 할 수있는 작업은 각 항목에 대해 profit/weight 비율을 계산하는 것입니다. 비율의 차이와 공간의 차이는 해당 공간에 대해 가능한 최상의 개선입니다. 예를 들어 빈 공간이 있고 재 배열 한 경우 다른 항목 Z를 쥐어 짜낼 수있는 경우 해당 공간에서 얻을 수있는 최대 이익은 (Zratio-0ratio) * 가중치가됩니다. 따라서 욕심 많은 알고리즘을 기반으로 후보 솔루션을 생성 한 다음이를 사용하여 가능한 개선 사항을 제한 할 수 있습니다. 일반적으로 동적 프로그래밍 관점에서이 접근 방법을 원할 것입니다.