설명

배낭 문제의 기본 형태: 일련의 잠재적인 항목이 주어지면 i
무게가 나가는 배낭에 넣다 c. 각 품목에는 이익 p가 있습니다.
그리고 가중치 w. 작업은 항목의 하위 집합을 선택하는 것입니다.
초과하지 않으면서 선택의 전체 유용성을 최대화합니다.
배낭의 무게 제한 c.

한스 켈러러, 울리히 퍼쉬, 데이비드 피싱어. 배낭 문제.
Springer-Verlag Berlin Heidelberg 2004. 페이지 3.

키워드: 혼합 정수 선형 계획법, 조합 최적화

소형 모델 유형 :MIP

카테고리 : 슬롯 게임 모델 라이브러리

메인 파일 : knapsack.gms

$title 바이너리 배낭 문제 (KNAPSACK,SEQ=436)

$onText
배낭 문제의 기본 형태: 잠재적인 항목 세트가 주어지면 i
무게가 나가는 배낭에 넣다 c. 각 품목에는 이익 p가 있습니다.
그리고 가중치 w. 작업은 항목의 하위 집합을 선택하는 것입니다.
초과하지 않으면서 선택의 전체 유용성을 최대화합니다.
배낭의 무게 제한 c.

한스 켈러러, 울리히 퍼쉬, 데이비드 피싱어. 배낭 문제.
Springer-Verlag Berlin Heidelberg 2004. 페이지 3.

키워드: 혼합 정수 선형 계획법, 조합 최적화
$offText

내가 '항목'을 설정;
매개변수
    p(i) '이익'
    w(i) '가중치'
    c '용량';

자유 변수 z '목적';
이진변수 x '선택';

방정식 cap_restr, 유틸리티;
cap_restr .. sum(i, w(i)*x(i)) =l= c;
유틸리티 .. z =e= sum(i, p(i)*x(i));

z.lo = 0;

모델 배낭 /all/;

* 예시 사례
내가 /i1*i10/으로 설정;
c = 269;

테이블 데이터
    피 승
나는1 55 95
i2 10 4
i3 47 60
i4 5 32
i5 4 23
i6 50 72
i7 8 80
i8 61 62
i9 85 65
i10 87 46;

p(i) = 데이터(i,'p');
w(i) = 데이터(i,'w');

mip max z를 사용하여 배낭을 해결합니다.