Bài toán về chiếc ba lô phân số trong C++ đề cập đến việc xác định cách lấp đầy một túi với các vật phẩm có trọng lượng và lợi nhuận nhất định theo cách sao cho túi chứa giá trị tối đa mà không vượt quá giới hạn tối đa.
Cách giải bài toán về chiếc ba lô phân số trong C++
Cho một bộ vật phẩm, mỗi vật phẩm có trọng lượng và lợi nhuận cho trước, xác định từng số lượng vật phẩm trong tổ hợp sao cho tổng trọng lượng các vật phẩm nhỏ hơn giới hạn tối đa của túi nhưng giá trị phải được giữ càng lớn càng tốt.
Thuật toán thực hiện bài toán ba lô phân số
Hoạt động của thuật toán Knapsack có thể được hiểu qua các điểm sau:
- Lấy hai mảng trọng lượng và lợi nhuận.
- Đặt giá trị bao tải tối đa thành W.
- Xác định mật độ bằng cách lấy tỷ lệ của cả hai tham số.
- Sắp xếp các mục theo thứ tự mật độ giảm dần.
- Cộng các giá trị cho đến khi nó <=W.
Phương pháp tham lam để giải bài toán chiếc ba lô phân số
Cách tiếp cận tham lam nhằm mục đích đưa ra những lựa chọn lý tưởng ở mỗi bước, dẫn đến giải pháp lý tưởng ở cuối. Nó giải quyết vấn đề từng bước dẫn đến kết luận thay vì chỉ kết luận kết quả cuối cùng. Đây là mã nguồn để triển khai giải pháp cho bài toán chiếc ba lô phân số trong C++:
#include
sử dụng không gian tên tiêu chuẩn ;
cấu trúc Sự vật {
int Trọng lượng giá trị ;
Sự vật ( int giá trị, int cân nặng )
: giá trị ( giá trị ) , cân nặng ( cân nặng )
{
}
} ;
bool cmp ( cấu trúc đối tượng x, cấu trúc Đối tượng y )
{
gấp đôi A1 = ( gấp đôi ) x. giá trị / x. cân nặng ;
gấp đôi A2 = ( gấp đôi ) Và. giá trị / Và. cân nặng ;
trở lại A1 > A2 ;
}
gấp đôi phân sốKnapsack ( cấu trúc Mảng đối tượng [ ] ,
int TRONG, int kích cỡ )
{
loại ( ừm, ừm + kích thước, cmp ) ;
int congTrọng lượng = 0 ;
gấp đôi giá trị cuối cùng = 0,0 ;
vì ( int Tôi = 0 ; Tôi < kích cỡ ; Tôi ++ ) {
nếu như ( congTrọng lượng + arr [ Tôi ] . cân nặng <= TRONG ) {
congTrọng lượng + = arr [ Tôi ] . cân nặng ;
giá trị cuối cùng + = arr [ Tôi ] . giá trị ;
}
khác {
int duy trì = TRONG - congTrọng lượng ;
giá trị cuối cùng + = arr [ Tôi ] . giá trị
* ( ( gấp đôi ) duy trì
/ arr [ Tôi ] . cân nặng ) ;
phá vỡ ;
}
}
trở lại giá trị cuối cùng ;
}
int TRONG = 60 ;
Mảng đối tượng [ ] = { { 100 , hai mươi } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int kích cỡ = kích thước của ( arr ) / kích thước của ( arr [ 0 ] ) ;
cout << 'Lợi nhuận tối đa ='
<< phân sốKnapsack ( mảng, v, kích thước ) ;
trở lại 0 ;
}
Trong mã này, một cấu trúc đối tượng được xác định có các giá trị trọng số và lợi nhuận được lưu trữ trong đó. Bool cmp() được sử dụng để so sánh giữa hai đối tượng trên cơ sở tỷ lệ trọng lượng và giá trị của hai đối tượng. Mảng được sắp xếp theo thứ tự giảm dần và giá trị tiếp tục tăng cho đến khi đạt mức tối đa. Nếu giá trị hiện tại cho phép và nằm trong giới hạn thì giá trị đó sẽ được thêm vào, nếu không thì tỷ lệ giảm của nó sẽ được thêm vào túi. Độ lớn của trọng lượng và giá trị được nhập vào mã chính và lợi nhuận tối đa được in trên đầu ra.
Lợi nhuận tối đa được tích trữ trong bữa ăn nhẹ là 580.
Phần kết luận
Bài toán về chiếc ba lô phân số trong C++ đề cập đến việc xác định cách lấp đầy một túi với các vật phẩm có trọng lượng và lợi nhuận nhất định theo cách sao cho túi chứa giá trị tối đa mà không vượt quá giới hạn tối đa. Điều này có thể đạt được bằng cách tiếp cận tham lam nhằm đưa ra những lựa chọn lý tưởng ở mỗi bước, dẫn đến giải pháp lý tưởng ở cuối.