$ V_i= i $ 일 때 knapsack 문제 np-hard입니까?

Question

배출 문제는 np-hard이며 다음과 같이 공식화 될 수 있습니다. $$ \ begin {정렬} & \ text {maximize} \ sum_ {i= 1} ^ n v_i x_i, \ tag {p1} \\ & \ text {} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ text {and} x_i \ in \ {0,1 \}. \ end {정렬} $$

$ V_I= I $ 이라면 어떨까요?그것은 여전히 np-hard입니까?

$$ \ begin {Align} & \ text {maximize} \ sum_ {i= 1} ^ n ix_i, \ tag {p2} \\ & \ text {} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ text {and} x_i \ in \ {0,1 \}. \ end {정렬} $$

(P1) (P2)를 줄이려고합니다 (P1).(P1)의 인스턴스를 감안할 때, 나는 동일한 수의 항목, 같은 가중치를 생성합니다.자, 저는 솔루션을 (P1) 및 (P2) 관련해야합니다.

Answer 1

아니오,이 문제는 $ \ mathbf {p} $ 에 있습니다. 모든 값의 합계가 $ 1 + 2 \ ldots + n \ \ frac {n (n + 1)} {2}= mathcal {o}이된다는 것입니다. n ^ 2) $ , 입력 크기의 다항식입니다. $ V_i= i $ 의 추가 제한이 없으면 모든 값의 합계는 입력 크기가 바이너리로 표시되므로 값 크기가 입력 크기가 표시 될 수 있습니다.

$ dp [i] [v] $ 을 정의 할 수 있습니다. 여기서 $ 1 \ leq i \ leq n $ 및 $ 0 \ leq v \ leq \ frac {n (n + 1)} {2} $ , 값을 얻는 데 필요한 최소 무게가됩니다. 최초의 $ i $ 항목 만 사용하여 최소한 $ v $ 의 $ dp [i] [v]= inf $ 을 설정할 것입니다. 최종 응답은 $ dp [n] [v] \ leq w $ $ v $ 입니다. >.

DP 값은 다음과 같이 계산할 수 있습니다.

$ DP [i] [v]=min (DP [I-1] [v], W_I + DP [i-1] [v - v_i]) .

첫 번째 용어는 $ i ^ {th} $ 항목의 가능성을 선택하지 않으며 두 번째 용어는 선택할 가능성이 있습니다. < / P>

$ \ mathcal {o} (n ^ 3) $ 시간 및 $를 해결할 수 있습니다. \ mathcal {o} (n ^ 3) $ 공간은 $ \ mathcal {o} (n ^ 2) $ 공간으로 축소 될 수 있습니다. $ \ frac {n (n + 1) {2} + 1 $ 의 두 개의 배열을 재사용하기 만하면됩니다.