Chia sẻ Trái cây Khá (Lập trình Động)

Question

Tôi đang gặp khó khăn trong việc cố gắng tìm ra cách giải quyết vấn đề này một cách hiệu quả. Hãy để tôi mô tả cách thức hoạt động:

"Một người mẹ làm việc chăm chỉ mua nhiều loại trái cây có giá trị dinh dưỡng khác nhau cho 3 trẻ em, Amelia, Jessica và Bruno. Cả hai cô gái đều thừa cân và họ rất xấu xa và luôn bỏ rơi Bruno không có gì, vì vậy mẹ của họ quyết định chia sẻ những món ăn theo cách thức sau đây:

• Amelia là một nặng nhất được số tiền nhất của dinh dưỡng giá trị gia tăng
• Jessica nhận được một khoản tiền tương đương hoặc thấp hơn Amelia
• Bruno được một số tiền bằng hoặc nhỏ hơn Jessica, nhưng bạn cần phải tìm cách để cho anh ta giá trị dinh dưỡng cao nhất có thể trong khi tôn trọng quy tắc (A> = J> = B) "

Lưu ý: Vấn đề ban đầu được mô tả khác nhau nhưng tôi không muốn bạn cùng lớp tìm bài đăng này khi họ google giúp hehe.

Một trong những trường hợp thử nghiệm do giáo viên của tôi là như sau:

The fruit list has the following values { 4, 2, 1, 8, 11, 5, 1} 

Input: 
7 -----> Number of Fruits 
4 2 1 8 11 5 1 ----> Fruits Nutritional Values 

Output: 
1 11 ----> One fruit, their nutritional values sum for Amelia 
5  ----> Position of the fruit in the list 
3 11 ----> Three fruits, their nutritional values sum for Jessica 
1 2 6 ----> Position of the fruits in the list 
3 10 ----> Three fruits, their nutritional values sum for Bruno 
3 4 7 ----> Position of the fruits in the list 

Lưu ý: Tôi biết rằng có một số cách lặn các loại trái cây trong những đứa trẻ, nhưng nó không thực sự quan trọng như miễn là nó tuân theo quy tắc A> = J> = B.

Lúc đầu, tôi đã tạo một thuật toán tạo tất cả các tập con, mỗi tập hợp con có tổng của chúng và các vị trí được sử dụng. Phương pháp đó nhanh chóng bị loại bỏ vì danh sách các loại trái cây có thể có tới 50 quả, và thuật toán tập hợp con là O (2^n). Tôi hết trí nhớ.

Ý tưởng thứ hai mà tôi có là sử dụng Lập trình động. Trong tiêu đề cột, tôi sẽ có các vị trí của Danh sách trái cây, trong tiêu đề hàng giống nhau, thật khó để giải thích với các chữ cái vì vậy tôi sẽ tiến hành làm bảng cho ví dụ trước {4, 2, 1, 8 , 11, 5, 1}.

00 01 02 03 04 05 06 07 
00 
01 
02 
03 
04 
05 
06 
07 

Mỗi lần chúng ta tiến vào hàng dưới đây chúng ta thêm các vị trí 1,2,3, ..., 7

00 01 02 03 04 05 06 07 
00 00      <---No positions in use 
01 04      <---RowPosition 1 + Column Position(Column 0) (4+0) 
02 06      <---RowPosition 1 + RowPosition 2 + Column Position (4+2+0) 
03 07      <---RP(1) + RP(2) + RP(3) + CP(0) (4+2+1+0) 
04 15      <--- (4+2+1+8+0) 
05 26 
06 31 
07 32      <--- (4+2+1+8+11+5+1+0) 

Bây giờ bạn biết làm thế nào nó đi cho phép thêm hàng đầu tiên

00 01 02 03 04 05 06 07 
00 00 04 02 01 08 11 05 01 <-- Sum of RP + CP      
01 04 00 06 05 12 15 09 05 <-- Sum of RP(0..1) + CP      
02 06      
03 07      
04 15      
05 26 
06 31 
07 32      

Tôi đặt số 00 vì vị trí thứ nhất đã được sử dụng. Bảng hoàn thành sẽ trông như thế này.

00 01 02 03 04 05 06 07 
00 00 04 02 01 08 11 05 01      
01 04 00 06 05 12 15 09 05       
02 06 00 00 07 14 17 11 07     
03 07 00 00 00 15 18 12 08     
04 15 00 00 00 00 26 20 16      
05 26 00 00 00 00 00 31 27 
06 31 00 00 00 00 00 00 32 
07 32 00 00 00 00 00 00 00  

