Агуулгыг алгасах

Үүргэвчийн бодлого

Урьдчилан шаардагдах мэдлэг: Динамик программчлалын танилцуулга

Оршил

Дараах жишээг авч үзье:

[USACO07 Dec] Charm Bracelet

$n$ ялгаатай эд зүйл ба $W$ багтаамжтай үүргэвч байна. Эд зүйл бүр жин ($w_{i}$) ба үнэ цэнэ ($v_{i}$) гэсэн 2 шинж чанартай. Нийт жин нь $W$ багтаамжаас хэтрэхгүй бөгөөд нийт үнэ цэнэ хамгийн их байхаар эд зүйлсийн дэд олонлогийг сонгож үүргэвчид хийх ёстой.

Дээрх жишээнд эд зүйл бүр хоёртын 0 ба 1-д харгалзах ердөө хоёр боломжит төлөвтэй (авсан эсвэл аваагүй). Тиймээс энэ төрлийн бодлогыг "0-1 үүргэвчийн бодлого" гэж нэрлэдэг.

0-1 Үүргэвч

Тайлбар

Дээрх жишээнд бодлогын оролт нь дараах: $i$-р эд зүйлийн жин $w_{i}$, $i$-р эд зүйлийн үнэ цэнэ $v_{i}$, ба үүргэвчийн нийт багтаамж $W$.

Зөвхөн эхний $i$ эд зүйлийг авч үзэх үед $j$ багтаамжтай үүргэвчийн зөөж чадах хамгийн их нийт үнэ цэнийг агуулах динамик программчлалын төлвийг $f_{i, j}$ гэе.

Эхний $i-1$ эд зүйлийн бүх төлөв боловсруулагдсан гэж үзвэл $i$-р эд зүйлийн хувьд ямар сонголт байх вэ?

  • Түүнийг үүргэвчид хийхгүй үед үлдсэн багтаамж өөрчлөгдөхгүй, нийт үнэ цэнэ өөрчлөгдөхгүй. Тиймээс энэ тохиолдолд хамгийн их үнэ цэнэ нь $f_{i-1, j}$
  • Түүнийг үүргэвчид хийх үед үлдсэн багтаамж $w_{i}$-ээр буурч, нийт үнэ цэнэ $v_{i}$-ээр нэмэгдэх тул энэ тохиолдолд хамгийн их үнэ цэнэ нь $f_{i-1, j-w_i} + v_i$

Эндээс бид dp шилжилтийн тэгшитгэлийг гаргаж авна:

$$f_{i, j} = \max(f_{i-1, j}, f_{i-1, j-w_i} + v_i)$$

Түүнчлэн $f_{i}$ нь зөвхөн $f_{i-1}$-ээс хамаардаг тул бид эхний хэмжээсийг хасаж болно. Бид шилжилтийн дүрмийг олж авна

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

ба үүнийг $j$-ийн буурах дарааллаар гүйцэтгэх ёстой (ингэснээр $f_{j-w_i}$ нь далдуур $f_{i,j-w_i}$ биш $f_{i-1,j-w_i}$-д харгалзана).

Энэ шилжилтийн дүрмийг ойлгох нь чухал, учир нь үүргэвчийн бодлогуудын ихэнх шилжилт үүнтэй адил байдлаар гарна.

Implementation

The algorithm described can be implemented in $O(nW)$ as:

for (int i = 1; i <= n; i++)
  for (int j = W; j >= w[i]; j--)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

Дахин хэлэхэд гүйцэтгэлийн дарааллыг анхаарна уу. Дараах инвариантыг хангахын тулд үүнийг чанд дагах ёстой: $(i, j)$ хос боловсруулагдахаас яг өмнө $f_k$ нь $k > j$-ийн хувьд $f_{i,k}$-д, харин $k < j$-ийн хувьд $f_{i-1,k}$-д харгалзана. Энэ нь $f_{j-w_i}$ нь $i$-р биш $(i-1)$-р алхмаас авагдахыг баталгаажуулна.

Бүрэн үүргэвч

Бүрэн үүргэвчийн загвар нь 0-1 үүргэвчтэй төстэй, 0-1 үүргэвчээс цорын ганц ялгаа нь эд зүйлийг ердөө нэг удаа биш, хязгааргүй олон удаа сонгож болдогт оршино.

