Saya tahu bahwa masalah Knapsack 2D dan 3D adalah NPC, tetapi apakah ada cara untuk menyelesaikannya dalam waktu yang wajar jika instansnya tidak terlalu rumit? Akankah pemrograman dinamis bekerja?
Dengan 2D (3D) Knapsack Maksudku, aku punya kotak (kubus) dan aku punya daftar objek, semua data dalam sentimeter dan paling banyak 20m.
Jawaban:
Knapsack dapat diselesaikan dengan pemrograman dinamis dalam pseudo-polynomial time dengan jumlah objek dan ukuran knapsack. Jadi, selama wadah Anda kecil (secara numerik), Anda dapat menyelesaikan masalah secara efisien. Perhatikan bahwa Anda dapat menyesuaikan dengan mengubah resolusi; tidak perlu mengukur wadah pengiriman ke µm, tetapi meter mungkin kasar (tergantung pada objek Anda).O(nW) n W W
Knapsack juga dapat didekati secara sewenang-wenang dengan baik dalam waktu polinomial (lihat skema aproksimasi waktu polinomial ).
Namun, Knapsack hanya mempertimbangkan nomor pas ke nomor lain; tidak peduli tentang geometri. Jika Anda perlu "puzzle", Anda perlu masalah lain; mempertimbangkan Tetris, ini mungkin jauh lebih sulit daripada Knapsack .
sumber
Keserakahan akan selalu menemukan solusi yang masuk akal, tetapi belum tentu yang optimal. Sederhananya objek terbesar yang akan pas setiap kali di ransel. Berhenti ketika tidak ada lagi benda yang cocok.
sumber