나는 알고리즘 의이 유형을 검색하고 많은 것들을 빨간색지만 내가 뭘 찾고 정확하게 찾을 수 없습니다.배낭 변종?
그래서 저는 쇼핑하러 가고 x 돈이 있고, 트럭은 y 무게까지 올라갈 수 있으며, 각 상품에는 무게와 가격이 보너스 크레딧이 있습니다. 출력은 선택한 항목의 총 중량이 트럭의 용량과 지출해야 할 금액을 초과하지 않도록 얻을 수있는 최대 보너스 크레딧을 제공해야합니다!
나는 여기에 도움을 줄 수 있는데, 알고리즘 이름을 알고 있니? 어떻게해야합니까? 나는 C 언어로해야만한다.
감사합니다.
당신은 무엇을 시도 했습니까?
이러한 유형의 문제는 일반적으로 최적화 또는 제약 조건 만족의 범주에 속합니다.
문제에 대한 함수 식을 작성하고 간단한 미적분 또는 단방향 방법으로 해결할 수 있는지 확인하십시오.
나는 시작도하지 않았고, 나는 최선의 방법을 이해하려고 노력했습니다. 동적 프로그래밍, memoization 등. 나는 지난 6 주 동안 NP 문제를 해결해 왔지만 어떻게 시작 해야할지 모르겠다. –
두 가지 변형 된 배낭 문제를 알고 있습니다. 0-1 버전은 분수 가중치를 포함 할 수 없습니다 (예를 들어 가져 가거나 두십시오). 예를 들어 두 번째로 좋은 선택의 절반을 차지할 수 없습니다. 다른 버전은 반대이며, 분수 항목이 허용됩니다. 이 작은 차이는 매우 중요하며 분수 버전에 유리하게 작용합니다.
분수 버전은 그리 디 알고리즘을 통해 해결할 수 있습니다. 가장 가치있는 "단가"를 사용하여 가능한 한 많은 항목을 가져올 수 있습니다. 트럭이 가득 찰 때까지 반복하십시오.
0-1 버전은 직접적인 욕심 많은 알고리즘으로 해결할 수 없기 때문에 조금 더 어렵습니다. 예를 들어, 트럭이 800 파운드를 운반 할 수 있다고 가정 해보십시오. 701lb - 무게 : 값 - $ 1577.25 : 단위 $ 2.25/파운드
탐욕스러운 알고리즘은 합계 $ 1577.25에 벤치를 잡을 것입니다.
최적 값은 3 개의 책장이고 테이블은 $ 1600입니다.
위의 경우 부분 배낭 버전은 총 $ 1775.25에 테이블/책장의 벤치와 99 파운드를 가져가는 것입니다.
0-1의 경우 모든 솔루션을 검사하기 위해 동적 프로그래밍과 같은 것을 사용해야합니다.
항목 가중치 및 항목 가격은 제약 조건입니다. 보너스 크레딧이 목표입니다. 따라서 다차원 배낭 문제 (한 가지 목표, 두 가지 제약 조건)가 있습니다. 잘 알려진 동적 프로그래밍 솔루션 배낭은 일반화 될 것이지만 복잡성은 제약 조건의 수에 따라 기하 급수적으로 증가합니다.
http://stackoverflow.com/questions/1827600/multiple-constraint-knapsack-problem –