Bài toán chia quà có điều kiện

[mobile7]

Em có 1 bài toán cần giải như thế này.
Dữ liệu đầu vào gồm các yếu tố:
1. Số lượng người được nhận quà (<=10)
2. Số lượng quà (<=100) với giá trị quà khác nhau, chia làm 4 hạng quà từ A-D
Cần chia quà cho đủ các bạn với điều kiện:
- Chênh lệch tối đa về giá trị quà cho trước (giữa người cao nhất và thấp nhất)
- Chênh lệch tối đa về số lượng quà cho trước
- Chênh lệch tối đa về số lượng quà hạng A cho trước
- Chênh lệch tối đa về số lượng quà hạng B cho trước
Đáp án cần thỏa mãn các điều kiện trên và có chênh lệch giá trị quà giữa người cao nhất và thấp nhất là nhỏ nhất.

Dữ liệu đầu vào là các ô bôi vàng và các cột màu đỏ. Đáp án cần xuất ra các ô màu xanh bên phải.

Các bác cho em cách xử lý ạ!

 

[befaint]

Mỗi người được tặng số lượng quà là bao nhiêu hay tùy ý vậy bạn?

Thấy số tiền lên hàng tỉ đồng vậy mình có nhiều quà thế cứ chia hết đi, phân chia làm chi.

 

[mobile7]

Số lượng quà thì tùy ý nhưng phải theo điều kiện bác ạ!

 

[bomberman211]

Mỗi người được tặng số lượng quà là bao nhiêu hay tùy ý vậy bạn?

Thấy số tiền lên hàng tỉ đồng vậy mình có nhiều quà thế cứ chia hết đi, phân chia làm chi.

Giải được bài này thì không chỉ là cao thủ lập trình mà còn là cao thủ toán học hoặc cao thủ search google.

 

[mobile7]

Chắc phải dùng nhiều vòng lặp nhưng em chưa nghĩ đc thuật toán tối ưu với vba

 

[VetMini]

Giải được bài này thì không chỉ là cao thủ lập trình mà còn là cao thủ toán học hoặc cao thủ search google.

Cao với đê gì ở đây.
Toán học: đây là loại bài sắp xếp. Môn toán ứng dụng về quản lý có dạy. Tại bạn không biết môn này nên cho là nó cao cấp.
Lập trình: có được cái mô hình bằng con toán trên rồi thì cứ đấy mà viết code. Mô hình phức tạp chỉ là mất thời gian thôi chứ cần gì phải giỏi.
Khó thì chưa chắc khó, chỉ khi nào muốn đưa nó về dạng tối ưu để đỡ mất thì giờ code và thử mới là khó.
Search Google: bạn chỉ biết biết gú gô nên nói vậy chứ mấy bài toán thuộc về loại ối ưu chính ra chúng cần đọc trong mấy bài nghiên cứu. Những đề tài nghiên cứu có giá trị gú gồ sẽ bó tay. Tối đa là gú gồ chỉ lấy được cái phần tóm tắt. Bởi vì chúng nằm trong những thư viện tư mà bạn phải là member mới trao đổi được (members thường là những viện nghiên cứu, trường đại học,...)

Tôi không muốn thử làm là tại vì bài này thấy chẳng có lợi ích gì cho ai cả.

 

[HieuCD]

Chắc phải dùng nhiều vòng lặp nhưng em chưa nghĩ đc thuật toán tối ưu với vba

Hướng xử lý tàm tạm
1/ Phân bổ số lượng quà cho từng người trong giới hạn int(52/5) +- int((3+1)/2) sao cho thỏa điếu kiện số lượng
2/ Tính số quà của từng hạng
3/ Phân bổ số quà hạng A cho từng người giống như 1/
4/ Phân bổ số quà hạng B cho từng người giống như 1/
5/ Phân bổ số quà các hạng còn lại cho từng người
6/ Tính giá trị và điều chuyển quà cùng hạng khác giá trị giữa từng người sao cho thỏa điều kiện giá trị

 

