Даацад багтах зүйлсээс нийт үнэ нь хамгийн их байхаар сонгоно. dp[i][j] хүснэгтийг мөр мөрөөр нь бөглөж боддог.

IntermediateХугацаа: O(n · W)Санах ой: O(n · W)
HackerRank дээр бодох

Эхлээд жижиг бодлого

Үүргэвчинд 5 кг багтана. Гурван зүйл байна: 2 кг (үнэ 3), 3 кг (үнэ 4), 4 кг (үнэ 5). Зүйл бүрийг ганц удаа л авна. Нийт үнийг хамгийн их болгоё.

2 кг ба 3 кг-ийг авбал яг 5 кг, үнэ 3 + 4 = 7. 4 кг-ийг авбал өөр юу ч багтахгүй, үнэ 5. Хариу 7.

Энгийн аргаас санаа руу

Энгийн арга бол бүх дэд олонлогийг шалгах. n зүйлд 2ⁿ сонголт, n = 100 бол хэзээ ч дуусахгүй. Үнэтэйг нь эсвэл хөнгөнийг нь түрүүлж авах Greedy ч алддаг.

Гол санаа: зүйлсийг нэг нэгээр нь шийднэ. dp[i][j] нь эхний i зүйлээс сонгоод j кг даацад багтаах хамгийн их үнэ. i-р зүйлийг авахгүй бол dp[i - 1][j]. Авбал түүнд w[i] кг зай гаргах ёстой: dp[i - 1][j - w[i]] + v[i]. Хоёрын ихийг нь авна.

Нэр томьёо ба тэмдэглэгээ

dp[i][j]
State: эхний i зүйлээс сонгоод j кг даацад багтаах хамгийн их үнэ.
w[i], v[i]
i-р зүйлийн жин ба үнэ. Зүйлс 1-ээс дугаарлагдана.
W
Үүргэвчийн даац. Хүснэгт (n + 1) × (W + 1) хэмжээтэй.
0/1
Зүйл бүрийг авахгүй (0) эсвэл нэг удаа авна (1). Хагас эсвэл хоёр удаа авахгүй.
i \ j012345670
0
0
0
0
0
0
0
0
1: 1 кг, 1₮
0
2: 3 кг, 4₮
0
3: 4 кг, 5₮
0
4: 5 кг, 7₮
0
W = 7

Үүргэвчинд 7 кг л багтана. Зүйл бүрийг ганц л удаа авч болно. Нийт үнийг хамгийн их болгоё. State: dp[i][j] нь эхний i зүйлээс сонгоод j кг даацад багтаах хамгийн их үнэ.

Алхам 1 / 30
Хурд
  • Бөглөж буй нүд
  • Transition-д уншиж буй нүд
  • Бөглөсөн
  • 0: зүйлгүй эсвэл даацгүй
  • Хариу ба авсан зүйлс
Слайд 1 / 6

Үүргэвч

Үүргэвчинд 7 кг л багтана. Дөрвөн зүйлээс алийг нь авбал нийт үнэ хамгийн их болох вэ? Зүйл бүрийг авах эсвэл авахгүй, 0 эсвэл 1. Тиймээс нэр нь 0/1 Knapsack.

