역 배낭 문제

다음 작업을 해결하려고합니다 : 각 가중치와 값이있는 항목 세트가 주어지면 주어진 총 값의 최소 배낭 용량을 결정합니다. 예 입력을위한역 배낭 문제

item1: w = 3.4, v = 3 
item2: w = 0.4, v = 1 
total value = 7

출력 :

이

우리는해야는 :

item1 x0, item2 x7

그리고

minimal capacity = 0 * 3.4 + 0.4 * 7 = 2.8 
total value = 7

재귀 어떤 수식을 내가해야 동적 프로그래밍을 사용하는 일반 알고리즘에 사용 하시겠습니까? 누구든지 작은 입력 데이터로이를 해결하는 예를 보여줄 수 있습니까?

P. 내 영어로 미안해.

출처

2011-10-29 yuyoyuppe

이것은 숙제 문제처럼 보입니다. 그렇다면 태그를 붙여야합니다. 또한이 문제를 해결하기위한 노력을 보여줄 필요가 있습니다. 시도한 접근 방식과 문제에 대해 알려주십시오. –

@VaughnCato, 웹에서 수식이나 예제를 검색했지만 "클래식"배낭 문제 만 발견했습니다. 나는 F = Sum (Weighti * Counti) [i = 0..n] (n - ItemCount)과 F2 = Sum (Valuei * Counti) [i = 0..n]과 같은 함수를 최소화해야 함을 알고 있습니다. total_value보다 낫지 만 수식이나 알고리즘을 만들 수는 없습니다. – yuyoyuppe

"최소 운반 능력"이란 무엇입니까? 왜 그냥 물건을 가져가는 것이 아닙니다. – hugomg

전통적인 (최대화) 배낭 알고리즘은 잘 작동합니다. max의 모든 발생을 min으로 바꾸면 거의 다 왔을 것입니다. 이것을 보는 또 다른 방법은 부정적인 비용을 사용하므로 최소화하는 것이 극대화됩니다 (빈 케이스에 특별한주의를 기울여야합니다).

출처

2011-10-29 15:56:10 hugomg

역 배낭 문제

답변

관련 문제