Thuật toán thu nhập tối đa

Question

Làm cách nào tôi có thể tính số tiền tối đa kiếm được từ vé m của vé n vé mà giá vé bằng với số lượng vé của cửa sổ đó?

Có 3 cửa sổ vé trong ga đường sắt. Cửa sổ có sẵn (j) vé có sẵn. Giá của một vé bằng với số lượng vé còn lại trong cửa sổ đó tại thời điểm đó. Số tiền tối đa mà nhà ga có thể kiếm được từ việc bán vé m đầu tiên là bao nhiêu?

Ví dụ: nếu chúng tôi có 3 cửa sổ vé, có vé 3, 3, 4 và chúng tôi muốn bán 5 vé. Sau đó:

n = 3, m = 5 
A[3] = {3, 3, 4} 

Số tiền tối đa thu được là 4 + 3 + 3 + 3 + 2 = 15

tôi thấy câu hỏi này trực tuyến và giải pháp của tôi là trước tiên đẩy tất cả vé số để một maxHeap và chạy một cho vòng lặp cho m lần. Mỗi lần chúng ta bật giá trị cao nhất của giá trị tối đa và thêm nó vào tổng số tiền kiếm được và nếu giá trị lớn hơn 1 chúng tôi đẩy (giá trị - 1) vào giá trị tối đa.

Nhưng điều này bằng cách nào đó quá tốn thời gian cho bất kỳ giải pháp nào tốt hơn?

Answer 1

Để giải quyết vấn đề này, chúng ta cần phải thực hiện một quan sát:

• Để có được kết quả tối đa, chúng ta cần phải nhận được nhiều nhất m vé hàng đầu.

Hãy x là số lượng tối đa vé còn lại trong một cửa sổ, vì vậy số tiền một cửa sổ i đóng góp vào tổng thu nhập là

(a(i) + a(i) - 1 + ... + x + 1) = a(i)*(a(i) + 1)/2 - x*(x + 1)/2 

Để tìm x, chúng ta có thể sử dụng tìm kiếm nhị phân

int start = 0; 
int end = maximum number of ticket in one window; 
while(start <= end) 
    int mid = (start + end)/2; 
    for(each window) 
     number of sell ticket += a(i) - mid;//if mid is larger than a(i), just add a zero 
    if(number of sell ticket >= m) 
     increase start; 
    else 
     decrease end; 

Vì vậy, độ phức tạp thời gian là O (n log m) với n là số cửa sổ và m là số lượng vé tối đa trong một cửa sổ.

Answer 2

Nếu bạn sử dụng heap tối đa, nó có thể được thực hiện trong O (m * logn). Dưới đây là mã C++ -

int main() { 
     int *inputArray; 
     int n; 
     int m; 
     cin >> n; 
     cin >> m; 
     inputArray = new int[n]; 
     for (int i = 0; i < n; i++) { 
      cin >> inputArray[i]; 
     } 
     cout << maximize(inputArray, n, m) << "\n"; 

     return 0; 
    } 

int maximize(int *inputArray, int n, int m){ 

     vector<int> v(inputArray, inputArray + n); 
     int sum = 0; 

     // make max heap 
     make_heap(v.begin(), v.end()); 

     for (m = 4; m != 0; m--) { 
      // get max value 
      int max = v.front(); 

      // move max value to end and heapify 
      pop_heap(v.begin(), v.end()); 
      // pop it out 
      v.pop_back(); 

      sum = sum + max; 

      if (max - 1) { 
       // insert m-1 into vector 
       v.push_back(max - 1); 
       // heapify the new vector 
       push_heap(v.begin(), v.end()); 
      } 
     } 

     return sum; 
    } 

Answer 3

 package package1; 
import java.util.Arrays; 
import java.util.Scanner; 

public class RailwayStation{ 
    int numOfTickets, ticketsToSell; 
    int[] ticketsPerBooth; 

    public RailwayStation(int numOfTickets, int ticketsToSell, int[] ticketsPerBooth) 
    { 
     this.numOfTickets = numOfTickets; 
     this.ticketsToSell = ticketsToSell; 
     this.ticketsPerBooth = ticketsPerBooth; 
    } 

    public int findMaxRevenue() 
    { 
     int[] perBooth = this.ticketsPerBooth; 
     Arrays.sort(perBooth); 
     int i = perBooth.length-1; 
     int revenue = 0; 
     while(i>=0 && ticketsToSell!=0){ 

      int diff = 0; 
      if(i==0){ 

       diff = 1; 
      }else{ 
       diff = perBooth[i] - perBooth[i-1]; 
      } 

      while(diff!=0 && ticketsToSell!=0){ 

       revenue = revenue + perBooth[i]; 
       perBooth[i]--; 
       diff--; 
       ticketsToSell--; 

      } 
      if(ticketsToSell!=0 && i==0){ 
       i = perBooth.length-1; 
      }else{ 
       i--; 
      } 


     } 
     return revenue; 
    } 

