Bob's Sale (pemesanan ulang pasangan dengan kendala untuk meminimalkan jumlah produk)

Saya telah menanyakan pertanyaan ini pada Stack Overflow beberapa waktu lalu: Masalah: Penjualan Bob . Seseorang menyarankan untuk mengirim pertanyaan di sini juga.

Seseorang telah mengajukan pertanyaan terkait dengan masalah ini di sini - Berat minimum hutan hujan dari kardinalitas yang diberikan - tetapi sejauh yang saya mengerti itu tidak membantu saya dengan masalah saya. Jawaban dengan nilai tertinggi di StackOverflow juga patut dilihat.

Inilah salinan kata demi kata dari pertanyaan StackOverflow saya. Ini mungkin tidak diformulasikan secara memadai untuk situs ini (heck, saya merasa tidak cukup hanya bertanya di sini), jadi silakan mengeditnya:

Catatan: ini adalah penulisan ulang abstrak dari masalah kehidupan nyata terkait pemesanan catatan dalam file SWF. Sebuah solusi akan membantu saya meningkatkan aplikasi open-source.

Bob memiliki toko, dan ingin melakukan penjualan. Tokonya membawa sejumlah produk, dan dia memiliki jumlah unit integer tertentu dari setiap produk dalam stok. Dia juga memiliki sejumlah label harga yang dipasang di rak (sebanyak jumlah produk), dengan harga sudah tercetak di atasnya. Dia dapat menempatkan label harga pada produk apa pun (harga kesatuan untuk satu item untuk seluruh stok produk itu), namun beberapa produk memiliki batasan tambahan - produk semacam itu mungkin tidak lebih murah daripada produk lain tertentu.

Anda harus menemukan cara mengatur label harga, sehingga biaya total semua barang Bob serendah mungkin. Total biaya adalah jumlah dari label harga masing-masing produk yang dikalikan dengan jumlah produk dalam stok.

Diberikan:

• N - jumlah produk dan label harga
• S _i , 0≤ i <N - jumlah dalam stok produk dengan indeks i (integer)
• P _j , 0≤ j <N - harga pada label harga dengan indeks j (integer)
• K - jumlah pasangan kendala tambahan
• A _k , B _k , 0≤ k <K - indeks produk untuk kendala tambahan
  • Setiap indeks produk dapat muncul paling banyak sekali dalam B. Dengan demikian, grafik yang dibentuk oleh daftar kedekatan ini sebenarnya adalah seperangkat pohon diarahkan.

Program harus menemukan:

• M _i , 0≤ i <N - pemetaan dari indeks produk ke indeks label harga (P _{M i} adalah harga produk i )

Untuk memenuhi persyaratan:

1. P _{M A k} ≤ P _{M B k} , untuk 0≤ k <K
2. Σ (S _i × P _{M i} ) untuk 0≤ i <N minimal

Perhatikan bahwa jika tidak untuk kondisi pertama, solusinya hanya akan menyortir label berdasarkan harga dan produk berdasarkan kuantitas, dan mencocokkan keduanya secara langsung.

Nilai tipikal untuk input adalah N, K <10000. Dalam masalah kehidupan nyata, hanya ada beberapa label harga yang berbeda (1,2,3,4).

Inilah salah satu contoh mengapa solusi paling sederhana (termasuk jenis topologi) tidak berfungsi:

$\$$$\$$

Solusi optimal adalah:

Price, $   1  2  3  4  5  6  7  8  9 10
Qty        9  8  7  6  1 10  5  4  3  2

$\$$

Saya juga memposting ini pada pertanyaan awal Anda di Stack Overflow:

Masalahnya adalah NP-lengkap untuk kasus umum. Ini dapat ditunjukkan melalui pengurangan 3-partisi (yang merupakan versi NP-complete bin packing yang masih kuat).

Misalkan w ₁ , ..., w _n menjadi bobot objek instance 3-partisi, misalkan b menjadi ukuran bin, dan k = n / 3 jumlah nampan yang diizinkan untuk diisi. Oleh karena itu, ada 3 partisi jika objek dapat dipartisi sedemikian sehingga ada 3 objek per bin.

Untuk pengurangan, kami menetapkan N = kb dan masing-masing bin diwakili oleh b label harga dari harga yang sama (memikirkan P _i meningkat setiap b label th). Mari t _i , 1≤ i ≤ k , menjadi harga label sesuai dengan i bin th. Untuk setiap w _i kami memiliki satu produk S _j dari kuantitas w _i + 1 (sebut saja ini produk root dari w _i ) dan produk w _i - 1 lainnya dari kuantitas 1 yang diharuskan lebih murah daripada S _j (sebut ini produk cuti).

