배낭 문제

1차원(제한) 배낭 문제의 예: 전체 무게를 15kg 이하로 유지하면서 돈의 양을 최대화하기 위해 어떤 상자를 선택해야 합니까?여러 가지 제약이 있는 문제는 상자의 무게와 부피를 모두 고려할 수 있습니다.
(솔루션: 각 박스가 몇 개라도 있으면 노란색 박스와 회색 박스가 각각 3개씩 표시됩니다.표시된 박스만 있으면 녹색 박스를 제외한 모든 박스가 표시됩니다.

배낭 문제는 조합 최적화의 문제입니다.각 항목에 가중치와 값을 지정하면 총 가중치가 지정된 제한 이하이고 총 값이 가능한 한 커지도록 컬렉션에 포함할 각 항목의 수를 결정합니다.그것은 고정 크기의 배낭에 묶여 가장 가치 있는 물건으로 채워야 하는 사람이 직면한 문제에서 그 이름을 따왔다.이 문제는 종종 자원 할당에서 발생하는데, 의사결정자는 각각 고정된 예산 또는 시간 제약 하에 분할할 수 없는 프로젝트 또는 태스크 중 하나를 선택해야 합니다.

배낭 문제는 한 세기 이상 연구되어 왔으며,^[1] 초기 작품들은 1897년까지 거슬러 올라간다."납스팩 문제"라는 이름은 수학자 토바이어스 단치히 (1884–1956)^[2]의 초기 저작으로 거슬러 올라가며, 짐을 너무 많이 싣지 않고 가장 가치 있고 유용한 물건들을 포장하는 흔한 문제를 가리킨다.

적용들

배낭 문제는 원재료 ^[3]절감을 위한 가장 낭비가 적은 방법 찾기, 투자와 ^[4]포트폴리오 선택, 자산유동화 증권화를 ^[5]위한 자산 선택, Merkle의 키 생성 등 다양한 분야의 실제 의사결정 프로세스에서 나타납니다.Hellman과^[6] 다른 배낭 암호 시스템들.

배낭 알고리즘의 초기 적용 사례 중 하나는 시험 응시자들이 어떤 문제에 대답할지에 대한 선택권을 갖는 시험 구성 및 채점이었다.작은 예를 들면, 수험생들에게 그러한 선택권을 주는 것은 꽤 간단한 과정이다.예를 들어, 시험에 각각 10점씩 12개의 문제가 포함되어 있는 경우, 응시자는 10개의 문제만 답하면 최대 100점을 얻을 수 있습니다.그러나 점 값의 이질적인 분포를 사용하는 검정에서는 선택 사항을 제공하기가 더 어렵습니다.Feuerman과 Weiss는 학생들에게 총 125점의 이질적인 시험을 치르는 시스템을 제안했다.학생들은 모든 질문에 최선을 다해 대답하도록 요구받는다.총점 값이 100인 문제의 가능한 부분 집합 중에서 배낭 알고리즘은 각 학생에게 가장 ^[7]높은 점수를 주는 부분 집합을 결정합니다.

1999년 Stony Brook University Algorithm Repository의 연구에 따르면 75개의 알고리즘 문제 중 배낭 문제가 19번째로 인기 있고 접미사 트리와 쓰레기통 포장 ^[8]문제 다음으로 세 번째로 필요한 것으로 나타났습니다.

정의.

The most common problem being solved is the 0-1 knapsack problem, which restricts the number $x_{i}$ of copies of each kind of item to zero or one.1 ~ $n$ ({ $displaystyle$ w_ $n$ $i})$ 의 $n$ $w_{i}$ $n$ 가 매겨진n개의 $항목$ 세트가 있는 경우, 각 항목에는 최대 $w_{i}$ $용량$ W({ $displaystyle$ $w_$ ${i$ $W$ 와 $v_{i}$ w $({$ 가 있습니다.

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

i

{\displaystyle

\

sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}w_{i}x_{i}\leq W

\sum _{i=1}^{n}w_{i}x_{i}\leq W

\sum _{i=1}^{n}w_{i}x_{i}\leq W

\sum _{i=1}^{n}w_{i}x_{i}\leq W

x

\sum _{i=1}^{n}w_{i}x_{i}\leq W

\sum _{i=1}^{n}w_{i}x_{i}\leq W

{

displaystyle \sum

_ { i

= 1

}^{

n}w_{i}x_{i}\leq

W

}

x_{i}\in \{0,1\}

x_{i}\in \{0,1\}

i

x_{i}\in \{0,1\}

{

x_{i}\in \{0,1\}

,

}{

display x_{i}\in \ 0

,

1

}에 따릅니다.

$x_{i}$ 서 $($ \displaystyle $x_{i$ })는 $x_{i}$ 배낭에 포함할 $항목$ i(\ $displaystyle$ i $)$ 의 $i$ 인스턴스 수를 나타냅니다.비공식적으로 문제는 배낭에 있는 항목의 값의 합을 최대화하여 무게의 합이 배낭의 용량보다 작거나 같도록 하는 것이다.

BKP(Bounded Napsack Problem)는 각 항목이 1개뿐이라는 제한을 없앤다.단, 각 항목의 복사 $x_{i}$ $(\$ })는 $x_{i}$ 음이 아닌 최대 정수 값 $c$ (\ $displaystyle$ c $c$ 로 제한합니다.

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

i

{\displaystyle

\

sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}w_{i}x_{i}\leq W

\sum _{i=1}^{n}w_{i}x_{i}\leq W

w

\sum _{i=1}^{n}w_{i}x_{i}\leq W

\sum _{i=1}^{n}w_{i}x_{i}\leq W

W {

displaystyle \sum

_ { i

\sum _{i=1}^{n}w_{i}x_{i}\leq W

=

1

}^{

n}w_{i}x_{i}\leq

W

}

x_{i}\in \{0,1,2,\dots ,c\}.

x_{i}\in \{0,1,2,\dots ,c\}.

x_{i}\in \{0,1,2,\dots ,c\}.

{

x_{i}\in \{0,1,2,\dots ,c\}.

,

x_{i}\in \{0,1,2,\dots ,c\}.

,

x_{i}\in \{0,1,2,\dots ,c\}.

}.\

displaystyle x_{i}\in

\ {

0,

1,

2,\c}

에 따릅니다.

}

Unbounded Nacksack Problem(UKP;무제한 배낭 문제)는 각 항목의 복사 수에 상한을 두지 않으며 xi $(\$ })에 $x_{i}$ $x_{i}$ 유일한 제한은 음이 아닌 정수라는 점을 제외하고 위와 같이 공식화할 수 있습니다.

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}v_{i}x_{i}

i

{\displaystyle

\

sum _{i=1}^{n}v_{i}x_{i}

\sum _{i=1}^{n}w_{i}x_{i}\leq W

\sum _{i=1}^{n}w_{i}x_{i}\leq W

\sum _{i=1}^{n}w_{i}x_{i}\leq W

w

\sum _{i=1}^{n}w_{i}x_{i}\leq W

\sum _{i=1}^{n}w_{i}x_{i}\leq W

W {

displaystyle \sum

_ { i =

1

}^{

n}w_{i}x_{i

}\

x_{i}\in \mathbb {N} .

W

}

및

x_{i}\in \mathbb {N} .

N

.\

displaystyle x_{i}\in \mathbb {N}

에 따릅니다.

무한 배낭 문제의 예로는 이 문서의 첫머리에 표시된 그림과 해당 그림의 설명에 있는 "각 상자의 임의의 수가 사용 가능한 경우"라는 텍스트를 사용합니다.

계산의 복잡성

배낭 문제는 여러 가지 이유로 컴퓨터 과학의 관점에서 흥미롭다.

배낭 문제의 결정 문제 형식(무게 W를 초과하지 않고 최소 V의 값을 달성할 수 있는가?)은 NP-완전하므로 모든 경우에서 정확하고 빠른(다항 시간) 알고리즘은 알려져 있지 않다.
결정 문제는 NP-완전이지만 최적화 문제는 그렇지 않고, 그 해결은 적어도 결정 문제만큼 어렵고, 솔루션이 주어진 경우 최적인지 아닌지를 판단할 수 있는 알려진 다항식 알고리즘은 없습니다(즉, 더 큰 V를 가진 솔루션이 없으므로 NP-완전 결정 문제를 해결할 수 있습니다).
동적 프로그래밍을 사용하는 의사 다항 시간 알고리즘이 있습니다.
완전 다항식 시간 근사 스킴이 있는데, 이 스킴은 의사 다항식 시간 알고리즘을 서브루틴으로 사용합니다.
실제로 발생하는 많은 사례와 일부 분포의 "랜덤 인스턴스"는 그럼에도 불구하고 정확하게 해결할 수 있습니다.

"결정"과 "최적화" 문제 사이에는 "결정" 문제를 해결하는 다항식 알고리즘이 존재한다면 k의 값을 증가시키면서 이 알고리즘을 반복적으로 적용함으로써 다항식 시간에 최적화 문제의 최대값을 찾을 수 있다는 점에서 링크가 있다.한편, 알고리즘이 다항시간에 최적화 문제의 최적값을 구했을 경우, 이 알고리즘에 의해 출력되는 해답값과 k값을 비교함으로써 결정문제를 다항시간에 해결할 수 있다.따라서 문제의 두 버전은 모두 유사한 난이도를 가지고 있습니다.

연구 문헌의 한 가지 주제는 배낭 문제의 "하드" 인스턴스가 어떻게 ^[9]^[10]생겼는지, 또는 다른 방식으로 보는 것이며, 실제 인스턴스의 속성이 최악의 경우 NP-완전 ^[11]동작을 시사하는 것보다 더 다루기 쉽게 만드는지를 식별하는 것이다.이러한 "하드" 인스턴스를 찾는 목적은 Merkle-Hellman 배낭 암호 시스템과 같은 공개 키 암호 시스템에서 사용하는 것입니다.

또한 주목할 점은 배낭 문제의 경도가 입력의 형태에 따라 달라진다는 사실이다.가중치와 이익을 정수로 지정하면 약 NP-완전인 반면 가중치와 이익을 유리수로 ^[12]지정하면 강 NP-완전이다.그러나 합리적인 가중치와 이익의 경우, 여전히 완전한 다항식 시간 근사 체계를 인정한다.

해결하는

동적 프로그래밍 접근법,^[13] 분기 및 제한^[14] 접근법 또는 두 ^[11]^[15]^[16]^[17]접근법의 하이브리드화에 기초하여 배낭 문제를 해결하기 위해 여러 알고리즘을 사용할 수 있습니다.

동적 프로그래밍 사전 알고리즘

Unbounded Napsack Problem(UKP;무제한 배낭 문제)은 각 항목의 복사본 수에 제한을 두지 않습니다.게다가 여기서 $x_{i}>0$ i $>$ $x_{i}>0$ { $display$ style $x$ _ { $i$ } > $x_{i}>0$ 0 이라고 $x_{i}>0$ 합니다.

m[w']=\max \left(\sum _{i=1}^{n}v_{i}x_{i}\right)

x_{i}>0

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

w

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

{\ {

displaystyle \sum _

{ i

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

= 1 }^{

n} w_{i}

x_{i}>0

{i}\leq

w

'}

및

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

x i

x_{i}>0

> 0 {

displaystyle x_{i}

>

0}

에 따릅니다.

m $m[w]$ [ $]$ { $displaystyle$ m [ $w$ ]의 $m[w]$ 속성은 다음과 같습니다.

$m[0]=0\,\!$ . $m[0]=0\,\!$ m [ $m[0]=0\,\!$ ] $=$ { $display$ m [ 0 ]= 0 , \ ! $m[0]=0\,\!$ } (빈 세트의 합계)

$m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ . $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ m [ $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ ] $=$ ( $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ + $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ [ $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ - $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ , $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ 2 + $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ [ $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ - $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ , $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ . , $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ n + $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ [ $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ - $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ n $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ $){$ $display style$ m [ w ]= \ $max$ ( $v _$ ${$ 1} + $m$ [ w _ { $}$ , v $_$ { $w$ _ 2 } , { $n$ } , .아이템의 종류입니다.

두 번째 특성은 자세히 설명해야 합니다.이 메서드를 실행하는 동안 w $\$ $displaystyle$ w를 $i$ 사용하여 $w$ 를 얻는 방법은 $i$ 과 같습니다.앞의 무게는w $w-w_{1},w-w_{2},...,w-w_{i}$ - $w-w_{1},w-w_{2},...,w-w_{i}$ $w-w_{1},w-w_{2},...,w-w_{i}$ , $w-w_{1},w-w_{2},...,w-w_{i}$ w - $w-w_{1},w-w_{2},...,w-w_{i}$ - w 2, $w-w_{1},w-w_{2},...,w-w_{i}$ . $w-w_{1},w-w_{2},...,w-w_{i}$ - $w-w_{1},w-w_{2},...,w-w_{i}$ i $,$ w - $w-w_{1},w-w_{2},...,w-w_{i}$ - w i 입니다. $여기서 w-w_{1}, w-w_{2}, w-w_{i}$ 는 $w-w_{1},w-w_{2},...,w-w_{i}$ $i$ $디스플레이 i$ 의 $i$ 가 다릅니다.항목(중량과 값이 완전히 동일하지 않다는 의미) $이러한$ 의 $i$ 각각의 값과 관련된 최대값을 미리 알고 있다면, 우리는 단지 그것들을 서로 비교하고 궁극적으로 최대값을 얻으면 끝입니다.

여기서 빈 세트의 최대값은 0으로 간주됩니다.m $m[0]$ [ $]$ { $displaystyle$ m [ $0$ ] $m[0]$ $m[W]$ $m[W]$ [ W $]$ { $displaystyle$ m [ W $]$ 까지의 $m[W]$ 결과를 표로 작성하면 해결 방법이 나타납니다.Since the calculation of each $m[w]$ involves examining at most $n$ items, and there are at most $W$ values of $m[w]$ to calculate, the running time of the dynamic programming solution is $O(nW)$ . Dividing $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ w 1, $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ 2, $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ w $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ {\ $displaystyle w_{1}, w_{2},$ \ $ldots, w_{n}, W$ 는 $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ 최대 공통 제수로 실행 시간을 향상시키는 방법입니다.

PnpNP라고 해도 $O(nW)$ O $(n$ W $)$ 의 $O(nW)$ 는 $O(nW)$ 배낭 문제가 NP-complete라는 사실과 모순되지 않습니다. $(\displaystyle$ W $W$ 는n(\ $displaystyle$ n $n$ 과 $달리$ 문제에 대한 입력 길이에 있어서 다항식이 아니기 때문입니다.문제에 $대한$ W $입력$ 의 $W$ 길이는 W $\displaystyle$ W가 $W$ $아니라$ W $\$ $displaystyle$ W $W$ $log$ W $\log W$ displaystyle W $\$ displaystyle $\log W$ 의 비트 수에 비례합니다.단, 이 런타임은 의사다중공칭이기 때문에 (의 결정판) 배낭 문제가 약한 NP-완전 문제가 됩니다.

0-1 배낭 문제

다이내믹 프로그래밍 접근법 시연

0-1 배낭 문제에 대한 유사한 동적 프로그래밍 솔루션도 의사 다항 시간에 실행됩니다. $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ 1, $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ , $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ {\ $displaystyle w_{1}, w_{2},\ldots$ ,, $w_{$ n}, $W}$ 가 $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ 엄밀하게 양의 정수라고 $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ 합니다.m $m[i,w]$ [ $m[i,w]$ , $]{$ $display style$ m $[ i$ , $w$ ]{ $display style$ w} $w$ 의 $m[i,w]$ $w$ 중량으로 얻을 수 있는 최대값으로 $m[i,w]$ 합니다 $($ $최초$ i { $display style$ i}항목 $i$ ).

m $m[i,w]$ [ $m[i,w]$ , $]$ { $display style$ m [ $i$ , $w$ ] } 를 다음과 $m[i,w]$ 같이 재귀적으로 $m[i,w]$ 할 수 있습니다(정의 A).

$m[0,w]=0$
$m[i,\,w]=m[i-1,\,w]$ $w_{i}>w\,\!$ $m[i,\,w]=m[i-1,\,w]$ [ $m[i,\,w]=m[i-1,\,w]$ , w $m[i,\,w]=m[i-1,\,w]$ ] $=$ [ $m[i,\,w]=m[i-1,\,w]$ - $m[i,\,w]=m[i-1,\,w]$ , $]{$ $display style$ m [ $i$ , w ]= $m$ [ i - 1 , w $m[i,\,w]=m[i-1,\,w]$ ] > $w_{i}>w\,\!$ \ $display w$ _ { $i$ } （ w _ { i } > w , \ , \ $w_{i}>w\,\!$ } $w_{i}>w\,\!$ （ 새로운 아이템은 현재 무게 제한보다 커집니다 $m[i,\,w]=m[i-1,\,w]$ .
$m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ $m$ $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ [ $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ , w $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ ] $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ ( m $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ [ $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ - $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ , $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ , $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ [ $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ - $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ , $w$ - $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ i $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ ] + $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ i ) $=$ \ $max$ ( m [ i _ $1$ , w $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ ] , m [ i - 1 , w $]$ , m [ i - 1 , w $_ i$ $w_{i}\leqslant w$ ] + v _ { i $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ } } ( $w_{i}\leqslant w$ ( max [ i - 1 、 w _ i } ) w _ i ) w _ sl _ sl } $）$ ifstylestyle 。 w $w_{i}\leqslant w$

그런 다음 m $m[n,W]$ , W $]$ { $displaystyle m[n,$ W $m[n,W]$ 을(를) 계산하면 해결 방법을 찾을 수 있습니다. 이를 효율적으로 수행하려면 표를 사용하여 이전 계산을 저장할 수 있습니다.

다이내믹 프로그램의 의사 코드를 다음에 나타냅니다.

// 입력: // 값(어레이 v에 저장) // 중량(배열 w에 저장) // 구분 항목 수 (n) // 배낭 용량 (W) // 메모:배열 "v" 및 배열 "w"는 인덱스 1에서 시작하는 모든 관련 값을 저장하는 것으로 가정합니다.  배열 m[0..n, 0..W]; 위해서 j 부터 0 로. W 하다:     m[0, j] := 0 위해서 i 부터 1 로. n 하다:     m[i, 0] := 0  위해서 i 부터 1 로. n 하다:     위해서 j 부터 0 로. W 하다:         한다면 w[i] > j 그리고나서:             m[i, j] := m[i-1, j]         또 다른:             m[i, j] := 맥스.(m[i-1, j], m[i-1, j-w[i]] + v[i])

따라서 이 솔루션은 O $n$ W $)$ 시간 $O(nW)$ $O(nW)$ O $(n$ W $) 공간$ 내에서 $O(nW)$ 됩니다.(m[n,W] 값만 필요한 경우 필요한 메모리 양이 O(W)가 되도록 코드를 수정할 수 있습니다.이것에 의해, 어레이 「m」의 최근 2 행이 격납됩니다).

단, 한두 걸음 더 나아가면 O $($ $n W)$ 와 $O(nW)$ O $n$ $사이$ 의 시간 내에 메서드가 실행된다는 것을 알 수 있습니다.정의 A에서는 항목 수 및 항목 $선택$ 시 모든 가중치를 계산할 필요가 없습니다.즉, 위 프로그램은 무게가 0에서 W로 자주 변경되기 때문에 필요 이상으로 계산됩니다.이 관점에서 이 메서드가 재귀적으로 실행되도록 프로그래밍할 수 있습니다.

// 입력: // 값(어레이 v에 저장) // 중량(배열 w에 저장) // 구분 항목 수 (n) // 배낭 용량 (W) // 메모:배열 "v" 및 배열 "w"는 인덱스 1에서 시작하는 모든 관련 값을 저장하는 것으로 가정합니다.  정의 가치[n, W]  초기화 모든. 가치[i, j] = -1  정의 m:=(i,j)         // 조건 하에서 얻을 수 있는 최대값을 나타내도록 함수 m을 정의합니다.첫 번째 i 항목을 사용하세요.총 무게 제한은 j입니다. {     한다면 i == 0 또는 j <=> 0 그리고나서:         가치[i, j] = 0         돌아가다      한다면 (가치[i-1, j] == -1) 그리고나서:     // m[i-1, j]가 계산되지 않았습니다. 함수 m을 호출해야 합니다.         가치[i-1, j] = m(i-1, j)      한다면 w[i] > j 그리고나서:                      // 가방 안에 물건이 들어가지 않습니다.         가치[i, j] = 가치[i-1, j]     또 다른:          한다면 (가치[i-1, j-w[i]] == -1) 그리고나서:     // m[i-1,j-w[i]가 계산되지 않았습니다.함수 m을 호출해야 합니다.             가치[i-1, j-w[i]] = m(i-1, j-w[i])         가치[i, j] = 맥스.(가치[i-1,j], 가치[i-1, j-w[i]] + v[i]) }  달려. m(n, W)

예를 들어, 10개의 다른 품목이 있고 무게 제한은 67입니다.그렇게,

{\displaystyle {displaystyle}&w[1]=23,w[2]=26,w[3]=20,w[4]=18,w[5]=32,w[6]=27,w[7]=29,w[8]=26,w[9]=30,w[10]=27\&v]=505,35[2]

위의 방법을 사용하여 $m(10,67)$ m( $m(10,67)$ $)$ { $displaystyle$ m( $10,67$ 을 계산하면 m $m(i,j)=0$ , $=$ ({ $displaystyle$ m $(i,j$ )= $0$ 을 생성하는 콜을 제외하고 다음과 같이 됩니다.

{\displaystyle{\begin{정렬}&, m(10,67)=1270\\&, m(9,67)=1270,m(9,40)=678\\&, m(8,67)=1270,m(8,40)=678,m(8,37)=545\\&, m(7,67)=1183,m(7,41)=725,m(7,40)=678,m(7,37)=505\\&, m(6,67)=1183,m(6,41)=725,m(6,40)=678,m(6,38)=678,m(6,37)=505\\&, m(5,67)=1183,m(5,41)=725,m(5,40)=678,m(5,38)=678,m(5,37)=505\\&, m(4,67)=1183,m(4,41)=725,m(4,40)=678,m(4,38)=678,m(4,37)=505,m(4,35)=505\\&, m(3,67)=963,m(3,49)=963,m(3,41)=505,m(3,40)=505,m(3,38)=505,m(3,37)=505,m(3,35)=505,m(3,23)=505,m(3,22)=458,m(3,20)=458\\&, m(2,67)=857,m(2,49)=857,m(2,47)=505,m(2,41)=505,m(2,40)=505,m(2,38)=505,m(2,37)=505,m(2,35)=505,m(2,29)=505,m(2,23)=505\\&, m(1,67)=505,m(1,49)=505,m(1,47)=505,m(1,41)=505,m(1,40)=505,m(1,38)=505,m(1,37)=505,m(1,35)=505,m(1,29)=505,m(1,23)=505\\end{aligned}}

게다가, 재귀를 깨고 트리로 바꿀 수도 있어.그런 다음 이 방법을 신속하게 실행하기 위해 몇 가지 작업을 줄이고 병렬 컴퓨팅을 사용할 수 있습니다.

전체 값뿐만 아니라 항목의 실제 하위 집합을 찾으려면 위의 함수를 실행한 후 이 작업을 수행할 수 있습니다.

/** * 최적의 배낭 항목의 인덱스를 반환합니다. * i: 배낭에 아이템1 ~ i를 넣을 수 있습니다. * j: 배낭의 최대 무게 */ 기능. 배낭(i: 인트, j: 인트): 세트< >인트> {     한다면 i == 0 그리고나서:         돌아가다 {}     한다면 m[i, j] > m[i-1, j] 그리고나서:         돌아가다 {i} ∪ 배낭(i-1, j-w[i])     또 다른:         돌아가다 배낭(i-1, j) }  배낭(n, W)

미트 인 더 미들

0-1^[18] 배낭의 또 다른 알고리즘은 1974년에 발견되었으며 암호학에서 유사한 이름의 알고리즘과 유사하기 때문에 "중간자와의 만남"이라고 불리기도 합니다.다만, 다른 항목의 수는 기하급수적이지만, W $\displaystyle$ W가 $W$ n보다 클 $경우$ DP 알고리즘보다 유리할 수 있습니다.특히 $\$ 가 $w_{i}$ $w_{i}$ 가 아닌 정수인 경우에도 스케일링 및 반올림(고정점 산술 사용)을 통해 동적 프로그래밍 알고리즘을 사용할 수 있지만, 이 문제로 인해 정답에 도달하기 위해 d $\displaystyl$ d의 $d$ 정밀도가 $d$ 한 $경우$ W $\displaystyl$ $e$ W $}$ 는 $W$ $(\$ 10 $^{d$ 스케일링해야 합니다.DP 알고리즘에는 O $O(W10^{d})$ $)\displaystyle$ O $(W10^{d})$ $O(nW10^{d})$ 과 $O(W10^{d})$ O $O(nW10^{d})$ $O(nW10^{d})$ $)\displaystyle$ O $(nW10^{d})$ 시간이 $O(nW10^{d})$ $O(W10^{d})$ 합니다.

Meet-in-the-middle 알고리즘 입력: 가중치와 값을 가진 항목 집합.출력:서브셋의 최대 결합값입니다.집합 {1...n}을(를) 크기가 거의 동일한 두 집합 A와 B로 분할하여 A의 각 하위 집합에 대한 각 집합의 무게와 값을 계산하고, 결합된 무게가 W보다 작도록 가장 큰 값의 B의 하위 집합을 찾습니다.

이 알고리즘에는 $O(2^{n/2})$ O $/$ )의 $O(2^{n/2})$ 공간이 $O(2^{n/2})$ 합니다.{ $displaystyle$ O(2 $^{n/2}})$ 스텝3의 효율적인 실장(예를 들어 무게에 따라 B의 서브셋을 정렬하고, 값이 크거나 같은B의 다른 서브셋보다 무게가 큰B의 서브셋을 폐기하고, 바이너리 검색을 사용하여 최적의 일치를 찾아내는 등)은 $O(n2^{n/2})$ O( $O(n2^{n/2})$ )의 런타임으로 됩니다. $O(n2^{n/2})$ $O(n2^{n/2})$ ) $O(n2^{n/2})$ { $displaystyle$ $O(n2^{n/2})$ O ( $n2$ ^ { $O(n2^{n/2})$ $n$ / 2 $O(n2^{n/2})$ $}$ $O(n2^{n/2})$ } 。암호화에서의 중간 공격에서의 만남과 마찬가지로, 이것은 순진한 무차별 포스 접근 $\{1...n\}$ $\{1...n\}$ 의 모든 서브셋을 검사 $O(n2^{n})$ 의 $O(n2^{n})$ $O(n2^{n})$ ( $O(n2^{n})$ 2 $n$ ) runtime에서 개선됩니다. $n$ $n\}}),$ 일정한 공간이 아닌 지수적 공간을 사용하는 비용('베이비 스텝 자이언트 스텝' 참조).

근사 알고리즘

대부분의 NP-완전 문제의 경우, 최적이 아니더라도 실행 가능한 해결책을 찾는 것으로 충분할 수 있습니다.단, 바람직하게는 근사치는 발견된 솔루션의 값과 최적 솔루션의 값의 차이에 대한 보증을 수반한다.

유용하지만 계산적으로 복잡한 많은 알고리즘과 마찬가지로 솔루션에 가까운 알고리즘을 만들고 분석하는 데 상당한 연구가 진행되어 왔습니다.배낭 문제는 NP-Hard이지만 여전히 지정된 정도까지 근사할 수 있는 알고리즘 집합 중 하나입니다.이것은 문제가 다항식 시간 근사 체계를 가지고 있다는 것을 의미합니다.정확히 말하면, 배낭 문제는 완전 다항식 시간 근사 체계(FPTAS)^[19]를 가지고 있습니다.

탐욕 근사 알고리즘

George Dantzig는 무한 배낭 ^[20]문제를 해결하기 위해 탐욕스러운 근사 알고리즘을 제안했다.이 버전은 아이템을 무게 단위당 값 내림차순으로 정렬합니다. $v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}$ 1/ $v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}$ 1 $v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}$ v $v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}$ v $v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}$ / $v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}$ \ $displaystyle$ v _ { $1}$ / w _ {1} \ $geq \cdots \geq$ v _ ${n}$ / $w$ _ {n} $v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}$ } .q until until until in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in in inm{\ $displaystyle$ m $}$ 이 $m$ 가방에 들어가는 아이템의 최대값인 $경우$ gready 알고리즘은 m $m/2$ / $(\displaystyle$ m/2 $m/2$ $이상$ 의 값을 $m/2$ 수 있습니다.

각 종류의 품목의 공급이 제한되는 제한적인 문제의 경우, 위의 알고리즘은 최적과는 거리가 멀 수 있습니다.단, 간단한 수정만으로 이 문제를 해결할 수 있습니다.간단하게 하기 위해 모든 아이템이 봉투에 개별적으로 들어가 있다고 가정합니다( $모든$ i $\$ i의 경우 w $\displaystyle w_{i}\leq$ W $).$ 아이템을 가능한 한 오랫동안 탐욕스럽게 포장하여 $S_{1}$ $({$ 을 $S_{1}$ $S_{1}=\left\{1,\ldots ,k\right\}$ 구축합니다( $S_{1}=\left\{1,\ldots ,k\right\}$ : $S_{1}=\left\{1,\ldots ,k\right\}$ $S_{1}=\left\{1,\ldots ,k\right\}$ { $S_{1}=\left\{1,\ldots ,k\right\}$ , $S_{1}=\left\{1,\ldots ,k\right\}$ $S_{1}=\left\{1,\ldots ,k\right\}$ $}$ { $displaystyle S_{1$ } = \ $left\{1,\ldots, k\right\}).$ $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ 서 k $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ 1 $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ k $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ n $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ $wdisplay$ i w 1 $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ ′1 ′1 $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ ′ $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ ′1 ′1 ′1 ′1 ′1 ′1 ′1 ′1 ′1 ′1 ′1 ′1{ $i}\leq$ W $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$ 또한 첫 번째 항목이 맞지 않는 두 번째 $S_{2}=\left\{k+1\right\}$ $S_{2}=\left\{k+1\right\}$ 2 $=$ { $S_{2}=\left\{k+1\right\}$ $S_{2}=\left\{k+1\right\}$ $S_{2}=\left\{k+1\right\}$ $}$ { $display style$ S_ ${2$ }=\ $left\{k+1\right\}$ 을 $S_{2}=\left\{k+1\right\}$ (를) 구축합니다 $.$ $S_{1}\cup S_{2}$ $S_{1}\cup S_{2}$ $(\$ S_ ${2})$ 는 $S_{1}\cup S_{2}$ 문제의 LP 완화에 대한 상한을 제공하므로 세트 중 하나에 m $m/2$ 2 $(\displaystyle$ m $/2$ $})$ $m/2$ 의 값이 필요합니다. $S_{1}$ (\ $displaystyle$ $S_$ ${$ 1})과 $S_{2}$ S2(\ $displaystyle$ S_2}) 중 $S_{2}$ $S_{1}$ 쪽이 더 $1/2$ 이 더 좋은 것을 반환합니다 $1/2$ $(디스플레이 스타일$ 1/2) $-$ 대략 $1/2$ .

평균 성능은 $n^{-1/2}$ n - $n^{-1/2}$ 1 / $({$ n $^{-1/2}})$ 로 최적의 분산 용액으로 수렴됨을 알 수 있다.

완전 다항식 시간 근사 체계

배낭 문제에 대한 완전 다항식 시간 근사 체계(FPTAS)는 문제에 알려진 다항식 시간 솔루션이 없는 이유가 항목과 관련된 이익이 제한되지 않기 때문이라는 사실을 이용한다.이익 값 중 가장 낮은 자릿수를 반올림하면, 그것들은 다항식과 1/θ에 의해 제한된다. 여기서 θ는 솔루션의 정확성에 대한 제한이다.이 제한은 알고리즘이 최적 ^[19]해법의 (1-θ) 계수 내에서 올바른 해법을 다항 시간 내에 찾을 수 있음을 의미합니다.

알고리즘 FPTAS가 입력됩니다. $v_{i}$   $v_{i}$ ( \  $display$  style  $v$ _ { $i$ } )및 중량 출력: S' the FPTAS solution P :  $\{v_{i}\mid 1\leq i\leq n\}$   $\{v_{i}\mid 1\leq i\leq n\}$  { v i $\{v_{i}\mid 1\leq i\leq n\}$  i  $\{v_{i}\mid 1\leq i\leq n\}$  1 $\{v_{i}\mid 1\leq i\leq n\}$  n $\{v_{i}\mid 1\leq i\leq n\}$  {  $display style$  \ { v $\{v_{i}\mid 1\leq i\leq n\}$ _ i } \  $mid$  1 \  $qle i$ 。 $v'_{i}$  ${\frac {P}{n}}$ ~ n ${\frac {P}{n}}$   $v'_{i}$   $vi$  {  $displaystyle$  $v$  $' _$  $v'_{i}$ { i  $v'_{i}$ } :  $\left\lfloor {\frac {v_{i}}{K}}\right\rfloor$  ⌊  $\left\lfloor {\frac {v_{i}}{K}}\right\rfloor$  K $v'_{i}$  $⌋$  { $displaystyle$   $\$  $left$  \  $lfloor$  } { $frac$  { $v$  _ { $v'_{i}$  $i}$   $}$  \ $rfloor$ } for $\left\lfloor {\frac {v_{i}}{K}}\right\rfloor$  $v'_{i}$  for for for for for for for for for for for for for for for outlined  $outlined$  for for for for for outlined outlined outlined for for for for for for for for for outlined for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for

정리:위의 알고리즘에 의해 계산된 $세트S$ ${\$ { $displaystyle$ S}는 $S'$ $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ t $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ ( $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ ) $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ i $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ ( $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ - $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ ) ) $p$ \ $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ \ $mathrm$ { $profit }$ ( $S' )\$ $geq$ ( $1$ - \ $varepsilon$ )\ $cdot$ \ $mathrm$ { profit $}$ ( S ) $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ { profit } { profit } ( S $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$ } ( $S$ ) 。

지배 관계

필요 없는 아이템을 버리면 배낭 문제를 쉽게 해결할 수 있습니다.특정 $항목$ i(\ $displaystyle$ i $i$ 에 대해 총 무게가i(\ $displaystyle$ i $i$ 보다 작고 총 값이 $(\displaystyle$ i $i$ 값보다 큰 $항목$ J(\ $displaystyle$ J $)$ 세트를 $J$ 찾을 수 있다고 가정합니다. $그러면$ i를 $i$ $J$ 로 대체함으로써 $i$ 를 $i$ $i$ 하는 잠재적인 솔루션을 항상 개선할 수 있기 때문에 $i$ 를 최적의 $i$ 솔루션으로 나타낼 수 없습니다. 따라서 $i$ 를 $J$ 로 $i$ 하면 $i$ 를 $i$ 완전히 무시할 수 있습니다 $.$ 이 경우 J ${displaystyle$ J $}$ 가 $J$ i ${displaystyle$ i $i$ 를 $i$ 한다고 합니다.(J ${displaystyle$ J $}$ 의 아이템은 이미 소진되었을 수 있으므로 경계 배낭 문제에는 해당되지 않습니다.) $J$

지배적 관계를 찾는 것은 서치 공간의 크기를 크게 줄일 수 있습니다.지배 ^[11]관계에는 여러 가지 다른 유형이 있으며, 이들은 모두 형태의 불평등을 충족합니다.

$\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ $\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ $\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ $\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ $\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ x j $\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ w $\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ w i \ $qquad \sum _ {$ j $\in J$ $}w_$ ${$ j}, $x_{j}\$ $leq$ \alpha \, $w_$ $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ i $\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ 및 $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ J $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ J $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ J $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ J $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ v v v $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ v v $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ v $ji$ { \ $displaystylek \ sum$ \ sum \ $j$ },

$\alpha \in Z_{+}\,,J\subsetneq N$ 서 α $\alpha \in Z_{+}\,,J\subsetneq N$ Z + $\alpha \in Z_{+}\,,J\subsetneq N$ 、 ${\$ N \ $displaystyle \ alpha$ \ $in$ Z _ { + } , $J$ \ $subsetneq$ N $\alpha \in Z_{+}\,,J\subsetneq N$ $i\not \in J$ $i\not \in J$ \ $displaystyle$ i \ $in J$ $。$ $벡터$ x { $displaystyle$ x}는 $x$ $J$ 의 각 멤버의 복사 수를 나타냅니다 $J$

집단 우위: 만약 항목의 J{J\displaystyle}에 조합의 총 무게 wi보다 그들의 총액 vi보다 큰 경우 그 나는{\displaystyle 나는}-th 항목 집합적으로 J{J\displaystyle}, 나는 J{i\ll J\displaystyle}≪ 쓴, 지배하고 있다.형식적으로,∑ j∈ Jwj)j≤ wi{\displa. $ystyle$ \ $sum$ _ ${j}w_{j$ }, $x_{j}\leq w_{i}$ 및 $\sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}$ $\sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}$ " $i$ $\sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}$ $\sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}$ $\sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}$ i $\ style \sum$ _ ${$ $j$ } $v_{j$ }, $x_$ {j $}\$ geq v_ ${i}"$ 일부 $\sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}$ $x\in Z_{+}^{n}$ $Z$ + {\ $stylexstylexyle$ n\styleq v_ ${i$ }yamic 프로그래밍 접근법.실제로 이는 V $V=v_{i}$ $V=v_{i}$ \ $displaystyle$ V = $v$ _ { i $V=v_{i}$ } , W $W=w_{i}$ $W=w_{i}$ \ $displaystyle$ W = $w$ _ { i $W=w_{i}$ } , $W=w_{i}$ 이J \ $displaystyle$ J $J$ 로 $J$ 되는 $V=v_{i}$ 배낭 결정 문제를 해결하는 것과 같습니다.
문턱값 우위: i $({$ $displaystyle$ i $})$ 의 $i$ 일부 $i\prec \prec J$ 이 J $({displaystyle$ J $J$ 에 $i$ 의해 $J$ 되는 경우, i({ $displaystyle$ i $i\prec \prec J$ 의 문턱값은 J $({$ $displaystyle$ J $J$ 에 $의해$ 지배되는 문턱값입니다. 정식적으로는 $\sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ J( $\sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ $\sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ $\sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ i $(\$ J)입니다 $.$ }},\leq \alpha \,w_{나는}\,x_{j}\ ∑ j∈ J'v'j)j≥ α vi{\displaystyle \sum_{j\in J}v_{j}\,x_{j}\\geq \alpha \,v_{나는}\,}을 위한 x∈ Z+n{\displaystylex\in Z_{+}^{n}}과α ≥ 1{\displaystyle \alpha \geq 1}. 이것은 일반화의 집단 지배가 처음 소개되 in[13]과 u.sedEDUK 알고리즘에 포함되어 있습니다.이와 $\alpha$ 가장 작은 α(\ $displaystyle$ \alpha $i$ 는 $\alpha$ $t_{i}=(\alpha -1)w_{i}$ $i$ $(\$ (\ $alpha$ - 1) $w_{i$ 의 임계값을 정의합니다. 이 경우 최적의 솔루션은 최대1 $(\displaystyle$ \ $alpha$ -1)의 $\alpha -1$ i(\ $displaystyle$ $\alpha -1$ i $i$ 를 포함할 수 있습니다.
다중 우위: i $(\displaystyle$ i $)$ - 번째 $i$ $i$ 은 i $(\displaystyle$ i $i\ll _{m}j$ 로 표기된 단일 $항목$ j $displaystyle$ i)에 의해 곱셈됩니다. i $(\displaystyle$ i $)$ 가 $i$ j $(\displaystyle$ j $j$ 의 일부 복사본에 의해 지배되는 $경우$ , $w_{j}\,x_{j}\ \leq w_{i}$ 으로는 w $w_{j}\,x_{j}\ \leq w_{i}$ (\ $displaystyle w_x,$ x x x x x x, $x_j)$ w $\$ $qle$ w $\$ $le$ w $\$ $le$ w\ $le$ w\le w. $_{i$ 및 $v_{j}\,x_{j}\ \geq v_{i}$ $v_{j}\,x_{j}\ \geq v_{i}$ $v_{j}\,x_{j}\ \geq v_{i}$ $v_{j}\,x_{j}\ \geq v_{i}$ {\ $displaystyle v_{j}, x_{j}\ geq v_{i$ }( $x_{j}\in Z_{+}$ $x_{j}\in Z_{+}$ j $x_{j}\in Z_{+}$ Z $x_{j}\in Z_{+}$ + { $displaystyle x_{j}\)$ 의 $x_{j}\in Z_{+}$ 경우). $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ { $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ , $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ , $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ j $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ j ${\$ { $displaystyle$ J = \ { j \ , \ $alpha = 1$ , $x$ _ { j } = \ $lfloor$ { $frac$ { w $_$ { $i$ } { w $_$ { $j$ } } \ $lfloor$ 이 우세는 비교적 쉽게 검출할 수 있기 때문에 효율적으로 사용할 수 있다.
모듈러 우위: $b$ $(\displaystyle$ b $)$ 를 $b$ 모든 $(\displaystyle$ $i$ $i$ 에 ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ 대해 최적의 아이템으로 $합니다$ . $즉$ , v ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ b ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ v i $w$ w w w w i ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ } \ $geq$ { $frac$ { $v$ _ { i $}$ { $w$ _ { $i$ } 。이것은 가치 밀도가 가장 높은 아이템입니다. $i$ $(\displaystyle$ i $)$ - 번째 $i$ 항목은 $(\displaystyle$ i $i\ll _{\equiv }j$ 로 $표기된$ 단일 $항목 j(\displaystyle$ i)에 의해 좌우됩니다. i $(\displaystyle$ i $w_{j}+tw_{b}\leq w_{i}$ 가 $i$ j $(\displaystyle$ i)와 $j$ b(\ $displaystyle$ b $b$ 의 여러 복사본에 $의해$ 좌우됩니다. 정식으로 w $w_{j}+tw_{b}\leq w_{i}$ + $w_{j}+tw_{b}\leq w_{i}$ w $)$ 입니다. $\displaystyle w_{j}+tw_{b}\leq w_{i$ 및 $v_{j}+tv_{b}\geq v_{i}$ j + $v_{j}+tv_{b}\geq v_{i}$ $v_{j}+tv_{b}\geq v_{i}$ b $v_{j}+tv_{b}\geq v_{i}$ v $v_{j}+tv_{b}\geq v_{i}$ { $displaystyle v_{j}+tv_{b}\geq v_{i$ }. 즉, $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ { $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ , $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ , $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ , $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ , $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ j $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ { $display$ J = \ { b , j \ , \ $alpha =$ 1, x _ { b } $= t$ , $x$ _ { j } $= 1$ .

바리에이션

배낭 문제는 기본 문제의 방대한 응용 프로그램에서 많은 변형이 발생합니다.주요 변동은 항목 수, 목표 수 또는 배낭 수와 같은 일부 문제 매개변수의 수를 변경함으로써 발생합니다.

다목적 배낭 문제

이 변동은 배낭을 채우는 개인의 목표를 변경합니다.금전적 이익의 최대화와 같은 하나의 목적 대신에, 그 목적은 여러 차원을 가질 수 있다.예를 들어, 경제적 목표뿐만 아니라 환경적 또는 사회적 우려가 있을 수 있다.자주 다루는 문제에는 포트폴리오 및 운송 로지스틱 ^[22]^[23]최적화가 포함됩니다.

예를 들어 유람선을 운영한다고 가정해 보겠습니다.당신은 유명한 코미디언을 몇 명 고용할지 결정해야 합니다.이 보트는 1톤 이하의 승객을 태울 수 있으며, 연예인의 몸무게는 1000파운드 미만이어야 합니다.각각의 코미디언들은 무게가 있고, 그들의 인기를 바탕으로 사업을 하고, 특정한 연봉을 요구해요.이 예에서는 여러 가지 목표가 있습니다.당신은 물론 연예인들의 인기를 극대화하는 동시에 그들의 출연료를 최소화하기를 원한다.또한, 당신은 가능한 한 많은 연예인을 갖고 싶어합니다.

다차원 배낭 문제

이 변형에서 배낭 $i$ 의 $i$ 중량은 ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ w i ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ ( ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ 1, ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ … ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ , ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ i ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ ) { $displaystyle$ { $w$ _ { i } = ( $w$ _ { i1} , $\ldots$ , w _ { iD ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ } )에 ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ 의해 주어지며, 배낭은 D차원 용량 $(W_{1},\ldots ,W_{D})$ w_{ $iD$ $(W_{1},\ldots ,W_{D})$ W_ $(W_{1},\ldots ,W_{D})$ }, $(W_{1},\ldots ,W_{D})$ W, W, W, D, D, D, D, ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ , D, D, D, D를 가진다.목표는 각 치수 $\displaystyle$ d $\$ displaystyle $W_{d$ 를 $W_{d}$ 하지 $d$ 않도록 배낭 내 아이템 값의 합계를 최대화하는 것입니다.

다차원 배낭은 배낭보다 계산이 어렵습니다. D $D=2$ $D=2$ ${\displaystyle$ D=2 $D=2$ 의 $=$ $D=2$ 에도 P $=$ {\ $displaystyle$ =} ^[24]NP가 아니면 EPTAS가 없습니다.단, 의 알고리즘은^[25] sparse instance를 효율적으로 해결하는 것을 나타내고 있습니다.만약 m<>를 위한 일련 J){1,2,…, m}{\displaystyle J=\{1,2,\ldots ,m\}}은 다차원 배낭의 인스턴스;D{\displaystyle m<, 매우 부족하다.D}나는{\displaystyle 나는}모든 배낭을 메고 항목을 위한과 같이∃ z>입니다 나이{\displaystyle \exists;입니다 나이 z>}가∀ j∈ J∪{z}, 아니 나는 j ≥ 0{\displaystyle \fo. $rall$ j $\in$ J $\cup$ \{ $z\},\w_{ij}\geq$ 0 $}$ 및 $\forall j\in J\cup \{z\},\ w_{ij}\geq 0$ $\forall y\notin J\cup \{z\},w_{iy}=0$ " $\forall y\notin J\cup \{z\},w_{iy}=0$ "{z $\forall y\notin J\cup \{z\},w_{iy}=0$ $\forall y\notin J\cup \{z\},w_{iy}=0$ y $=$ { $displaystyle \forall$ y $\notin$ J $\{z\}, w_iy$ }= $0$ 예를 들어 무선 네트워크 ^[25]릴레이 노드에서 패킷을 스케줄링할 때 발생합니다.에서의^[25] 알고리즘은 또한 객관식 변형, 객관식 다차원 배낭의 희박한 인스턴스도 해결합니다.

IHS(높이 선반 증가) 알고리즘은 2D 배낭(2차원 단위 크기 정사각형으로 정사각형을 패킹)에 최적입니다. 최적 ^[26]패킹에 정사각형이 최대 5개 있을 때 사용합니다.

다중 배낭 문제

이 변동은 빈 포장 문제와 유사합니다.이는 항목의 하위 집합을 선택할 수 있다는 점에서 빈 포장 문제와 다른 반면, 빈 포장 문제에서는 모든 항목을 특정 빈에 포장해야 합니다.배낭이 여러 개 있다는 콘셉트입니다.이것은 사소한 변경처럼 보일 수 있지만, 초기 배낭의 용량을 추가하는 것과 동등하지는 않습니다.이 변동은 Operations Research의 많은 로드 및 스케줄링 문제에 사용되며 다항식 시간 근사 ^[27]체계를 가지고 있습니다.

2차 배낭 문제

2차 배낭 문제는 2차 및 선형 용량 ^[28]제약에 따라 2차 목적 함수를 최대화한다.이 문제는 1980년 ^[29]Gallo, Hammer 및 Simeone에 의해 도입되었지만, 이 문제의 첫 번째 해결은 1975년 ^[30]Witzgall로 거슬러 올라간다.

부분집합 문제

서브셋 합계 문제는 각 항목의 무게가 $w_{i}=v_{i}$ $=$ $w_{i}=v_{i}$ ${$ }= $v_{i$ 와 같은 $w_{i}=v_{i}$ 한 경우입니다.암호화 분야에서 배낭 문제라는 용어는 서브셋 합계 문제를 가리키기 위해 자주 사용되며 일반적으로 Karp의 21 NP-com 중 하나로 알려져 있습니다.사소한 ^[31]문제

부분집합 문제의 일반화를 다중 부분집합 문제라고 하는데, 이 문제에서는 동일한 용량을 가진 여러 개의 빈이 존재합니다.일반화에는 FPTAS가 ^[32]없는 것으로 나타났습니다.

기하학적 배낭 문제

기하학적 배낭 문제에는 값이 다른 직사각형 집합과 직사각형 배낭이 있습니다.목표는 가능한 한 큰 가치를 배낭에 ^[33]담는 것입니다.

「」를 참조해 주세요.

메모들

^ Mathews, G. B. (25 June 1897). "On the partition of numbers" (PDF). Proceedings of the London Mathematical Society. 28: 486–490. doi:10.1112/plms/s1-28.1.486.
^ Dantzig, Tobias (2007). Number : the language of science (The Masterpiece Science ed.). New York: Plume Book. ISBN 9780452288119.
^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack problems. Berlin: Springer. p. 449. ISBN 978-3-540-40286-2. Retrieved 5 May 2022.
^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack problems. Berlin: Springer. p. 461. ISBN 978-3-540-40286-2. Retrieved 5 May 2022.
^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack problems. Berlin: Springer. p. 465. ISBN 978-3-540-40286-2. Retrieved 5 May 2022.
^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack problems. Berlin: Springer. p. 472. ISBN 978-3-540-40286-2. Retrieved 5 May 2022.
^ Feuerman, Martin; Weiss, Harvey (April 1973). "A Mathematical Programming Model for Test Construction and Scoring". Management Science. 19 (8): 961–966. doi:10.1287/mnsc.19.8.961. JSTOR 2629127.
^ Skiena, S. S. (September 1999). "Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository". ACM SIGACT News. 30 (3): 65–74. CiteSeerX 10.1.1.41.8357. doi:10.1145/333623.333627. ISSN 0163-5700. S2CID 15619060.
^ 피싱어, D. 2003배낭의 어려운 문제는 어디에 있습니까?테크니컬 리포트 2003/08, 덴마크 코펜하겐 대학교 컴퓨터 과학부.
^ Caccetta, L.; Kulanoot, A. (2001). "Computational Aspects of Hard Knapsack Problems". Nonlinear Analysis. 47 (8): 5547–5558. doi:10.1016/s0362-546x(01)00658-7.
^ ^a ^b ^c Poirriez, Vincent; Yanev, Nicola; Andonov, Rumen (2009). "A hybrid algorithm for the unbounded knapsack problem". Discrete Optimization. 6 (1): 110–124. doi:10.1016/j.disopt.2008.09.004. ISSN 1572-5286.
^ Wojtczak, Dominik (2018). "On Strong NP-Completeness of Rational Problems". International Computer Science Symposium in Russia. Lecture Notes in Computer Science. 10846: 308–320. arXiv:1802.09465. doi:10.1007/978-3-319-90530-3_26. ISBN 978-3-319-90529-7. S2CID 3637366.
^ ^a ^b Andonov, Rumen; Poirriez, Vincent; Rajopadhye, Sanjay (2000). "Unbounded Knapsack Problem : dynamic programming revisited". European Journal of Operational Research. 123 (2): 168–181. CiteSeerX 10.1.1.41.2135. doi:10.1016/S0377-2217(99)00265-9.
^ S. 마르텔로, P.Toth, 배낭 문제:알고리즘과 컴퓨터 구현, John Wiley and Sons, 1990
^ S. 마르텔로, D.삐삐삐삐삐삐삐삐삐삐삐삐삐삐삐삐삐.0-1 배낭 문제에 대한 동적 프로그래밍 및 강력한 경계, 관리. 경전, 45:414~424, 1999.
^ Plateau, G.; Elkihel, M. (1985). "A hybrid algorithm for the 0-1 knapsack problem". Methods of Oper. Res. 49: 277–293.
^ Martello, S.; Toth, P. (1984). "A mixture of dynamic programming and branch-and-bound for the subset-sum problem". Manag. Sci. 30 (6): 765–771. doi:10.1287/mnsc.30.6.765.
^ Horowitz, Ellis; Sahni, Sartaj (1974), "Computing partitions with applications to the knapsack problem", Journal of the Association for Computing Machinery, 21 (2): 277–292, doi:10.1145/321812.321823, hdl:1813/5989, MR 0354006, S2CID 16866858
^ ^a ^b 바지라니, 비제이근사 알고리즘Springer-Verlag Berlin Heidelberg, 2003.
^ Dantzig, George B. (1957). "Discrete-Variable Extremum Problems". Operations Research. 5 (2): 266–288. doi:10.1287/opre.5.2.266.
^ Calvin, James M.; Leung, Joseph Y. -T. (1 May 2003). "Average-case analysis of a greedy algorithm for the 0/1 knapsack problem". Operations Research Letters. 31 (3): 202–210. doi:10.1016/S0167-6377(02)00222-5.
^ 장, T.J. 등카디널리티 제약 포트폴리오 최적화를 위한 휴리스틱스.테크니컬 리포트, 런던 SW7 2AZ, 영국:1998년 5월 임페리얼 칼리지 경영학교
^ 장, C.S. 등"DC 철도 시스템의 트랙션 변전소에 대한 유전자 알고리즘 기반의 바이리테리온 최적화"포겔 [102], 11-16.
^ Kulik, A.; Shachnai, H. (2010). "There is no EPTAS for two dimensional knapsack" (PDF). Inf. Process. Lett. 110 (16): 707–712. CiteSeerX 10.1.1.161.5838. doi:10.1016/j.ipl.2010.05.031.
^ ^a ^b ^c 코헨, R. 및 그레블라, G. 2014."릴레이 노드가 있는 무선 네트워크에서의 다차원 OFDMA 스케줄링"프로세서에 있습니다. IEEE INFOCOM'14, 2427–2435
^ Yan Lan, György Dosa, Shin Han, Cheyang Zhou, Atila Benk [ [ 1 ]: 2D 배낭: 포장용 사각, 이론 컴퓨터 과학 Vol. 508, 35-40 페이지.
^ Chandra Chekuri and Sanjeev Khanna (2005). "A PTAS for the multiple knapsack problem". SIAM Journal on Computing. 35 (3): 713–728. CiteSeerX 10.1.1.226.3387. doi:10.1137/s0097539700382820.
^ Wu, Z. Y.; Yang, Y. J.; Bai, F. S.; Mammadov, M. (2011). "Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems". J Optim Theory Appl. 151 (2): 241–259. doi:10.1007/s10957-011-9885-4. S2CID 31208118.
^ Gallo, G.; Hammer, P. L.; Simeone, B. (1980). Quadratic knapsack problems. Mathematical Programming Studies. Vol. 12. pp. 132–149. doi:10.1007/BFb0120892. ISBN 978-3-642-00801-6.
^ Witzgall, C. (1975). "Mathematical methods of site selection for Electronic Message Systems (EMS)". NASA Sti/Recon Technical Report N. NBS Internal report. 76: 18321. Bibcode:1975STIN...7618321W.
^ 리처드 M. 카프(1972년)."조합적 문제의 경감"R. E. 밀러와 J. W. 대처(편집자)에서.컴퓨터 계산의 복잡성.뉴욕: 플레넘. 페이지 85~103
^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000). "The Multiple Subset Sum Problem". SIAM J. Optim. 11 (2): 308–319. CiteSeerX 10.1.1.21.9826. doi:10.1137/S1052623498348481.
^ Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1–19. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1. ISBN 978-3-939897-89-7.

레퍼런스

Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A6: MP9, 247페이지.
Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems. Springer. doi:10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. MR 2161720. S2CID 28836720.
Martello, Silvano; Toth, Paolo (1990). Knapsack problems: Algorithms and computer implementations. Wiley-Interscience. ISBN 978-0-471-92420-3. MR 1086874.

외부 링크

책 "Knapsack 문제:알고리즘과 컴퓨터 구현", Silvano Martello와 Paolo Toth의 작품
배낭 문제에 대한 강의 슬라이드
PYASUKP: 하지만 코드에서는 하이브리드 알고리즘, 벤치마크 및 일부 논문의 다운로드 가능한 복사본에서 우세 관계를 활용하는 무한 Knapsack 문제의 또 다른 해결사입니다.
데이비드 피싱어 홈페이지(David Pisinger)에 게재된 일부 논문 다운로드 가능 복사본(하드 배낭 문제 포함)")
Rosetta Code에서 여러 언어로 된 Knapsack 문제 해결 방법
0/1 Knapsack 문제에 대한 동적 프로그래밍 알고리즘
배낭 문제 해결사(온라인)
루비의 유전자 알고리즘을 사용한 0-1-KNAPSACK 해결 2011년 5월 23일 웨이백 머신에서 아카이브
2차 배낭 문제에 대한 코드

[1] Mathews, G. B. (25 June 1897). "On the partition of numbers" (PDF). Proceedings of the London Mathematical Society. 28: 486–490. doi:10.1112/plms/s1-28.1.486.

[2] Dantzig, Tobias (2007). Number : the language of science (The Masterpiece Science ed.). New York: Plume Book. ISBN 9780452288119.

[3] Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack problems. Berlin: Springer. p. 449. ISBN 978-3-540-40286-2. Retrieved 5 May 2022.

[4] Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack problems. Berlin: Springer. p. 461. ISBN 978-3-540-40286-2. Retrieved 5 May 2022.

[5] Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack problems. Berlin: Springer. p. 465. ISBN 978-3-540-40286-2. Retrieved 5 May 2022.

[6] Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack problems. Berlin: Springer. p. 472. ISBN 978-3-540-40286-2. Retrieved 5 May 2022.

[7] Feuerman, Martin; Weiss, Harvey (April 1973). "A Mathematical Programming Model for Test Construction and Scoring". Management Science. 19 (8): 961–966. doi:10.1287/mnsc.19.8.961. JSTOR 2629127.

[8] Skiena, S. S. (September 1999). "Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository". ACM SIGACT News. 30 (3): 65–74. CiteSeerX 10.1.1.41.8357. doi:10.1145/333623.333627. ISSN 0163-5700. S2CID 15619060.

[pisinger200308-9] 피싱어, D. 2003배낭의 어려운 문제는 어디에 있습니까?테크니컬 리포트 2003/08, 덴마크 코펜하겐 대학교 컴퓨터 과학부.

[Cacetta2001-10] Caccetta, L.; Kulanoot, A. (2001). "Computational Aspects of Hard Knapsack Problems". Nonlinear Analysis. 47 (8): 5547–5558. doi:10.1016/s0362-546x(01)00658-7.

[poirriez_et_all_2009-11] Poirriez, Vincent; Yanev, Nicola; Andonov, Rumen (2009). "A hybrid algorithm for the unbounded knapsack problem". Discrete Optimization. 6 (1): 110–124. doi:10.1016/j.disopt.2008.09.004. ISSN 1572-5286.

[Wojtczak18-12] Wojtczak, Dominik (2018). "On Strong NP-Completeness of Rational Problems". International Computer Science Symposium in Russia. Lecture Notes in Computer Science. 10846: 308–320. arXiv:1802.09465. doi:10.1007/978-3-319-90530-3_26. ISBN 978-3-319-90529-7. S2CID 3637366.

[eduk2000-13] Andonov, Rumen; Poirriez, Vincent; Rajopadhye, Sanjay (2000). "Unbounded Knapsack Problem : dynamic programming revisited". European Journal of Operational Research. 123 (2): 168–181. CiteSeerX 10.1.1.41.2135. doi:10.1016/S0377-2217(99)00265-9.

[martellototh90-14] S. 마르텔로, P.Toth, 배낭 문제:알고리즘과 컴퓨터 구현, John Wiley and Sons, 1990

[martellopisingertoth99a-15] S. 마르텔로, D.삐삐삐삐삐삐삐삐삐삐삐삐삐삐삐삐삐.0-1 배낭 문제에 대한 동적 프로그래밍 및 강력한 경계, 관리. 경전, 45:414~424, 1999.

[plateau85-16] Plateau, G.; Elkihel, M. (1985). "A hybrid algorithm for the 0-1 knapsack problem". Methods of Oper. Res. 49: 277–293.

[martellotothe99-17] Martello, S.; Toth, P. (1984). "A mixture of dynamic programming and branch-and-bound for the subset-sum problem". Manag. Sci. 30 (6): 765–771. doi:10.1287/mnsc.30.6.765.

[18] Horowitz, Ellis; Sahni, Sartaj (1974), "Computing partitions with applications to the knapsack problem", Journal of the Association for Computing Machinery, 21 (2): 277–292, doi:10.1145/321812.321823, hdl:1813/5989, MR 0354006, S2CID 16866858

[Vazirani,_Vijay_2003-19] 바지라니, 비제이근사 알고리즘Springer-Verlag Berlin Heidelberg, 2003.

[dantzig1957-20] Dantzig, George B. (1957). "Discrete-Variable Extremum Problems". Operations Research. 5 (2): 266–288. doi:10.1287/opre.5.2.266.

[21] Calvin, James M.; Leung, Joseph Y. -T. (1 May 2003). "Average-case analysis of a greedy algorithm for the 0/1 knapsack problem". Operations Research Letters. 31 (3): 202–210. doi:10.1016/S0167-6377(02)00222-5.

[22] 장, T.J. 등카디널리티 제약 포트폴리오 최적화를 위한 휴리스틱스.테크니컬 리포트, 런던 SW7 2AZ, 영국:1998년 5월 임페리얼 칼리지 경영학교

[23] 장, C.S. 등"DC 철도 시스템의 트랙션 변전소에 대한 유전자 알고리즘 기반의 바이리테리온 최적화"포겔 [102], 11-16.

[24] Kulik, A.; Shachnai, H. (2010). "There is no EPTAS for two dimensional knapsack" (PDF). Inf. Process. Lett. 110 (16): 707–712. CiteSeerX 10.1.1.161.5838. doi:10.1016/j.ipl.2010.05.031.

[CohenGrebla-25] 코헨, R. 및 그레블라, G. 2014."릴레이 노드가 있는 무선 네트워크에서의 다차원 OFDMA 스케줄링"프로세서에 있습니다. IEEE INFOCOM'14, 2427–2435

[26] Yan Lan, György Dosa, Shin Han, Cheyang Zhou, Atila Benk [ [ 1 ]: 2D 배낭: 포장용 사각, 이론 컴퓨터 과학 Vol. 508, 35-40 페이지.

[27] Chandra Chekuri and Sanjeev Khanna (2005). "A PTAS for the multiple knapsack problem". SIAM Journal on Computing. 35 (3): 713–728. CiteSeerX 10.1.1.226.3387. doi:10.1137/s0097539700382820.

[QKP-28] Wu, Z. Y.; Yang, Y. J.; Bai, F. S.; Mammadov, M. (2011). "Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems". J Optim Theory Appl. 151 (2): 241–259. doi:10.1007/s10957-011-9885-4. S2CID 31208118.

[29] Gallo, G.; Hammer, P. L.; Simeone, B. (1980). Quadratic knapsack problems. Mathematical Programming Studies. Vol. 12. pp. 132–149. doi:10.1007/BFb0120892. ISBN 978-3-642-00801-6.

[30] Witzgall, C. (1975). "Mathematical methods of site selection for Electronic Message Systems (EMS)". NASA Sti/Recon Technical Report N. NBS Internal report. 76: 18321. Bibcode:1975STIN...7618321W.

[31] 리처드 M. 카프(1972년)."조합적 문제의 경감"R. E. 밀러와 J. W. 대처(편집자)에서.컴퓨터 계산의 복잡성.뉴욕: 플레넘. 페이지 85~103

[32] Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000). "The Multiple Subset Sum Problem". SIAM J. Optim. 11 (2): 308–319. CiteSeerX 10.1.1.21.9826. doi:10.1137/S1052623498348481.

[33] Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1–19. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1. ISBN 978-3-939897-89-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

Search

배낭 문제

네임스페이스

더

목차

적용들

정의.

계산의 복잡성

해결하는

동적 프로그래밍 사전 알고리즘

0-1 배낭 문제

미트 인 더 미들

근사 알고리즘

탐욕 근사 알고리즘

완전 다항식 시간 근사 체계

지배 관계

바리에이션

다목적 배낭 문제

다차원 배낭 문제

다중 배낭 문제

2차 배낭 문제

부분집합 문제

기하학적 배낭 문제

「」를 참조해 주세요.

메모들

레퍼런스

외부 링크

Search

배낭 문제

적용들

정의.

계산의 복잡성

해결하는

동적 프로그래밍 사전 알고리즘

0-1 배낭 문제

미트 인 더 미들

근사 알고리즘

탐욕 근사 알고리즘

완전 다항식 시간 근사 체계

지배 관계

바리에이션

다목적 배낭 문제

다차원 배낭 문제

다중 배낭 문제

2차 배낭 문제

부분집합 문제

기하학적 배낭 문제

「 」를 참조해 주세요.

메모들

레퍼런스

외부 링크

「」를 참조해 주세요.