Bây giờ chúng tôi có bảng. Tôi chia tổng giá trị dinh dưỡng cho số lượng trẻ em, 32/3 = 10.6667, trần nhà sẽ là 11. Tôi cố gắng kiểm tra 11, nếu nó ở trong bảng, tôi chọn nó và đánh dấu vị trí của hàng và cột của các bảng được sử dụng, sau đó tôi sẽ cố gắng kiểm tra 11 lần nữa, nếu nó nằm trong bảng tôi chọn nó nếu không thì hãy tìm 10, hoặc 9, vv cho đến khi tôi tìm thấy nó. Sau đó tôi sẽ đánh dấu các vị trí tương ứng như được sử dụng sau đó tổng hợp các vị trí không sử dụng để có được trái cây của Bruno.

Tôi biết rằng phải có cách tốt hơn để làm điều này bởi vì tôi đã tìm thấy một lỗ hổng trong phương pháp của tôi, bảng chỉ có tổng của một vài tập con. Vì vậy, có thể điều đó sẽ gây bất lợi trong một vài trường hợp thử nghiệm. Có lẽ một Cube Memoization 3D ?, Tôi nghĩ rằng nó sẽ tiêu thụ quá nhiều bộ nhớ, và tôi có một giới hạn quá 256MB.

Ồ, tôi không nhận ra rằng tôi đã nhập nhiều x.X. Tôi hy vọng tôi không nhận được nhiều tl; dr. Bất kỳ trợ giúp/hướng dẫn nào sẽ được đánh giá rất cao: D

EDIT: Tôi đã tạo mã tạo bảng trong trường hợp bất kỳ ai muốn dùng thử.

static void TableGen(int[] Fruits) 
    { 
     int n = Fruits.Length + 1; 
     int[,] memo = new int[n, n]; 

     for (int i = 1; i < n; i++) 
     { 
      memo[0, i] = Fruits[i - 1]; 
      memo[i, 0] = memo[i - 1, 0] + Fruits[i - 1]; 

      for (int j = i + 1; j < n; j++) 
       memo[i, j] = memo[i, 0] + Fruits[j - 1];    
     } 


     for (int i = 0; i < n; i++) 
     { 
      for (int j = 0; j < n; j++) 
       Console.Write("{0:00} ", memo[i, j]); 

      Console.WriteLine(); 
     } 

    } 

Answer 1

for(i = 0; i < count; i++) 
    { 
    currentFruit=Fruits.Max(); 

    if(Amelia.Sum() + currentFruit < Jessica.Sum() + currentFruit) 
     { 
     Amelia.Add(currentFruit); 
     Fruits.Remove(currentFruit); 
     continue; 
     } 
    if(Jessica.Sum() + currentFruit < Bruno.Sum() + currentFruit) 
     { 
     Jessica.Add(currentFruit); 
     Fruits.Remove(currentFruit); 
     continue; 
     } 
    Bruno.Add(currentFruit); 
    Fruits.Remove(currentFruit); 
    } 

này làm việc cho các loại trái cây có giá trị tương đối giống nhau. Nếu bạn thêm một trái cây có giá trị lớn hơn tất cả các loại trái cây khác kết hợp (mà tôi đã từng làm một lần do tai nạn) nó sẽ bị hỏng một chút.

Answer 2

Cách tính toán chuyên sâu về mặt tính toán một chút là gán quả theo cách tròn, bắt đầu với giá trị dinh dưỡng cao nhất cho amelia.
Từ đó, dần dần vòng qua trái cây từ giá trị dinh dưỡng thấp nhất được tổ chức bởi amelia, và thử mỗi kết hợp hoặc (a) cho trái cây để jessica, hoặc (b) trao đổi trái cây với một tổ chức bởi jessica, trong khi vẫn đáp ứng qui định. Sau đó áp dụng cùng một phương pháp cho jessica và bruno. Lặp lại 2 vòng lặp này cho đến khi không thể hoán đổi hoặc trao đổi thêm.
Hơi phức tạp hơn, nhưng có khả năng nhanh hơn, sẽ đồng thời trao/hoán đổi thành jess/bruno. Đối với mỗi 2 miếng trái cây mà A giữ, bạn sẽ có 4 tùy chọn để thử, với nhiều hơn nếu bạn cùng một lúc thử và cân bằng J & B.

Để có một thuật toán nhanh hơn, bạn có thể thử hỏi tại ngăn toán học trang web trao đổi, vì đây là một vấn đề lý thuyết tập hợp rất nhiều.