Бид төлвийг тодорхойлохын тулд 0-1 үүргэвчийн санааг ашиглаж болно: $f_{i, j}$ нь эхний $i$ эд зүйлийг $j$ хамгийн их багтаамжтайгаар ашиглан үүргэвчийн олж авах хамгийн их үнэ цэнэ.

Төлвийн тодорхойлолт нь 0-1 үүргэвчийнхтэй төстэй боловч түүний шилжилтийн дүрэм нь 0-1 үүргэвчийнхээс өөр болохыг тэмдэглэх нь зүйтэй.

Тайлбар

Тривиаль арга бол эхний $i$ эд зүйлийн хувьд эд зүйл бүрийг хэдэн удаа авахыг тоолох явдал юм. Үүний time complexity нь $O(n^2W)$.

Энэ нь дараах шилжилтийн тэгшитгэлийг өгнө:

$$f_{i, j} = \max\limits_{k=0}^{\infty}(f_{i-1, j-k\cdot w_i} + k\cdot v_i)$$

Үүний зэрэгцээ энэ нь "хавтгай" тэгшитгэл болж хялбарчлагдана:

$$f_{i, j} = \max(f_{i-1, j},f_{i, j-w_i} + v_i)$$

Энэ нь ажилладаг шалтгаан нь $f_{i, j-w_i}$ аль хэдийн $f_{i, j-2\cdot w_i}$ гэх мэтчилэн шинэчлэгдсэн байдагт оршино.

0-1 үүргэвчтэй адил бид space complexity-г оновчтой болгохын тулд эхний хэмжээсийг хасаж болно. Энэ нь бидэнд 0-1 үүргэвчтэй ижил шилжилтийн дүрмийг өгнө.

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

Implementation

The algorithm described can be implemented in $O(nW)$ as:

for (int i = 1; i <= n; i++)
  for (int j = w[i]; j <= W; j++)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

Ижил шилжилтийн дүрэмтэй хэдий ч дээрх код 0-1 үүргэвчийн хувьд буруу.

Кодыг анхааралтай ажиглавал одоо боловсруулж буй эд зүйл $i$ ба одоогийн төлөв $f_{i,j}$-ийн хувьд $j\geqslant w_{i}$ үед $f_{i,j}$ нь $f_{i,j-w_{i}}$-ээр нөлөөлөгдөхийг бид харна. Энэ нь эд зүйл $i$-г үүргэвчид олон удаа хийж болохтой тэнцүү бөгөөд энэ нь 0-1 үүргэвчийн бодлого биш бүрэн үүргэвчийн бодлоготой нийцнэ.

Олон тооны үүргэвч

Олон тооны үүргэвч нь бас 0-1 үүргэвчийн хувилбар юм. Гол ялгаа нь эд зүйл бүр ердөө $1$ биш $k_i$ ширхэг байдагт оршино.

Тайлбар

Маш энгийн санаа бол: "эд зүйл бүрийг $k_i$ удаа сонгох" нь "ижил эд зүйлийн $k_i$ ширхэгийг нэг нэгээр нь сонгох"-той тэнцүү. Ингэснээр үүнийг дараах шилжилтийн функцээр тодорхойлж болох 0-1 үүргэвчийн загвар болгон хувиргана:

$$f_{i, j} = \max_{k=0}^{k_i}(f_{i-1,j-k\cdot w_i} + k\cdot v_i)$$

Энэ процессын time complexity нь $O(W\sum\limits_{i=1}^{n}k_i)$

Хоёртын бүлэглэлийн оновчлол

Бид оновчлолын тулд олон тооны үүргэвчийн загварыг 0-1 үүргэвчийн загвар болгон хувиргахыг авч үзсээр байна. $O(Wn)$ time complexity-г дээрх аргаар цаашид оновчтой болгож чадахгүй тул бид $O(\sum k_i)$ бүрэлдэхүүн хэсэгт анхаарлаа хандуулна.