    public static void main(String[] args) 
    { 
     Scanner sc = new Scanner(System.in); 
     int numOfBooths = sc.nextInt(); 
     int ticketsToSell = sc.nextInt(); 
     int perBooth[] = new int[numOfBooths]; 
     for(int i = 0; i < numOfBooths; i++) 
     { 
      perBooth[i] = sc.nextInt(); 
     } 
     RailwayStation rt = new RailwayStation(numOfBooths, ticketsToSell, perBooth); 
     System.out.println("Max Revenue = " + rt.findMaxRevenue()); 
    } 
} 

Answer 4

"" "thừa sửa đổi mà tổng kết cho đến khi giới hạn chỉ số của vòng" ""

def modified_fact (giới hạn, số lượng): sum_fact = 0 for i in range (số - giới hạn + 1, số + 1): sum_fact + = i trở sum_fact

''' tôi đã tính toán bao nhiêu vòng tôi sẽ phải làm gì để giảm giá trị. Và trong lần lặp cuối cùng tối đa chỉ số nào tôi cần để lặp lại.

'''

def maximum_earning_algorithm (n, cửa sổ): """

:param windows: 
:param n: 
:rtype: int 
""" 
money = 0 
final_round_limit_index = n % len(windows) 
rounds = n/(len(windows)) 
print final_round_limit_index, rounds 
for i in range(len(windows)): 
    if i < final_round_limit_index: 
     money += modified_fact(rounds + 1, windows[i]) 
    else: 
     money += modified_fact(rounds, windows[i]) 
return money 

nếu tên == 'chính': cửa sổ = [5, 4, 3] in maximum_earning_algorithm (3, cửa sổ)

Answer 5

Cách tiếp cận 1)
Là @ n.m. đã chỉ ra tối ưu hóa nhỏ trên giải pháp MaxHeap:

Bạn không cần phải xóa từng vé một. Nếu bạn có một cửa sổ trên cùng, bạn cần phải biết có bao nhiêu vé và có bao nhiêu vé tiếp theo. Sau đó, bạn có thể loại bỏ sự khác biệt và tính tổng giá trong một thao tác. Với một sửa đổi nhỏ, bạn có thể làm tương tự nếu bạn có nhiều cửa sổ với cùng số lượng vé tối đa.

---

Cách tiếp cận 2) sử dụng mảng được sắp xếp:

tải cửa sổ vào một mảng. Sắp xếp mảng. Đi ngược lại thông qua mảng và như bạn làm: lưu trữ số đó (hiện tại), thêm số đó vào trình tổng hợp, chuyển đến giá trị tiếp theo. Nếu nó là như nhau (hiện tại), sau đó thêm nó vào aggregator, trừ 1 từ nó, tiếp tục đi. Nếu nó khác, hãy quay lại phần cuối của mảng và bắt đầu lại. Làm điều đó N lần (vòng lặp nội bộ, không phải là bên ngoài).

---

Cách tiếp cận 3) sử dụng mảng count (tuyến tính thời gian phức tạp):

1. Tạo một mảng với chỉ số như là không có. vé và giá trị là không. các quầy hàng có nhiều số vé. Vì vậy, {0-> 0, 1-> 1, 2-> 0, 3-> 2} có nghĩa là 1 gian hàng có 1 vé và 2 quầy hàng có 3 vé)

2. Bắt đầu với chỉ số cao nhất của mảng -1) và thêm chỉ mục đó vào trình tổng hợp của bạn (A) sao cho A = 3, rồi giảm chỉ mục đó (3) từ 1 đến 1 và tăng chỉ mục bên dưới (= 2) 1 đến 1.
   Mảng là { 0,1,1,1} và A = 3. Nói lại. A = 6, mảng là {0,1,2,0}. Chỉ mục cuối cùng bằng 0, vì vậy hãy di chuyển con trỏ của bạn đến chỉ mục 2.
   Lặp lại, vì vậy A = 8, mảng = {0,2,1,0}. Nói lại. A = 10, mảng là {0,5,0,0}. (. Cho số lượng vé bán ra)
   ngừng hoạt động khi bạn đã làm t này lần

Đây là việc thực hiện của phương pháp này:

int[] stalls = new int[] { 3,1,3 }; // 2 stalls have 3 tickets each and 1 stall have 1 ticket 
     int t = 4; 

     Arrays.sort(stalls); 

     int tickets = stalls[stalls.length - 1]; 
     int[] dp = new int[tickets + 1]; 

     for (int i = 0; i < stalls.length; i++) { 
      dp[stalls[i]]++; 
     } 

     int total = 0; 
     int i = dp.length - 1; 

     while (t > 0) { 
      if (dp[i] > 0) { 
       total += i; 
       t--; 
       dp[i]--; 
       dp[i - 1]++; 
      } else { 
       i--; 
      } 
     } 

     System.out.println(total);