Số lượng tối đa bằng cách hoán đổi

Trong bài toán này, một chuỗi số nguyên dương được đưa ra, chúng ta phải tìm hoán vị có giá trị lớn nhất bằng cách hoán đổi các chữ số 'k lần, vào các vị trí khác nhau.

Chúng ta sẽ giải quyết vấn đề này bằng cách chọn một chữ số và hoán đổi nó với các chữ số theo sau nó lần lượt để tìm một số lớn nhất. Chúng tôi lặp lại quy trình k lần. Chiến lược backtracking đang hoạt động ở đây vì khi chúng tôi tìm thấy một số không lớn hơn giá trị trước đó, chúng tôi quay trở lại giá trị cũ và kiểm tra lại.

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

Input:
A number of multiple digits.
The input is: 129814999
Output:
The maximum value from these digits by swapping them.
The output is: 999984211

Thuật toán

maxNum(number, swaps, maxNumber)

Đầu vào - Số dưới dạng một chuỗi, số lần hoán đổi và chuỗi Số tối đa.

Đầu ra - Cập nhật maxNumber để nhận giá trị lớn nhất.

Begin
   if swaps = 0, then
      return
   n := number of digits in the number
   for i := 0 to n-2, do
      for j := i+1 to n-1, do
         if number[i] < number[j], then
            exchange number[i] and number[j]
            if number is greater than maxNumber, then
               maxNumber := number
            maxNum(number, swaps-1, maxNumber)
            exchange number[i] and number[j] again for backtrack
      done
   done
End

Ví dụ

#include <iostream>
using namespace std;

void maxNum(string str, int swaps, string &max) {
   if(swaps == 0)        //when no swaps are left
      return;
   int n = str.length();

   for (int i = 0; i < n - 1; i++) {        //for every digits og given number
      for (int j = i + 1; j < n; j++) {
         if (str[i] < str[j]) {             //when ith number smaller than jth number
            swap(str[i], str[j]);
            if (str.compare(max) > 0)      //when current number is greater, make it maximum
               max = str;
            maxNum(str, swaps - 1, max);   //go for next swaps
            swap(str[i], str[j]);        //when it fails, reverse the swapping
         }
      }
   }
}

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

Đầu ra

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