동적 프로그래밍 - 도둑 변형 문제

Question

도둑의 변형 인 동적 프로그래밍 문제가 발생했습니다.

당신이 도둑이고 당신은 rob :

행에 여러 주택이 주어집니다.

$$ House_1, House_2 \ Dots House_n $$

다음 값을 갖는 각 집이 $$ (x_i \ geq y_i \ geq z_i \ gt0) $$

집을 털는 경우 x 이익을 얻지 만 주택 중 어느 것도 없습니다.

집을 털고 정확히 하나의 인접한 주택 중 하나를 빼앗는 경우 y 이익을 얻습니다.

집을 털고 모두 집에 주택을 털는 경우 z 이익을 얻습니다.

A-B-C가있는 주택이있는 경우 :

$$ Profit (001)= 0 + 0 + C_x $$ $$ PROP (101)= A_X + 0 + C_x $$ $$ profit (110)= a_y + b_y + 0 $$ $$ profit (111)= a_y + b_z + c_y $$

1 곳은 집을 강탈하는 것을 의미합니다.

첫 번째와 마지막 집에 대한 z 값을 사용할 수 없으며 각 값 집합은 무작위입니다.

이제 질문은 다음과 같습니다. 최대 이익을 얻으려면 어느 집을 롭시겠습니까?

내 주요 문제는이 문제에 대한 기본 사례를 설정할 수 없다는 것입니다.

처음에는 모든 집이 도둑질을하지 않을 때 0-n에서 도둑질을 할 수있는 n * m 배열을 만듭니다. 그것을 롭게하지만 아무것도 내 렸습니다.

모든 팁이나 방향을 알 수 있습니다.

미리 감사드립니다.

Answer 1

$ i= 1, \ dots, n $ 및 $ r \ in \ e, r, b \} $ $ OPT [i, r] $ 을 정의하십시오. 첫 번째 $ i $ 주택의 적절한 하위 집합을 다음과 같은 제약 조건으로 강탈함으로써 얻을 수있는 최대 이익 :

• $ x= s $ ( s kip에서와 같이) 집 $ i $ 은 강도 없어서는 안됩니다.
• $ x= r $ 집 $ i $ 은 r 집 $ i + 1 $ 은 강하지 않습니다 (나중에 사례 구별을 피하기 위해 우리는 집 $ i + 1 $ 은 $ i= n $ 에도 존재합니다.
• $ x= b $ b oth house $ i $ 및 하우스 $ i + 1 $ 도둑질해야합니다.

$ i= 1 $ $ opt [1, s]= 0 $ , $ opt [1, r]= x_1 $ , $ opt [1, b]= y_1 $ .

$ i> 1 $ : $$ OPT [i, s]=max \ {opt [i-1, s], opt [i-1, r] \}, $$ $$ OPT [i, r]=max \ {x_i + OPT [i-1, s], y_i + opt [i-1, b] \}, $$ $$ OPT [i, b]=max \ {y_i + opt [i-1, s], z_i + opt [i-1, b] \}. $$

최적의 이익은 다음과 같습니다. $ \ max \ {opt [n, s], opt [n, r] \} $ \ / span> 및 $ o (n) $ 위의 수식을 사용하여 전체 시간.