Giải quyết thuật toán lợi nhuận tối đa

Question

Tôi đang thực hành các thuật toán cho các cuộc phỏng vấn việc làm sắp tới và tôi gặp sự cố khi triển khai chính xác giải pháp này. Tôi cũng đang cố gắng tối đa hóa hiệu quả. Đây là vấn đề:

Tối đa hóa lợi nhuận của doanh nghiệp bạn bán thanh kim loại. Nếu bạn bán N thanh kim loại có chiều dài L, bạn nhận được N * L * metal_price. Các thanh kim loại nhỏ hơn còn lại sẽ được chuyển vào thùng rác. Để cắt thanh kim loại, bạn cần phải trả cost_per_cut cho mỗi lần cắt. Lợi nhuận tối đa bạn có thể kiếm được là bao nhiêu? đầu vào

constraints: 
lengths will be 1 to 50 elements, inclusive. 
each element of length will lie in range [1,10000] 
1 <= metal_price, cost_per_cut <=1000 

mẫu:

cost_per_cut =1 

metal_price =10 

lengths = [26,103, 59] 

return: 1770 

cách cuốn sách giải quyết này là chiều dài tối ưu nhất của thanh là 6. vì vậy chúng tôi cắt 4 miếng có độ dài 6 từ que 1st, và ném miếng dài 2 từ nó. tiếp theo chúng tôi cắt 17 miếng chiều dài 6 từ thanh thứ 2, và vứt bỏ chiều dài 1. cho thứ ba, chúng tôi cắt 9 miếng chiều dài 6, và ném một mảnh chiều dài 5. vì vậy trong tổng số chúng tôi đã thực hiện 30 vết cắt. Vì vậy, 30 * 6 * 10 - 30 * 1-1770

Đây là nỗ lực của tôi cho đến nay:

def maxProfit(cost_per_cut, metal_price, lengths): 

    profit =0 
    for num in lengths: 

Tôi chỉ là không thực sự chắc chắn làm thế nào để đi về việc này. Tôi có nên lặp lại các con số và xem con số thấp nhất mà chúng có thể chia hết cho và sử dụng số đó không? Bất kỳ ý tưởng?

Answer 1

Kể từ khi dãy đầu vào là khá nhỏ, có thể giúp bạn không chỉ brute force này

static int getProfit(int[] rods, int cutCost, int metalPrice, int L) 
    { 
     int profit = 0; 
     foreach (int rod in rods) 
     { 
      if (rod % L == 0) 
      { 
       profit += (metalPrice * rod - (rod/L - 1) * cutCost); 
      } 
      else 
      { 
       profit += (metalPrice * (rod - rod % L) - (rod/L) * cutCost); 
      } 
     } 
     return profit; 
    } 

    static void Main(string[] args) 
    { 
     int[] rods = new int[] { 26,103,59}; 
     int cutCost =1; 
     int metalPrice=10; 
     int maxProfit = 0; 
     for (int L = 1; L <= 10000; ++L) 
     { 
      int profit= getProfit(rods, cutCost, metalPrice, L); 
      if (profit > maxProfit) 
      { 
       maxProfit = profit; 
      } 
     } 
     Console.WriteLine(maxProfit); 
    } 

Answer 2

Trong khi các thuật toán được cung cấp bởi @JasonL, phù hợp trả lời câu hỏi, nhưng tôi nghĩ rằng chỉ vì chiều dài của các yếu tố nằm trong khoảng [1,1000] chúng tôi không cần phải nhất thiết phải bắt đầu từ 1 và đi tất cả các cách để 1000.

hãy trường hợp của bạn ví dụ:

lengths = [26,103, 59] 

các lý tưởng tình huống sẽ là nếu nhỏ nhất của những con số này, tức là 26 cũng là hệ số 103 và 59. Chúng tôi sẽ không phải để thùng rác bất kỳ chiều dài và có lợi nhuận tối đa.

Vì vậy, trong thuật toán của bạn, đó là lần kiểm tra đầu tiên bạn nên làm. Bây giờ nếu số nhỏ nhất không chia hai số còn lại. Chỉ cần lặp qua số lớn nhất cho đến 1. Khi @ user3386109, đúng được chỉ ra, không cần thiết nhỏ nhất luôn được bao gồm, tuy nhiên lớn nhất nên là vì chúng tôi đang tối đa hóa lợi nhuận ở đây. Vì vậy, trong trường hợp của bạn, thay vì kiểm tra từ [1,1000] nếu bạn chỉ cần kiểm tra từ [1,103] và tìm bội số lớn nhất của những con số này nhỏ hơn hoặc bằng 26.103, 59 và tính toán lợi nhuận một cách thích hợp. Bạn nên có lợi nhuận tối đa.

Thời gian phức tạp của thuật toán này ->O(max(lengths)*size(lengths)) nơi lengths là mảng [26,103, 59] và max() là yếu tố lớn nhất của mảng đó và size() hiện chiều dài của mảng đó.

Hy vọng nó giúp bạn bắt đầu đi đúng hướng.