Masalah ransel pecahan dalam C++ mengacu pada mengidentifikasi cara mengisi tas dengan barang-barang dengan berat dan keuntungan tertentu sedemikian rupa sehingga tas tersebut berisi nilai maksimum tanpa melebihi batas maksimum.
Cara Menyelesaikan Masalah Knapsack Pecahan di C++
Diberikan sekumpulan barang, masing-masing dengan berat dan keuntungan tertentu, tentukan setiap jumlah barang dalam kombinasi sedemikian rupa sehingga berat total barang kurang dari batas maksimum kantong, tetapi nilainya harus dijaga sebesar mungkin.
Algoritma Untuk Mengimplementasikan Masalah Knapsack Pecahan
Cara kerja algoritma Knapsack dapat dipahami melalui poin-poin berikut:
- Ambil dua susunan bobot dan untung.
- Tetapkan nilai karung maksimum ke W.
- Tentukan massa jenis dengan mengambil rasio kedua parameter.
- Urutkan item dalam urutan kepadatan yang menurun.
- Tambahkan nilai hingga <=W.
Pendekatan Serakah untuk Memecahkan Masalah Knapsack Pecahan
Pendekatan serakah bertujuan untuk membuat pilihan ideal pada setiap langkah, yang pada akhirnya mengarah pada solusi ideal. Ini memecahkan masalah langkah demi langkah yang mengarah pada kesimpulan, bukan hanya menyimpulkan hasil pada akhirnya. Ini adalah kode sumber untuk mengimplementasikan solusi masalah ransel pecahan di C++:
#termasuk
menggunakan ruang nama std ;
struktur Obyek {
ke dalam nilai, berat ;
Obyek ( ke dalam nilai, ke dalam berat )
: nilai ( nilai ) , berat ( berat )
{
}
} ;
bodoh cmp ( struktur Objek x, struktur Objek y )
{
dobel A1 = ( dobel ) X. nilai / X. berat ;
dobel A2 = ( dobel ) Dan. nilai / Dan. berat ;
kembali A1 > A2 ;
}
dobel pecahanKnapsack ( struktur Arr objek [ ] ,
ke dalam DI DALAM, ke dalam ukuran )
{
menyortir ( arr, arr + ukuran, cmp ) ;
ke dalam berat saat ini = 0 ;
dobel nilai akhir = 0,0 ;
untuk ( ke dalam Saya = 0 ; Saya < ukuran ; Saya ++ ) {
jika ( berat saat ini + arr [ Saya ] . berat <= DI DALAM ) {
berat saat ini + = arr [ Saya ] . berat ;
nilai akhir + = arr [ Saya ] . nilai ;
}
kalau tidak {
ke dalam tetap = DI DALAM - berat saat ini ;
nilai akhir + = arr [ Saya ] . nilai
* ( ( dobel ) tetap
/ arr [ Saya ] . berat ) ;
merusak ;
}
}
kembali nilai akhir ;
}
ke dalam di dalam = 60 ;
Arr objek [ ] = { { 100 , dua puluh } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
ke dalam ukuran = ukuran dari ( arr ) / ukuran dari ( arr [ 0 ] ) ;
cout << 'Keuntungan maksimum ='
<< pecahanKnapsack ( arr, v, ukuran ) ;
kembali 0 ;
}
Dalam kode ini, struktur objek didefinisikan yang memiliki nilai bobot dan keuntungan yang tersimpan di dalamnya. Bool cmp() digunakan untuk membuat perbandingan antara dua benda berdasarkan rasio berat dan nilai dua benda. Array disusun dalam urutan menurun dan nilainya terus bertambah hingga mencapai maksimum. Jika nilai saat ini diperbolehkan dan dalam batas, maka ditambahkan, jika tidak, rasio yang dikurangi akan ditambahkan ke kantong. Besaran bobot dan nilai diinput pada kode utama dan keuntungan maksimal dicetak pada output.
Keuntungan maksimal yang disimpan dalam snack adalah 580.
Kesimpulan
Masalah ransel pecahan dalam C++ mengacu pada mengidentifikasi cara mengisi tas dengan barang-barang dengan berat dan keuntungan tertentu sedemikian rupa sehingga tas tersebut berisi nilai maksimum tanpa melebihi batas maksimum. Hal ini dapat dicapai dengan pendekatan serakah yang bertujuan untuk membuat pilihan ideal pada setiap langkah, yang pada akhirnya mengarah pada solusi ideal.