Số lớn nhất bằng cách hoán đổi (Max Number By Swapping)

Giới thiệu

Cho một chuỗi số nguyên dương, tìm hoán vị có giá trị lớn nhất bằng cách hoán đổi các chữ số tối đa k lần.

Giải bằng backtracking: chọn một chữ số, hoán đổi với các chữ số phía sau lần lượt để tìm số lớn nhất. Lặp lại k lần. Nếu kết quả không tốt hơn, quay lui (backtrack) về trạng thái cũ.

Đầu vào và Đầu ra

Đầu vào: Số nhiều chữ số: 129814999
Đầu ra: Giá trị lớn nhất: 999984211

Thuật toán

maxNum(number, swaps, maxNumber)

Đầu vào: Số dạng chuỗi, số lần hoán đổi, chuỗi maxNumber.

Đầu ra: Cập nhật maxNumber thành giá trị lớn nhất.

Begin
  nếu swaps = 0 thì return
  n := số chữ số
  với i := 0 đến n-2 làm:
    với j := i+1 đến n-1 làm:
      nếu number[i] < number[j] thì
        hoán đổi number[i] và number[j]
        nếu number > maxNumber thì maxNumber := number
        maxNum(number, swaps-1, maxNumber)
        hoán đổi lại number[i] và number[j] (backtrack)
    done
  done
End

Ví dụ (C++)

#include <iostream>
using namespace std;

void maxNum(string str, int swaps, string &max) {
  if(swaps == 0) return;
  int n = str.length();
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      if (str[i] < str[j]) {
        swap(str[i], str[j]);
        if (str.compare(max) > 0) max = str;
        maxNum(str, swaps - 1, max);
        swap(str[i], str[j]);  // backtrack
      }
    }
  }
}

int main() {
  string str = "129814999";
  int swapNumber = 4;
  string max = str;
  maxNum(str, swapNumber, max);
  cout << "The given number is: " << str << endl;
  cout << "The maximum number is: " << max << endl;
}

Kết quả đầu ra

The given number is: 129814999
The maximum number is: 999984211