Temukan urutan panjang maksimal secara bersamaan memenuhi dua kendala pemesanan

Kami diberi himpunan dari Fruits. Setiap Buah memiliki harga dan kandungan vitamin ; kami menghubungkan buah dengan pasangan yang dipesan . Sekarang kita harus mengatur buah-buahan ini sedemikian rupa sehingga daftar yang diurutkan berisi harga dalam urutan menaik dan kandungan vitamin dalam urutan menurun.$F=\{f_1, f_2, f_3, …, f_N\}$$N$$P_i$$V_i$$f_i$$(P_i, V_i)$

Contoh 1 : dan .$N = 4$$F = \{(2, 8), (5, 11), (7, 9), (10, 2)\}$

Jika kita mengatur daftar sedemikian rupa sehingga semua harga dalam urutan naik dan kandungan vitamin dalam urutan menurun, maka daftar yang valid adalah sebagai berikut:

• $[(2, 8)]$
• $[(5, 11)]$
• $[(7, 9)]$
• $[(10, 2)]$
• $[(2, 8), (10, 2)]$
• $[(5, 11), (7, 9)]$
• $[(5, 11), (10, 2)]$
• $[(7, 9), (10, 2)]$
• $[(5, 11), (7, 9), (10, 2)]$

Dari daftar di atas, saya ingin memilih daftar ukuran maksimal. Jika lebih dari satu daftar memiliki ukuran maksimal, kita harus memilih daftar ukuran maksimal dengan jumlah harga paling sedikit. Daftar yang harus dipilih dalam contoh di atas adalah .$\{(5, 11), (7, 9), (10, 2)\}$

Contoh 2 : dan$N = 10$

$$F = \{(99,10),(12,23),(34,4),(10,5),(87,11),(19,10), \\(90,18), (43,90),(13,100),(78,65)\}$$

Jawaban untuk contoh contoh ini adalah .$[(13,100),(43,90),(78,65),(87,11),(99,10)]$

Sampai sekarang, inilah yang telah saya lakukan:

1. Sortir daftar asli dengan urutan harga naik;
2. Temukan semua urutan daftar yang diurutkan;
3. Periksa apakah urutannya valid, dan bandingkan semua urutan yang valid.

Namun, ini membutuhkan waktu yang eksponensial; bagaimana saya bisa menyelesaikan masalah ini dengan lebih efisien?

Solusi pemrograman dinamis akan bekerja di sini, jika kandungan vitamin berasal dari himpunan terbatas (misalnya, bilangan bulat terikat). Pertama, mengurutkan buah-buahan pada kenaikan harga dan dalam kasus itu dua atau lebih buah memiliki harga yang sama, mengurutkannya berdasarkan kandungan vitamin (turun). Sekarang, tentukan sebagai jumlah maksimum buah dalam sublist, yang hanya berisi buah terakhir (dari daftar yang diurutkan), yang memiliki kandungan vitamin paling banyak . dan Menggunakan pemrograman dinamis memberi Anda solusi yang berjalan di$M[f, v]$$f$$v$$M[0, *] = 0$

$$M[f, v] = \begin{cases} \mathrm{max} \{M[f-1, v], 1 + M[f-1, V_f]\} & \text{if \(V_f <= v\)} \\ M[f-1, v] & \text{otherwise} \\ \end{cases}$$ $O(\text{number of fruit} \times \text{possible vitamin values})$ .