Isi kandungan:
Definisi - Apakah maksud Knapsack Problem?
Masalah knapsack adalah masalah pengoptimalan yang digunakan untuk menggambarkan masalah dan penyelesaian. Ia memperoleh namanya dari senario di mana seseorang dikekang dalam jumlah item yang boleh diletakkan di dalam knapsack bersaiz tetap. Memandangkan satu set item dengan berat dan nilai tertentu, matlamatnya adalah untuk mendapatkan sebanyak nilai ke dalam knapsack yang mungkin memandangkan kekangan berat knapsack.
Techopedia menerangkan Masalah Knapsack
Masalah knapsack adalah contoh masalah pengoptimalan combinational, topik dalam matematik dan sains komputer tentang mencari objek optimal antara satu set objek. Ini adalah masalah yang telah dikaji selama lebih dari satu abad dan merupakan masalah contoh yang biasa digunakan dalam pengoptimalan combinatorial, di mana terdapat keperluan objek optimum atau penyelesaian terhingga di mana pencarian menyeluruh tidak mungkin. Masalahnya boleh dijumpai senario dunia sebenar seperti peruntukan sumber dalam kekangan kewangan atau bahkan dalam memilih pelaburan dan portfolio. Ia juga boleh didapati dalam bidang seperti matematik yang diterapkan, teori kerumitan, kriptografi, gabungan dan sains komputer. Ia dengan mudah merupakan masalah yang paling penting dalam logistik.
Dalam masalah knapsack, item yang diberikan mempunyai dua atribut sekurang-kurangnya - nilai item, yang mempengaruhi kepentingannya, dan berat atau kelantangan item, yang merupakan aspek batasannya. Memandangkan pencarian menyeluruh tidak mungkin, seseorang boleh memecahkan masalah menjadi sub-masalah kecil dan menjalankannya secara rekursif. Ini dipanggil sub struktur yang optimum. Ini hanya berkaitan dengan satu item pada satu masa dan berat semasa masih terdapat di knapsack. Penyelesaian masalah hanya perlu memutuskan sama ada untuk mengambil item atau tidak berdasarkan berat yang masih boleh diterima. Walau bagaimanapun, jika ia merupakan program, pengiraan semula tidak bebas dan akan menyebabkan masalah. Di sinilah teknik pengaturcaraan dinamik boleh digunakan. Penyelesaian kepada setiap sub-masalah disimpan supaya pengiraan hanya perlu berlaku sekali.
