Uploaded by

Tuấn Hoàng

0% found this document useful (0 votes)

315 views

39 pages

Original Title

4-Optimization

Copyright

© © All Rights Reserved

Available Formats

PDF, TXT or read online from Scribd

Share this document

Did you find this document useful?

Is this content inappropriate?

0% found this document useful (0 votes)

315 views39 pages

4 Optimization

Uploaded by

Tuấn Hoàng

Trong siêu thị có n gói hàng (n <= 100), gói hàng thứ i có trọng lượng là Wi <= 100 và trị giá Vi <= 100. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M ( M <= 100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất.

Input: file văn bản BAG.INP

• Dòng 1: Chứa hai số n, M cách nhau ít nhất một dấu cách
• n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương Wi, Vi cách nhau ít nhất một dấu cách

Output: file văn bản BAG.OUT

• Dòng 1: Ghi giá trị lớn nhất tên trộm có thể lấy
• Dòng 2: Ghi chỉ số những gói bị lấy

BAG.INP

BAG.OUT

5

11

11

3

3

5 2 1

4

4

5

4

9

10

4

4

Cách giải:

Nếu gọi F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các gói {1, 2, …, i} với giới hạn trọng lượng j, thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F[n, M].

3.2.1. Công thức truy hồi tính F[i, j].

Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1, 2, …,i - 1, i} để có giá trị lớn nhất sẽ có hai khả năng:

• Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể bằng cách chọn trong số các gói {1, 2, …, i - 1} với giới hạn trọng lượng là j, tức là F[i, j] = F[i - 1, j]
• Nếu có chọn gói thứ i (tất nhiên chỉ xét tới trường hợp này khi mà Wi <= j) thì F[i, j] bằng giá trị gói thứ i là Vi cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói {1, 2, …, i - 1} với giới hạn trọng lượng j - Wi. Tức là về mặt giá trị thu được: F[i, j] = Vi + F[i - 1, j - Wi]

Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể, nên F[i, j] sẽ là max trong 2 giá trị thu được ở trên.

3.2.2. Cơ sở quy hoạch động:

Dễ thấy F[0, j] = giá trị lớn nhất có thể bằng cách chọn trong số 0 gói = 0.

3.2.3. Tính bảng phương án:

Bảng phương án F gồm n + 1 dòng, M + 1 cột, trước tiên được điền cơ sở quy hoạch động: Dòng 0 gồm toàn số 0. Sử dụng công thức truy hồi, dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2, v.v… đến khi tính hết dòng n.

3.2.4. Truy vết:

Tính xong bảng phương án thì ta quan tâm đến F[n, M] đó chính là giá trị lớn nhất thu được khi chọn trong cả n gói với giới hạn trọng lượng M. Nếu F[n, M] = F[n - 1, M] thì tức là không chọn gói thứ n, ta truy tiếp F[n - 1, M]. Còn nếu F[n, M] ¹ F[n - 1, M] thì ta thông báo rằng phép chọn tối ưu có chọn gói thứ n và truy tiếp F[n - 1, M - Wn]. Cứ tiếp tục cho tới khi truy lên tới hàng 0 của bảng phương án.

Bài toán xếp ba lô (còn được biết đến với tên gọi bài toán cái túi) là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài toán tương tự thường xuất hiện trong kinh doanh.

Bài toán: Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là m. Vậy vấn đề đặt ra là tên kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được?

Yêu cầu: Hãy xác định tổng giá trị đồ vật lớn nhất mà tên trộm có thể mang đi được.

Dữ liệu: Vào từ tệp văn bản DRSEM.INP gồm:

• Dòng 1: Ghi số nguyên dương n và m (n ≤ 20, m ≤ 109).
• Trong n dòng tiếp theo, dòng thứ i ghi số nguyên dương ai và bi (ai, bi ≤ 109).

Dữ liệu vào đảm bảo có ít nhất một cách chọn đồ vật.

Kết quả: Ghi ra tệp văn bản DRSEM.OUT gồm một dòng duy nhất ghi tổng giá trị đồ vật lớn nhất mà tên trộm có thể mang đi được.

DRSEM.INP

DRSEM.OUT

Giải thích

5 17

5 3

2 4

3 6

6 2

8 5

22

Chọn đồ vật thứ tự 1, 3, 4, 5 có tổng khối lượng là 16 < 17 và tổng giá trị lớn nhất là 22.

Code tham khảo:

include

using namespace std; int max(int x, int y) { return (x > y) ? x : y; } int tromDo(long long m, int a[], int b[], int n) { int i, t; int k[n + 1][m + 1]; for (i = 0; i <= n; i++) {

  for (t = 0; t <= m; t++) {
     if (i == 0 || t == 0)
        k[i][t] = 0;
     else if (b[i - 1] <= t)
        k[i][t] = max(a[i - 1] + k[i - 1][t - b[i - 1]], k[i - 1][t]);
     else
    k[i][t] = k[i - 1][t];
  }

freopen("DRSEM.INP","r",stdin);
freopen("DRSEM.OUT","w",stdout);
int n; long long m;
cin >> n >> m;
int a[n], b[n];
for (int i = 0; i < n; i++) {
  cin >> a[i];
  cin >> b[i];
}

Ngoài cách sử dụng mảng, chúng ta có thể sử dụng Vector để xử lý bài toán trên.

include

include

include

include

using namespace std; struct Item {

int weight;
int value;

vector> dp(n + 1, vector(m + 1, 0));
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        if (items[i - 1].weight <= j) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
        }
        else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}
return dp[n][m];

ifstream inputFile("DRSEM.INP");
ofstream outputFile("DRSEM.OUT");
int n, m;
inputFile >> n >> m;
vector items(n);
for (int i = 0; i < n; i++) {
    inputFile >> items[i].weight >> items[i].value;
}
int maxTotalValue = knapsack(n, m, items);
outputFile << maxTotalValue << endl;
inputFile.close();
outputFile.close();
return 0;

int weight;
int value;

vector> dp(n + 1, vector(m + 1, 0));
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        if (items[i - 1].weight <= j) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
        }
        else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}
return dp[n][m];

ifstream inputFile("DRSEM.INP");
ofstream outputFile("DRSEM.OUT");
int n, m;
inputFile >> n >> m;
vector items(n);
for (int i = 0; i < n; i++) {
    inputFile >> items[i].weight >> items[i].value;
}
int maxTotalValue = knapsack(n, m, items);
outputFile << maxTotalValue << endl;
inputFile.close();
outputFile.close();
return 0;

int weight;
int value;

vector> dp(n + 1, vector(m + 1, 0));
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        if (items[i - 1].weight <= j) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
        }
        else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}
return dp[n][m];

ifstream inputFile("DRSEM.INP");
ofstream outputFile("DRSEM.OUT");
int n, m;
inputFile >> n >> m;
vector items(n);
for (int i = 0; i < n; i++) {
    inputFile >> items[i].weight >> items[i].value;
}
int maxTotalValue = knapsack(n, m, items);
outputFile << maxTotalValue << endl;
inputFile.close();
outputFile.close();
return 0;