$i$-р эд зүйлээс салгасан $j$-р эд зүйлийг $A_{i, j}$ гэж тэмдэглэе. Дээр авч үзсэн тривиаль аргад $A_{i, j}$ нь бүх $j \leq k_i$-ийн хувьд ижил эд зүйлийг илэрхийлнэ. Бидний бага үр ашгийн гол шалтгаан нь бид маш их давтан ажил хийж байгаад оршино. Жишээ нь $\{A_{i, 1},A_{i, 2}\}$-г сонгох, мөн $\{A_{i, 2}, A_{i, 3}\}$-г сонгохыг авч үзье. Эдгээр хоёр нөхцөл бүрэн эквивалент. Тиймээс салгах аргыг оновчтой болгох нь time complexity-г ихээхэн бууруулна.

Бүлэглэлийг хоёртын бүлэглэл ашиглан илүү үр ашигтай болгодог.

Тодруулбал $A_{i, j}$ нь $2^j$ ширхэг эд зүйл агуулна ($j\in[0,\lfloor \log_2(k_i+1)\rfloor-1]$). Хэрэв $k_i + 1$ нь $2$-ын бүхэл зэрэг биш бол үүнийг нөхөхийн тулд $k_i-(2^{\lfloor \log_2(k_i+1)\rfloor}-1)$ хэмжээтэй өөр багц ашиглана.

Дээрх салгах аргаар цөөн хэдэн $A_{i, j}$-г сонгох замаар $\leq k_i$ эд зүйлийн дурын нийлбэрийг олж авах боломжтой. Эд зүйл бүрийг тайлбарласан аргаар салгасны дараа бодлогын шинэ томьёоллыг бодоход 0-1 үүргэвчийн аргыг ашиглахад хангалттай.

Энэ оновчлол нь бидэнд $O(W\sum\limits_{i=1}^{n}\log k_i)$ time complexity өгнө.

Implementation

index = 0;
for (int i = 1; i <= n; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

Монотон дарааллын оновчлол

Энэ оновчлолд бид үүргэвчийн бодлогыг максимум дараалал-ын бодлого болгон хувиргахыг зорино.

Тайлбарлахад тохиромжтой байлгах үүднээс $g_{x, y} = f_{i, x \cdot w_i + y} ,\space g'_{x, y} = f_{i-1, x \cdot w_i + y}$ гэе. Тэгвэл шилжилтийн дүрмийг дараах байдлаар бичиж болно:

$$g_{x, y} = \max_{k=0}^{k_i}(g'_{x-k, y} + v_i \cdot k)$$

Цаашилбал $G_{x, y} = g'_{x, y} - v_i \cdot x$ гэе. Тэгвэл шилжилтийн дүрмийг дараах байдлаар илэрхийлж болно:

$$g_{x, y} \gets \max_{k=0}^{k_i}(G_{x-k, y}) + v_i \cdot x$$

Энэ нь сонгодог монотон дарааллын оновчлолын хэлбэрт хувирна. $G_{x, y}$-г $O(1)$-д тооцоолж болох тул тогтмол $y$-ийн хувьд бид $g_{x, y}$-г $O(\lfloor \frac{W}{w_i} \rfloor)$ хугацаанд тооцоолж болно. Тиймээс бүх $g_{x, y}$-г олох complexity нь $O(\lfloor \frac{W}{w_i} \rfloor) \times O(w_i) = O(W)$. Ингэснээр алгоритмын нийт complexity нь $O(nW)$ болж буурна.

Холимог үүргэвч

Холимог үүргэвчийн бодлого нь дээр тайлбарласан гурван бодлогын хослолыг агуулна. Өөрөөр хэлбэл зарим эд зүйлийг зөвхөн нэг удаа, заримыг хязгааргүй, заримыг хамгийн ихдээ $k$ удаа авч болно.

Бодлого айдас төрүүлэм санагдаж болох ч өмнөх үүргэвчийн бодлогуудын үндсэн санааг ойлгож, тэдгээрийг нэгтгэвэл та үүнийг хийж чадна. Шийдлийн псевдокод дараах байдалтай:

for (each item) {
  if (0-1 knapsack)
    Apply 0-1 knapsack code;
  else if (complete knapsack)
    Apply complete knapsack code;
  else if (multiple knapsack)
    Apply multiple knapsack code;
}

Дасгал бодлогууд