Untuk t _i = (2b + 1) ⁱ , 1≤ i ≤ k , ada 3-partisi jika dan hanya jika Bob dapat menjual untuk 2b Σ _{1≤ i ≤ k} t _i :

• Jika ada solusi untuk 3-partisi, maka semua produk b yang sesuai dengan objek w _i , w _j , w _l yang ditugaskan ke bin yang sama dapat dilabeli dengan harga yang sama tanpa melanggar batasan. Dengan demikian, solusi memiliki biaya 2b Σ _{1≤ i ≤ k} t _i (karena jumlah total produk dengan harga t _i adalah 2b ).
  
• Pertimbangkan solusi optimal Penjualan Bob. Pertama-tama amati bahwa dalam solusi apa pun ada lebih dari 3 produk root dengan label harga yang sama, untuk setiap produk root yang "terlalu banyak" ada label harga lebih murah yang menempel pada kurang dari 3 produk root. Ini lebih buruk daripada solusi apa pun jika ada tepat 3 produk root per label harga (jika ada).
  Sekarang masih bisa ada solusi dari Penjualan Bob dengan 3 label root per harga, tetapi produk cuti mereka tidak memakai label harga yang sama (nampan semacam mengalir). Mengatakan yang paling harga mahal label tag produk akar w _i yang memiliki produk cuti tagged lebih murah. Ini menyiratkan bahwa 3 label root w _i , w _j , w _l ditandai dengan harga paling mahal tidak menambahkan hingga b . Karenanya, total biaya produk yang ditandai dengan harga ini setidaknya 2b +1 .
  Oleh karena itu, solusi semacam itu memiliki biaya t _k (2b + 1) + beberapa biaya penugasan lainnya. Karena biaya yang optimal untuk 3-partisi ada adalah 2b Σ _{1≤ i ≤ k} t _i , kita harus menunjukkan bahwa kasus hanya dianggap lebih buruk. Ini adalah kasus jika t _k > 2b Σ _{1≤ i ≤ k-1} t _i (perhatikan bahwa k-1 dalam jumlah sekarang). Pengaturan t _i= (2b +1) ⁱ , 1≤ i ≤ k , ini masalahnya. Ini juga berlaku jika bukan label harga yang paling mahal adalah yang "buruk", tetapi yang lainnya.

Jadi, ini adalah bagian yang merusak ;-) Namun, jika jumlah label harga yang berbeda adalah konstan, Anda dapat menggunakan pemrograman dinamis untuk menyelesaikannya dalam waktu polinomial.

Ini adalah tindak lanjut dari jawaban Gero . Idenya adalah untuk memodifikasi konstruksinya untuk menunjukkan kekerasan-NP yang kuat.

$t_i=(2b+1)^i$$t_i=i$$P=2b\sum_{1\leq i \leq k} t_i$

$w_i-1$$P$$P$

Oleh karena itu, hanya mungkin untuk mencapai hadiah yang diklaim, jika semua produk daun memiliki hadiah yang sama dengan produk dasar mereka, yang berarti ada 3 partisi.

$k$$f(k)\cdot n^{O(1)}$$n^{O(k)}$

Juga lintas-posting ke pertanyaan stack-overflow asli.

Ini terdengar seperti pertanyaan teori permainan. Dalam hal ini, solusi brute-force yang sangat sederhana adalah:

Mari kita asumsikan kendala mewakili beberapa invarian formulir

S-> AkSBk | AkBkS | SAkBk

Solusinya adalah dengan terus menambahkan kendala terlebih dahulu, dan kemudian elemen. Misalnya: Katakanlah n = 10 dan ada 2 kendala, A1B1 dan A2B2. Lalu, ada tiga anak ke simpul akar (level 2). Masing-masing dari 3 node ini akan memiliki 7 anak level 3, masing-masing 21 memiliki 6 di level 4, dll. Pada dasarnya Anda menjalankan semua kombinasi yang mungkin.

                A1B1 --- Level 1 
               / | \
              / | \
             / | \
            / | \
    A1A2B2A1 A1B1A2B2 A2B2A1B1 --- Level 2

dan menumbuhkan pohon. Meskipun pada awalnya itu tampak seperti solusi yang mengerikan, saya merasa Anda bisa meninggalkan mengejar daun yang sangat mahal dengan menggunakan beberapa heuristik dan pemangkasan ...