Sırt çantası sorunu doğrusal programlama'daki sorunlara benzese de, sırt çantası sorunu neden doğrusal programlama algoritmaları kategorisinin altında yer almıyor.Neden Sırt Çantası problemini çözüyoruz? doğrusal programlama olarak kabul edilmez?
cevap
Sırt çantası tamsayı doğrusal programlama program olarak yazılabilir. Normal doğrusal programlamadan farklı olarak, bu problem, çözümdeki değişkenlerin tamsayı olmasını gerektirir. Tamsayılı doğrusal programlama NP-tamamlanırken, doğrusal programlamanın polinom zamanında çözülebilir olduğu bilinmektedir.
Okuyucu için alıştırma: 3SAT'nin tamsayı doğrusal programlamaya indirgenebileceğini gösterin.
Diğer bilgiler: MAX-3SAT (3SAT'nin varyantı olan memnun sayılar sayısını en üst düzeye çıkarmak istediğimiz) gibi sorunlar için yaklaşık algoritmalar vardır. Öncelikle MAX-3SAT'yi bir tamsayı doğrusal program olarak yazarsınız. Ardından, 'u lineer programa, tamsayı kısıtlamasını kaldırarak gevşetin. Ardından, doğrusal programı polinom zamanında çözersiniz. Son olarak, gerçek x verilen i ∈ [0,1], tamsayı bunları yuvarlak ya da rastgele tam sayı çözüm üretmek y i y i = 1 olasılığı x i olduğu.
Tamamlayıcı olarak: http://stackoverflow.com/q/3128001/395857 –
Genel olarak, verilen NP problemini ILP'ye indirgemek genellikle nispeten kolaydır. –
- 1. Dinamik Programlama ve Sırt Çantası Uygulaması
- 2. Ayrık Sırt Çantası Dinamik Programlama Python3
- 3. Özyinelemeli algoritma kullanarak Sırt Çantası Çözümü
- 4. Rails'te Sırt Çantası benzeri bir Takvim oluşturma
- 5. Ondalık değerleri kullanarak Sırt Çantası Algoritması?
- 6. Doğrusal olmayan programlama kitaplığı C++ 'da
- 7. Neden bu varsayılan kurucu olarak kabul edilmiyor?
- 8. C# için iyi doğrusal programlama kitaplığı?
- 9. C# 0-1 Sırt Çantası Sorunun bilinen toplam sayısı ve sıfır sayısı ile sayısı
- 10. Renderer, inverElementMethod işlevi için renderer2 için bir alternatif olarak kabul edilmez mi?
- 11. 0-1 Tam tersi yanlış yanıt veren sırt çantası (Dynamic Programming)
- 12. Doğrusal svms neden HoG tanımlayıcılarıyla iyi çalışır?
- 13. requestAnimationFrame işlevi neden bir öğeyi argüman olarak kabul ediyor?
- 14. Mercuri alt depoları neden son çare olarak kabul edilir
- 15. JSF neden MVP olarak kabul edilir, MVVM çerçevesi değil
- 16. Görüntü arka planını doğrusal olarak nasıl belirleyebilirim?
- 17. Bu 2 sırt çantası algoritması aynı mı? kapasitesini C olduğu varsayılarak, N ürünlerinin miktarı, w, Benim kod
- 18. Algoritma tasarımı: Çoklu sırt çantası problemine bir çözüm sunabilir misiniz? Ben etkili olanlarla sözde kod çözüm arıyorum
- 19. İsteklere "kabul" başlıklarına uygun olarak kabul edilemez özellikteki yanıtlar
- 20. Kabul tamsayılar ** kwargs ait anahtarları olarak
- 21. bunyan log.child Doğru kullanım çantası?
- 22. Android doğrusal hızlanma doğruluğu
- 23. Neden Stream.flatMap bir koleksiyonu kabul edemiyor?
- 24. sabit nesne var parametre olarak kabul edilemez
- 25. JSON.stringify() Tarih nesneleri neden kabul ediyor?
- 26. Neden wget kullanıcı adımı/şifremi kabul etmiyor?
- 27. Neden kontrolüm klavye girişini kabul etmiyor?
- 28. DisplayMemeberPath neden standart bir özelliği kabul etmiyor?
- 29. Bilgisayar bilimi teorisindeki bu problem tanımı için uygun problem adı/algoritması nedir?
- 30. Kör bir kişi olarak Android için programlama
@ yes123 Doğrusal programlamada, doğrusal değil, zaman kısıtlamalarıdır. – fgb