[bomberman211]

Cao với đê gì ở đây.
Toán học: đây là loại bài sắp xếp. Môn toán ứng dụng về quản lý có dạy. Tại bạn không biết môn này nên cho là nó cao cấp.
Lập trình: có được cái mô hình bằng con toán trên rồi thì cứ đấy mà viết code. Mô hình phức tạp chỉ là mất thời gian thôi chứ cần gì phải giỏi.
Khó thì chưa chắc khó, chỉ khi nào muốn đưa nó về dạng tối ưu để đỡ mất thì giờ code và thử mới là khó.
Search Google: bạn chỉ biết biết gú gô nên nói vậy chứ mấy bài toán thuộc về loại ối ưu chính ra chúng cần đọc trong mấy bài nghiên cứu. Những đề tài nghiên cứu có giá trị gú gồ sẽ bó tay. Tối đa là gú gồ chỉ lấy được cái phần tóm tắt. Bởi vì chúng nằm trong những thư viện tư mà bạn phải là member mới trao đổi được (members thường là những viện nghiên cứu, trường đại học,...)

Tôi không muốn thử làm là tại vì bài này thấy chẳng có lợi ích gì cho ai cả.

Người biết thì thấy đơn giản, không biết không hiểu thì thấy nó cao siêu thôi bác. Dù sao em cũng rất hóng cách giải bài này, nhiều điều kiện quá, rất dễ vô nghiệm.

 

[VetMini]

Người biết thì thấy đơn giản, không biết không hiểu thì thấy nó cao siêu thôi bác. Dù sao em cũng rất hóng cách giải bài này, nhiều điều kiện quá, rất dễ vô nghiệm.

Tôi không biết, không hiểu nhưng cũng chẳng thấy nó cao siêu.
Kinh nghiệm cho tôi biết cái khó nhất chỉ nằm ở chỗ bị sót nghiệm. Tức là nó có nghiệm nhưng cách giải của mình bị sót, kết luận rằng vô nghiệm.

 

[bomberman211]

Tôi không biết, không hiểu nhưng cũng chẳng thấy nó cao siêu.
Kinh nghiệm cho tôi biết cái khó nhất chỉ nằm ở chỗ bị sót nghiệm. Tức là nó có nghiệm nhưng cách giải của mình bị sót, kết luận rằng vô nghiệm.

Khó hơn nữa là tìm phương án tối ưu, tức chênh lệch là nhỏ nhất có thể, khi đó phải có hệ số 'ưu tiên' của các điều kiện, xem điều kiện nào là quan trọng nhất.

 

[VetMini]

Khó hơn nữa là tìm phương án tối ưu, tức chênh lệch là nhỏ nhất có thể, khi đó phải có hệ số 'ưu tiên' của các điều kiện, xem điều kiện nào là quan trọng nhất.

Điển hình là đây: Bạn chưa giải đã nghĩ đến tối ưu rồi. Vì vậy mới thấy nó khó.
Đi từng bước một sẽ quen với cách giải nhũng bài thế này.
Bạn cứ trông gương tác giả bài #7. Cứ từ từ, mỗi bước phải trải qua vài thử thách. Đối diện với thử thách nhiều sẽ quen.

 

[bomberman211]

cái khó nhất chỉ nằm ở chỗ bị sót nghiệm

À. Ý em là ngoài cái khó nhất của bác em còn hóng cái khó hơn nữa. Chỉ hóng thôi chứ sức e chưa làm được

 

[batman1]

Ta giả thiết: "Số quà 1" <= "Số quà 2" <= ... <= "Số quà 5". Sẽ rút thăm ai nhận "Số quà 1", ..., "Số quà 5".

"Số quà 5" không thể < 52/5 = 10,4. Tức "Số quà 5" >= 11.

