Bilinen desen karşı veri setini eşleştirmek için bir temiz, verimli bir yol arıyor

3 Cevap php

PHP5.2 ve MySQL 4.1.22 kullanma

Ben ilk başta, basit çıktı, bir şey rastlamak ettik ama beri basit, temiz bir çözüm getirmedi bana yapmamış olan.

Biz ürün "paketleri" önceden tanımlanmış. Paket 1 o ürünler A, B ve C olabilir. Paket 2 paketleri 3'ten 5 ürün boyutu değişir, vb, içinde A, C, D ve G olabilir.

Şimdi, müşteri bulunan herhangi 10 ürün almak ve "özel" bir paket yapabilirsiniz. Biz zaten önceden tanımlanmış belli paketler var, biz mümkün (nakliye kolaylığı için) daha küçük mevcut paketleri ile özel bir paket oluşturmak istiyorum.

Yani, örneğin, bir müşteri ürün A, B, C, D, E ve F Biz zaten A, B ve C Foo adında içeren önceden tanımlanmış bir paket var bir 'özel paket' yaratmak için seçer. Yani, sipariş sonra Foo, D, E ve F olacaktır

Yakalamak paket en az miktarda ardından ürüne en az miktarda sahip bulunmaktadır. Örneğin:

Özel Paket: A, B, C, D, E, F, G, H, I, J

Önceden belirlenmiş paket (1): A, B, C, D, E

Önceden tanımlı Paketi (2): A, B, C

Önceden tanımlı Paketi (3): D, E, F

Ben sadece büyük maçı alırsak, o zaman ben 1 (5pc) paketi ve 5 ayrı ürün yok. Ne Paketi (2), ne de (3) geri kalan öğeleri ile inşa edilebilir.

Ben derin bakarsanız, ben paketi bina değil (1) yerine (2) paketi oluşturmak olduğunu bulmak ve paketi (3). Hangi Ben 2 paket ve 4 bireysel öğeler (bu buisiness kural daha iyi bir seçim) var demektir.

MySQL kullanarak kulüpler gibi, ben sadece alt (benim gördüğüm kadarıyla) mevcut seçtiğiniz bir tabaka olan kısıtlama altında değilim. Yani bu tür php yapılması gerekir. Ben eşleşmeleri belirlemek için array_intersect () kullanarak baktım, ama önceden tanımlanmış paketlerin sayısının doğrusal büyüdükçe ben buldum her şekilde işleme açısından katlanarak büyür.

Hepimiz o göründüğü kadar basit olmadığını bulundu kolay bir cevap olması gerektiği gibi görünüyordu ederken, yine bir çift diğer kodlayıcı arkadaşlar ve bu koştu. Yani, ben bir güzel makarna sedye olarak buradan sonrası düşündüm. Zaman ayırdığınız için çok şimdiden teşekkürler!

3 Cevap

Sorun genellikle (hesaplama karmaşıklığı açısından konuşma) bir "sert" biridir. Aslında muhtemelen Knapsack problem gibi bu klasik algoritma sorunlarından biri azalttığını kafamın arkasında bazı çan çalar, ama ben buna uygun bir isim takmak olamaz.

Ancak, (onlar sadece 10 ürün seçebilirsiniz) gibi küçük bir problem alanı ile, sadece bir şey kaba kuvvet oldukça hızlı olmalıdır. Birisi özel yapım gönderdiğinde, sadece ardışık tüm olanakları ile saldırı ve bir iyi olduğunu görüyoruz.

Yani, onlar seçtiğiniz bileşenler alacak ve ilk ondan "Paket 1" bileşenleri kaldırmak için çalışın. Bu mümkün değilse, geri kalan bileşenlerini almak ve şimdiye kadar birlikte gitmek gibi bulduğum en iyi çözüm takip edin vs, ondan "Paket 2" nin bileşenlerini almaya çalışın.

O hala yeterince hızlı değil (ama kaç önceden oluşturulmuş paketler bağlı olarak, muhtemelen olacağını düşünüyorum), bazı dynamic programming yöntemler hızlandırmak için geçerli olabilir.

Edited to add:

Olasılıkların sayısı ve ne kadar bu aslında çalıştırmak için gereken bağlı olarak, yukarıda açıklanan kod yazmak istiyorum, ve sonra sadece devam edin ve mümkün olan her kombinasyonu için tüm çözümleri önceden hesaplamak olabilir. Birisi özel bir yapı gönderdiğinde Sonra, sadece yerine sıfırdan her zaman onu hesaplama cevap almak zorunda.

Tüm bunları önceden hesaplamak istemiyorsanız bile, birisi özel bir yapı yok, her zaman, daha sonra gelecekte herkesten aynı özel inşa etmez eğer çözüm yeniden hesaplamak zorunda değilsiniz sonucu depolamak öneririm .

Ben müşteri yardım edelim öneririz. Ürün seçimi ekranlarında, paketlenmiş setleri mevcut olduğunu göstermek ve onları (onesies toplamı özel işlem karşılamak için yeterli olduğunu bu yüzden uygun fiyatlı) kombinasyonlar yapalım.

Biraz daha karmaşık sorunu yapmak için beni bağışlayın. :-)

Eğer olası çözümleri önceden hesaplanması gibi, ya da tüketicilerin aslında önceden tanımlanmış paketler kendilerini seçim olabilir rağmen: ne önceden belirlenmiş bir paket stok artık olur?

Hiçbir çözüm şu anda sipariş tamamlamak için var ne olur? Eğer sipariş kısmını gemi ve eğer öyleyse: Eğer biraz daha sonra bir anda ön tanımlı paketin seçebilirsiniz biliyorum bile tek tek öğeleri içerir?

Ve önceden tanımlanmış paketleri bazı "tercih" atanmış olmayacak gerçekten emin misiniz? Hangi önceden tanımlanmış paket "ABCD" ve önceden tanımlanmış paketleri "ABC" ve "BCD" mevcut sipariş ederken seçmek gibi? Örneğin, önceden tanımlanmış paket "ABC" stokta sık sık olduğunu biliyorum, eğer, o zaman belki "BCD" mümkün tercih edilmesi yapacak.

Yani: belki kolayca yerine otomatikleştirilmiş bir çözüm bulmaya çalışmak yerine, bazı kodlanmış kurallarını değiştirebilirsiniz hangi bazı modelleme kullanmak gerekir. Bu tabii ki PHP kendisi olabilir.

etiketler