Bagaimana "masalah memetik Pizza" diselesaikan dengan menggunakan teknik pemrograman dinamis?

9

Masalah memetik pizza Winkler:

  • Pie pizza bundar nirisan, di mana irisan imemiliki luas S_iyaitu area berbeda untuk setiap potongan pie.
  • Pelahap Alice dan Bob bergantian memetik irisan, tetapi tidak sopan untuk membuat beberapa celah dalam pai (menganggapnya tidak diizinkan).
    • Jadi setiap pemakan dibatasi untuk mengambil salah satu dari dua irisan yang berdekatan dengan wilayah terbuka. Alice yang pertama, dan kedua pemakan mencari pie sebanyak mungkin.

Bagaimana algoritma pemrograman dinamis menentukan berapa banyak pie yang dimakan Alice, jika Alice dan Bob bermain sempurna untuk memaksimalkan konsumsi pizza mereka?

Pemahaman saya:

Dalam masalah DP umum, kami maju dengan menemukan sub-masalah yang dapat divisualisasikan menggunakan pohon rekursi atau, lebih ketat, menggunakan DAG. Di sini, saya tidak menemukan petunjuk apa pun untuk menemukan sub-masalah di sini.

Di sini, untuk sekumpulan S_i tertentu, kita perlu memaksimalkan luas irisan yang dimakan oleh Alice. Ini akan tergantung pada memilih permutasi irisan Pizza dari permutasi (n-1). Memilih irisan area maks dari dua opsi yang tersedia di setiap n \ 2 ternyata yang didapatkan Alice, akan memberi kita luas total irisan untuk permutasi. Kita perlu menemukan area slice untuk semua permutasi seperti itu. Dan kemudian maksimum dari ini.

Adakah yang bisa membantu saya untuk maju?

algorithms dynamic-programming Amit Shekhar
sumber

Jawaban:

5

Mulailah dengan mempertimbangkan irisan yang baru saja ditempatkan pada satu baris dan Anda dapat memilih dari salah satu dari kedua ujungnya. Dalam hal ini seandainya itu giliran Anda untuk memilih itu jelas bahwa pizzaAmount(slices)adalah

  1. Jika tidak ada pizza, hasilnya 0
  2. Jika hanya ada satu hasil irisan adalah irisan itu
  3. Jika setidaknya ada dua irisan maka hasilnya adalah:

(menggunakan sintaksis Python)

max(slices[0] + sum(slices[1:]) - pizzaAmount(slices[1:]),
    slices[-1] + sum(slices[:-1]) - pizzaAmount(slices[:-1]))

dengan kata lain Anda harus mempertimbangkan kedua alternatif dan bahwa setelah mengambil potongan Anda, Anda akan mendapatkan semua pizza yang tersisa kecuali hasil dari panggilan rekursif (karena teman Anda akan menggunakan strategi yang sama).

Anda dapat menerapkan ini dengan DP (atau memoizing) karena array memang diperbaiki dan Anda hanya dapat mempertimbangkan sebagai parameter indeks slice pertama dan terakhir.

Untuk menyelesaikan masalah penuh yang asli, Anda hanya perlu mencoba semua irisan sebagai irisan awal dan memilih salah satu yang memaksimalkan hasilnya.

6502
sumber
Terima kasih "6502". Saya dapat memvisualisasikan masalah dengan lebih baik dengan memanfaatkan petunjuk "mempertimbangkan irisan yang ditempatkan pada satu baris dan memilih dari salah satu dari dua ujungnya". Relasi yang diberikan berulang adalah menjaga pilihan optimal oleh lawan, juga. Saya akan segera memposting algoritma formal. Terima kasih kawan !!
Hanya ingin tahu, bagaimana urutan kompleksitas untuk algoritma ini? 0 (n * 2 ^ n)?
@ Akron: Inilah yang akan terjadi tanpa pendekatan pemrograman dinamis atau memoisasi. Namun Anda dapat mengambil keuntungan dari fakta bahwa hasil pizzaAmounttidak hanya bergantung pada apa yang merupakan indeks awal dan berhenti dari irisan yang tersisa dan bukan pada urutan pizza yang telah Anda dan teman Anda makan sehingga Anda dapat menyimpan hasilnya dalam matriks untuk menghindari perhitungan ulang. Oleh karena itu, urutan algoritmanya adalah O (n ** 2).
6502
Jika ada yang masih berjuang untuk mengerti, tautan ini memiliki penjelasan yang sangat bagus.
Amit Shekhar
3

Untuk sebagian pizza, tentukan F(i,j)berapa banyak orang yang dapat makan irisan. Potongan pizza (i,j)adalah:

if i <= j than slices i, i+1, ..., j-1, j
if i > j than slices i, i+1, ..., n-1, n, 1, 2, ..., j-1, j
and we don't define it for whole pizza, abs(i-j) < n-1

Tentukan R(i,j)(berapa banyak yang tersisa untuk orang kedua) sebagai sum(S_x, x in slices(i,j)) - F(i,j).

Dengan:

F(i,i) = S_i,
F(i,j) = max( S_i + R(i+1,j), S_j + R(i,j-1) ),

maksimum yang bisa dimakan Alice dihitung dengan:

max( S_i + F(i+1, (i-1) if i > 1 else n) ).
Sokongan
sumber