knapsack-01.cpp
#include <bits/stdc++.h>
using namespace std;
int n, W, w[105], v[105], dp[105][10005];
int main() {
cin >> n >> W;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (w[i] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
cout << dp[n][W] << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Зүйл бүрийг авах эсвэл авахгүй гэсэн хоёр сонголттой бодлогыг хүснэгтээр бодно. Хоёр хэмжээст DP-гийн сонгодог жишээ. HackerRank дээрх "Knapsack" бодлого бол нэг зүйлийг олон удаа авч болох хувилбар.

Яаж ажилладаг вэ?

1. State: dp[i][j] нь эхний i зүйлээс сонгоод j кг даацад багтаах хамгийн их үнэ. Мөр 0 ба багана 0 бүгд 0. 2. i-р зүйл (жин w[i], үнэ v[i]) багтахгүй бол (w[i] > j): dp[i][j] = dp[i − 1][j]. 3. Transition: багтвал хоёр сонголтын ихийг авна. Авахгүй бол dp[i − 1][j], авбал dp[i − 1][j − w[i]] + v[i]. 4. Хариу нь dp[n][W]. Оролт: эхний мөрөнд n W, дараагийн n мөрөнд w[i] v[i].

Яагаад зөв, хэр хурдан бэ?

i-р зүйлийн хувьд хамгийн сайн сонголт түүнийг авсан эсвэл аваагүй байна. Аваагүй бол үлдсэн нь эхний i - 1 зүйлээс j кг-д хийсэн хамгийн сайн сонголт. Авсан бол бусад нь j - w[i] кг-д багтах ёстой. Transition хоёуланг нь шалгадаг тул зөв.

Хүснэгтэд n · W нүд, нүд бүрийг O(1)-д бодно. n = 100, W = 10 000 бол сая нүд, хурдан. Харин W = 10⁹ бол хүснэгт санах ойд багтахгүй, өөр арга хэрэгтэй.

Түгээмэл алдаа

  • w[i] > j шалгалтгүйгээр dp[i - 1][j - w[i]] унших. Сөрөг index болно.
  • 1D хүснэгттэй хувилбарт j-г өсөх дарааллаар явуулах. Тэгвэл нэг зүйлийг олон удаа авчихна. 0/1 бол j буурах дарааллаар явна.
  • Үнийн нийлбэр int-ээс хэтрэх. n = 100, үнэ 10⁹ хүртэл бол long long хэрэгтэй.
  • Хүнд үнэтэй зүйлийг түрүүлж авах Greedy бичих. (3 кг, 5), (3 кг, 5), (4 кг, 7), W = 6 үед Greedy 7 авна, зөв хариу 10.

Хязгаарын тохиолдол

  • Ямар ч зүйл багтахгүй (бүгд W-ээс хүнд): бүх мөр нь дээрхээ хуулна, хариу 0.
  • Бүх зүйл нийлээд багтана: хариу нь бүх үнийн нийлбэр.
  • W = 0: багана 0 л үлдэнэ, хариу 0.

Өөрийгөө шалга

  1. Жишээний (1 кг, 1), (3 кг, 4), (4 кг, 5), (5 кг, 7), W = 7 үед хариу хэд вэ?

    Хариу харах

    9: 3 кг ба 4 кг-ийн зүйлс, 4 + 5.

  2. (3 кг, 5), (3 кг, 5), (4 кг, 7), W = 6 бол хариу хэд вэ?

    Хариу харах

    10: хоёр 3 кг-ийн зүйл. Хамгийн үнэтэй 7-г авбал өөр юу ч багтахгүй.

  3. n = 100, W = 10 000 бол хүснэгтэд ойролцоогоор хэдэн нүд байх вэ?

    Хариу харах

    101 · 10 001, сая орчим.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.(1 кг, 2), (2 кг, 3), (3 кг, 4), W = 4 үед хүснэгтийг мөр мөрөөр бөглө.

    Hint харах

    Мөр бүрт багана 1-ээс 4 хүртэл. Багтвал авах, авахгүй хоёрын ихийг ав.

    Хариу ба тайлбар

    Мөр 1: 2 2 2 2. Мөр 2: 2 3 5 5. Мөр 3: 2 3 5 6. Хариу 6: 1 кг ба 3 кг-ийн зүйлс.

  2. 2.Санах ойг O(W) болгож, нэг мөртэй dp[j] ашигла.

    Hint харах

    dp[j - w[i]] нь өмнөх мөрийн утга байх ёстой. j-г аль чиглэлд явуулбал тэр утга өөрчлөгдөөгүй байх вэ?

    Хариу ба тайлбар

    for (j = W; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]); j буурах тул dp[j - w[i]] хараахан энэ мөрөнд шинэчлэгдээгүй.

  3. 3.Зүйл бүрийг хэдэн ч удаа авч болдог бол (unbounded knapsack) юу өөрчлөх вэ?

    Hint харах

    Өмнөх дадлагын j-ийн чиглэлийг бод.

    Хариу ба тайлбар

    j-г өсөх дарааллаар явуулна: for (j = w[i]; j <= W; j++). (2 кг, 3), (3 кг, 4), (4 кг, 5), W = 6 үед 0/1 хариу 8, unbounded хариу 9 (2 кг-ийг гурван удаа).

Жишээ

Оролт

4 7
1 1
3 4
4 5
5 7

Гаралт

9

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.