1. "Số quà 5" = 11.
"Số quà 4" không thể < (52-11)/4 = 10,25, nhưng không thể > 11 ("Số quà 5"). Vậy "Số quà 4" = 11.
"Số quà 3" không thể < (52-2*11)/3 = 10, nhưng không thể > 11. Vậy "Số quà 3" = 10 hoặc 11.

1.1. "Số quà 3" = 11.
"Số quà 2" không thể < (52-3*11)/2 =9,5, nhưng không thể > 11. Vậy "Số quà 2" = 10 hoặc 11

Tóm lại có: 9 - 10 - 11 -11 - 11 hoặc 8 - 11 - 11 - 11 - 11

1.2. "Số quà 3" = 10.
"Số quà 2" không thể < (52-2*11-10)/2 =10, nhưng không thể > 10 ("Số quà 3"). Vậy "Số quà 2" = 10.
Tóm lại có: 10 - 10 - 10 - 11 - 11.

2. "Số quà 5" = 12. Vậy "Số quà 1" >= 9 (do "Số quà 5" - "Số quà 1" <= 3).
9 <= "Số quà 1" <= "Số quà 2", vậy "Số quà 1" + "Số quà 2" >= 18 *
Không thể có "Số quà 3" = 9 ** vì khi đó cả "Số quà 1" và "Số quà 2" cũng phải = 9 và tổng số quà là <= 3*9 + 2*12 = 51 < 52.

"Số quà 4" không thể < (52-12)/4 = 10, nhưng không thể > 12 ("Số quà 5"). Ta xét:

2.1."Số quà 4" = 12.
Do * và **: 9 < "Số quà 3" <= 52 - 2*12 - 18 = 10. Vậy "Số quà 3" = 10
Ta có: 9 - 9 - 10 - 12 - 12.

2.2. "Số quà 4" = 11.
Do * và **: 9 < "Số quà 3" <= 52 - 12 - 11 - 18 = 11.
2.2.1. "Số quà 3" = 10. Chỉ có thể "Số quà 1" là 9 và "Số quà 2" = 10.
Ta có: 9 - 10 - 10 - 11 - 12

2.2.2. "Số quà 3" = 11. Lúc này "Số quà 1" + "Số quà 2" = 52 - 12 - 11 - 11 = 18. Vậy "Số quà 1" = "Số quà 2" = 9
Ta có: 9 - 9 - 11 - 11 - 12

2.3. "Số quà 4" là 10.
9 < "Số quà 3" <= "Số quà 4" = 10. Vậy "Số quà 3" = 10.
"Số quà 1" + "Số quà 2" = 52 - 12 - 10 - 10 = 20, và do "Số quà 1" <= "Số quà 2" <= "Số quà 3" = 10, nên "Số quà 1" = "Số quà 2" = 10.
Ta có: 10 - 10 - 10 - 10 - 12

3. "Số quà 5" >= 13. Do "Số quà 5" - "Số quà 1" <= 3 nên "Số quà 1" >= 10
=> "Số quà 1" + "Số quà 2" + ... + "Số quà 5" >= 4*10 + 13 = 53 > 52 => mâu thuẫn.

Vậy chỉ có:
8, 11, 11, 11, 11
9, 9, 10, 12, 12
9, 9, 11, 11, 12
9, 10, 10, 11, 12
9, 10, 11, 11, 11
10, 10, 10, 10, 12
10, 10, 10, 11, 11

Chỉ khi tính về số lượng quà mới có thể tư duy tương đối ngắn gọn như vậy. Việc xét các điều kiện khác để chỉ ra các khả năng chỉ bằng kiểu tư duy như thế là rất khó khăn và mất thời gian. Công việc đó chỉ có thể xét bằng lập trình. Cái khó là tìm thuật toán để giảm đáng kể số lượng cần kiểm tra.

 

[mobile7]

Vâng bước đầu thì em cũng tính như vậy. Nhưng giờ nhiều vòng lặp quá thì lồng vào nhau ntn để ch trình chạy được nữa