SẮP XẾP HÀNG NGOÀI CẢNG


BÀI TOÁN
Có n kiền hàng mỗi kiện hàng có trọng lượng P_i. Sắp xếp các kiện hàng này lên xà lan có trọng tải W sao cho tổng trọng lượng xếp lên xà lan là cao nhất.

PHƯƠNG PHÁP
Sử dụng nguyên lý thứ tự để giải quyết bài toán trên.
1. Sắp xếp các kiên hàng tăng (giảm) theo trọng lượng.
2. Đặt các kiện hàng lên xà lan cho đến khi không còn đặt được nữa. Tức đặt thêm 1 kiên hàng trong tải đặt lên sẻ vượt quá trọng tải của xà lan.

CODE MẪU BẰNG MATHEMATICA 8.0

Code:

NhapKienHang[n_] := Module[{temp, i},
         temp = {};
         i = 0;
         While[i < n,
              w = Input["Nhap trong luong"];
              If[w > 0,
                   temp = Append[temp, w];
                   i++;];
           ];
         Return[temp];
      ];
Clear[P, n, W, i, w];
n = Input["Nhap n"];
P = NhapKienHang[n];
W = Input["Nhap trong tai cua xa lan"];
Print["Danh sach trong luong cua ", n, " kien hang:"];
Print[P];
Print["Xa lan co trong tai: ", W];
P = Sort[P, Greater];
Print["Trong luong duoc sap xep giam dan:"];
Print[P];
w = 0;
i = 1;
While[w + P[[i]] <= W && i ≤ n,
       w += P[[i]];
       i++;
    ];
Print["Trong luong duoc dat len xa lan: ", w];