Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Bài 9. Sắp xếp hàng ngoài cảng - Nguyên lý thứ tự

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Bài 9. Sắp xếp hàng ngoài cảng - Nguyên lý thứ tự

Bài gửi  admin on Thu Jan 06, 2011 5:10 pm

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];

    Hôm nay: Mon Oct 15, 2018 7:38 pm