---
# System prepended metadata

title: Giới thiệu thuật toán tham lam và kiểu dữ liệu 'vector' trong C++
tags: [C++theory]

---



# Giới thiệu về Thuật toán Tham lam trong C++

Thuật toán Tham lam (Greedy Algorithm) là một trong những thuật toán cơ bản và hiệu quả trong lĩnh vực lập trình và giải quyết các bài toán tối ưu. Đặc trưng của thuật toán Tham lam là luôn lựa chọn giá trị tốt nhất tại mỗi bước để tiến tới giải pháp tối ưu toàn cục. Điều này có nghĩa là tại mỗi bước, thuật toán luôn chọn hành động tốt nhất tại thời điểm đó, không quan tâm đến tác động của hành động đó vào tương lai.

## Cách thức hoạt động của Thuật toán Tham lam

Thuật toán Tham lam thường hoạt động theo cách sau:

1. Xác định cấu trúc của bài toán: Để áp dụng thuật toán Tham lam, ta cần xác định rõ cấu trúc của bài toán và các điều kiện giới hạn.

2. Xác định hàm mục tiêu: Ta cần xác định một hàm mục tiêu để đánh giá độ tốt/xấu của mỗi lựa chọn trong bài toán.

3. Xác định bước tham lam: Tại mỗi bước, ta lựa chọn hành động tốt nhất dựa trên hàm mục tiêu đã xác định ở bước trước.

4. Kiểm tra điều kiện dừng: Thuật toán tiếp tục lựa chọn bước tham lam cho đến khi đạt được kết quả tối ưu hoặc không thể lựa chọn thêm bước nào mà vẫn đảm bảo kết quả tối ưu.

## Ví dụ về Thuật toán Tham lam

Ví dụ cụ thể về Thuật toán Tham lam là bài toán "Tìm tổng nhỏ nhất của số tờ tiền để trả đúng một số tiền nào đó". Giả sử ta có một tập hợp các tờ tiền có mệnh giá là {1, 5, 10, 20, 50, 100} và muốn trả đúng số tiền là 175. Ta cần tìm cách trả sao cho tổng số tờ tiền là nhỏ nhất.

Giải pháp của thuật toán Tham lam là chọn tờ tiền có mệnh giá lớn nhất nhưng vẫn nhỏ hơn hoặc bằng số tiền cần trả, rồi tiếp tục lựa chọn tờ tiền tiếp theo cho đến khi tổng số tờ tiền đạt được số tiền cần trả.

# Giới thiệu về Vector trong C++

Trong ngôn ngữ lập trình C++, `vector` là một trong những cấu trúc dữ liệu linh hoạt và mạnh mẽ nhất được cung cấp sẵn trong thư viện chuẩn (`<vector>`). Vector được sử dụng để lưu trữ và quản lý một dãy các phần tử có cùng kiểu dữ liệu, giúp ta dễ dàng thao tác và điều chỉnh số lượng phần tử trong mảng.

## Khởi tạo và sử dụng Vector

Để sử dụng `vector` trong C++, ta cần bao gồm thư viện `<vector>` vào chương trình. Cú pháp khai báo một vector như sau:

```cpp
#include <vector>

std::vector<kiểu_dữ_liệu> tên_vector;
```

Ví dụ:

```cpp
#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers; // Khai báo vector lưu trữ các số nguyên

    // Thêm phần tử vào vector
    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);

    // Truy cập phần tử trong vector
    std::cout << "Phan tu tai vi tri thu 1: " << numbers[0] << std::endl;
    std::cout << "Phan tu tai vi tri thu 2: " << numbers[1] << std::endl;

    // Sử dụng vòng lặp để duyệt qua tất cả các phần tử trong vector
    std::cout << "Cac phan tu trong vector: ";
    for (int i = 0; i < numbers.size(); i++) {
        std::cout << numbers[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}
```

Kết quả đầu ra:

```
Phan tu tai vi tri thu 1: 10
Phan tu tai vi tri thu 2: 20
Cac phan tu trong vector: 10 20 30
```

## Các phương thức quan trọng của Vector

- `push_back(value)`: Thêm phần tử `value` vào cuối vector.
- `pop_back()`: Xóa phần tử cuối cùng khỏi vector.
- `size()`: Trả về số lượng phần tử trong vector.
- `clear()`: Xóa tất cả các phần tử trong vector.
- `empty()`: Kiểm tra vector có rỗng hay không.
- `resize(newSize)`: Thay đổi kích thước của vector thành `newSize`.
- `front()`: Trả về giá trị của phần tử đầu tiên trong vector.
- `back()`: Trả về giá trị của phần tử cuối cùng trong vector.
- `at(index)`: Trả về giá trị của phần tử tại vị trí `index`.