จำนวนช็อคโกแลตสูงสุดที่จะแจกจ่ายให้กับนักเรียน k คนใน C . อย่างเท่าเทียมกัน

เราได้รับช็อคโกแลตจำนวนหนึ่งในกล่องที่ต่อเนื่องกันในรูปแบบของอาร์เรย์และตัวเลข k ซึ่งแสดงถึงจำนวนนักเรียนที่จะแจกจ่ายช็อคโกแลตเหล่านี้ งานในที่นี้คือการเลือกกล่องที่ต่อเนื่องกันเพื่อให้ผลรวมของช็อกโกแลตที่อยู่ในกล่องนั้นสามารถแบ่งให้นักเรียน k ได้เท่าๆ กัน นอกจากนี้เรายังต้องตรวจสอบให้แน่ใจว่าจำนวนช็อกโกแลตมีมากที่สุด

สำหรับสิ่งนี้ เราจะสำรวจอาร์เรย์จากซ้ายไปขวา และเริ่มเพิ่มจำนวนช็อกโกแลตแล้วหารผลรวมด้วย k หากหารด้วยเศษเหลือเท่ากับ 0 แล้วให้เก็บผลรวมนี้ไว้ในตัวแปร เมื่อเราดำเนินการต่อไป เราจะทำซ้ำขั้นตอนนี้จนกว่าเราจะได้ผลรวมสูงสุดดังกล่าว ปัญหาคือการหาผลรวมย่อยสูงสุดหารด้วย k

ป้อนข้อมูล

Choco[]={ 1,2,4,5,2,8,3,5 } k=3

ผลผลิต −จำนวนช็อกโกแลตสูงสุดที่จะแจกจ่ายให้นักเรียน k คนเท่าๆ กัน − 5

คำอธิบาย − อาร์เรย์ย่อยผลรวมสูงสุดคือ { 5,2,8 } ผลรวมของช็อกโกแลตคือ 15 แบ่งเท่า ๆ กัน นักเรียนทั้ง 3 คนจะได้รับช็อกโกแลตสูงสุด 5.

หมายเหตุ − กล่องเรียงต่อกันและดัชนีคือ { 3,4,5 }

ป้อนข้อมูล

Choco[] = { 2,3,7,5,4,8,2,6 } k=5

ผลผลิต −จำนวนช็อกโกแลตสูงสุดที่จะแจกจ่ายให้นักเรียน k คนเท่าๆ กัน − 7

คำอธิบาย − อาร์เรย์ย่อยผลรวมสูงสุดคือ { 3,7,5,4,8,2,6 } รวมช็อกโกแลต 35.

เมื่อแบ่งเท่าๆ กัน ช็อกโกแลตสูงสุดที่นักเรียนทั้ง 5 คนจะได้รับคือ 7

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• เราใช้อาร์เรย์จำนวนเต็ม arr[] ซึ่งบรรจุช็อกโกแลตจำนวนหนึ่งไว้ในภาชนะที่ต่อเนื่องกัน

• จำนวนองค์ประกอบ 'n' หมายถึงจำนวนกล่อง

• เอาเลขที่ ของนักเรียน 'k' เป็นข้อมูลป้อนเข้า

• ฟังก์ชัน maxChocolate( int arr[], int n, int k ) รับอาร์กิวเมนต์สามตัว – อาร์เรย์ ขนาด และหมายเลข ของนักเรียน ก.

• เราจะเริ่มสำรวจ arr[] ตั้งแต่ต้นโดยใช้ for loop

• ใช้ตัวแปร sum และ maxSum สองตัว Sum เก็บผลรวมขององค์ประกอบที่ต่อเนื่องกันของอาร์เรย์ย่อย

• maxSum ใช้เพื่อเก็บผลรวมสูงสุดที่พบจนถึงตอนนี้

• Inside nested for loop ให้เพิ่มองค์ประกอบและตรวจสอบว่า sum%k ให้เศษ 0 หรือไม่

  นอกจากนี้ หากผลรวมนี้> maxSum ให้อัปเดต maxSum

• สุดท้าย maxSum จะมีจำนวนสูงสุด ของชอคโกแลตที่สามารถแบ่งให้นักเรียน k ได้เท่าๆกัน

• คืนค่าผลลัพธ์เป็น maxSum/k ซึ่งเป็นจำนวนช็อกโกแลตที่นักเรียนแต่ละคนได้รับ

ตัวอย่าง

#include <stdio.h>
// to find the maximum number
// of chocolates to be distributed equally among
// k students
int maxChocolates(int arr[], int n, int k){
   int sum;
   int maxSum = 0;
   for(int i=0;i<n;i++){
      sum=0;
      for(int j=i;j<n;j++){
         sum+=arr[j];
         if(sum%k==0 && sum>maxSum)
            maxSum=sum;
      }
   }
   // distributed equally among 'k' students
   return (maxSum / k);
}
int main(){
   int arr[] = { 2, 7, 6, 1, 4, 5 ,5, 3 };
   int n =8;
   int k =3;
   printf("Maximum number of chocolates to be distributed equally among k students: %d   ",maxChocolates(arr, n, k));
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Maximum number of chocolates to be distributed equally among k students − 11