ปัญหาการบรรจุถัง (ลดจำนวนถังขยะที่ใช้แล้ว) ใน C ++ หรือไม่

ในกรณีขององค์ประกอบ m ที่กำหนดที่มีน้ำหนักและช่องเก็บของต่างกันสำหรับความจุ C แต่ละองค์ประกอบ ให้กำหนดองค์ประกอบแต่ละส่วนให้กับถังขยะ เพื่อลดจำนวนถังขยะที่นำไปใช้งานทั้งหมด สันนิษฐานว่าองค์ประกอบทั้งหมดมีน้ำหนักน้อยกว่าความจุของถัง

แอพพลิเคชั่น

• การวางข้อมูลบนดิสก์หลายแผ่น

• การบรรทุกตู้คอนเทนเนอร์อย่างรถบรรทุก

• บรรจุโฆษณาในช่วงพักของสถานีวิทยุ/โทรทัศน์ที่มีความยาวคงที่

• ตารางงาน

ตัวอย่าง

Input: weight[] = {4, 1, 8, 1, 4, 2}
Bin Capacity c = 10
Output: 2
We require at least 2 bins to accommodate all elements
First bin consists {4, 4, 2} and second bin {8, 2}

ขอบเขตล่าง

เราสามารถคำนวณขอบเขตล่างของจำนวนถังขยะขั้นต่ำที่ต้องการโดยใช้ฟังก์ชัน ceil() ขอบล่างสามารถกำหนดได้ด้านล่าง -

• ถังขยะที่มีจำนวนขั้นต่ำ>=ceil ((น้ำหนักรวม) / (ความจุถัง))

• ในตัวอย่างข้างต้น ขอบล่างของตัวอย่างแรกคือ “ceil(4 + 1 + 8 + 2 + 4 + 1)/10” =2

• อัลกอริทึมโดยประมาณต่อไปนี้ถูกนำมาใช้สำหรับปัญหานี้

อัลกอริทึมออนไลน์

อัลกอริธึมเหล่านี้ถูกนำมาใช้สำหรับปัญหา Bin Packing โดยที่องค์ประกอบมาถึงทีละรายการ (ในลำดับที่ไม่ทราบ) แต่ละองค์ประกอบต้องถูกใส่ลงในถังขยะ ก่อนที่จะพิจารณาองค์ประกอบถัดไป

ฟิตต่อไป -

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

ต่อไปนี้คือแอปพลิเคชัน C++ สำหรับอัลกอริทึมนี้

// C++ program to calculate number of bins required implementing next fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to return number of bins needed implementing next fit online algorithm
int nextFit(int weight1[], int m, int C){
   // Result (Count of bins) and remaining capacity in current bin are initialized.
   int res = 0, bin_rem = C;
   // We have to place elements one by one
   for (int i = 0; i < m; i++) {
      // If this element can't fit in current bin
      if (weight1[i] > bin_rem) {
         res++; // Use a new bin
         bin_rem = C - weight1[i];
      }
      else
      bin_rem -= weight1[i];
      }
   return res;
}
// Driver program
int main(){
   int weight1[] = { 3, 6, 5, 8, 2, 4, 9 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in Next Fit : "
   <<nextFit(weight1, m, C);
   return 0;
}

ผลลัพธ์

Number of bins required in Next Fit : 4

Next Fit ถือเป็นอัลกอริธึมอย่างง่าย ต้องการเวลา O(m) และ O(1) พื้นที่พิเศษในการประมวลผลองค์ประกอบ m เท่านั้น

ฟิตแรก−

เมื่อประมวลผลองค์ประกอบถัดไป ให้ตรวจสอบหรือสแกนถังก่อนหน้าตามลำดับและวางองค์ประกอบในถังแรกที่พอดี หากองค์ประกอบไม่พอดีกับถังที่มีอยู่ในขณะนั้น เราจะเริ่มถังใหม่เท่านั้น

ตัวอย่าง

// C++ program to find number of bins needed implementing First Fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to return number of bins needed implementing first fit online algorithm
int firstFit(int weight1[], int m, int C){
   // We have to initialize result (Count of bins)
   int res = 0;
   // We have to create an array to store remaining space in bins there can be maximum n bins
   int bin_rem[m];
   // We have to place elements one by one
   for (int i = 0; i < m; i++) {
      // We have to find the first bin that can accommodate weight1[i]
      int j;
      for (j = 0; j < res; j++) {
         if (bin_rem[j] >= weight1[i]) {
            bin_rem[j] = bin_rem[j] - weight1[i];
            break;
         }
      }
      // If no bin could accommodate weight1[i]
      if (j == res) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   }
   return res;
}
// Driver program
int main(){
   int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in First Fit : "
   <<firstFit(weight1, m, C);
   return 0;
}

ผลลัพธ์

Number of bins required in First Fit : 4

การใช้งาน First Fit ข้างต้นนั้นกินเวลา O(m2) แต่ First Fit สามารถใช้ได้ในเวลา O(m log m) ในการปรับใช้แผนผังการค้นหาไบนารีที่ปรับสมดุลตัวเองได้

เหมาะสมที่สุด -

แนวคิดคือการวางรายการถัดไปในตำแหน่งที่แคบที่สุด นั่นหมายถึงใส่ไว้ในถังขยะเพื่อให้เหลือพื้นที่ว่างเป็นอย่างน้อย

ตัวอย่าง

// C++ program to calculate number of bins required implementing Best fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to returns number of bins required implementing best fit online algorithm
int bestFit(int weight1[], int m, int C){
   // We have to initialize result (Count of bins)
   int res = 0;
   // We have to create an array to store remaining space in bins there can be maximum n bins
   int bin_rem[m];
   // Place elements one by one
   for (int i = 0; i < m; i++){
      // Find the best bin that can accomodate weight1[i]
      int j;
      // We have to initialize minimum space left and index of best bin
      int min = C + 1, bi = 0;
      for (j = 0; j < res; j++){
         if (bin_rem[j] >= weight1[i] && bin_rem[j] - weight1[i] < min) {
         bi = j;
         min = bin_rem[j] - weight1[i];
      }
   }
   // We create a new bin,if no bin could accommodate weight1[i],
   if (min == C + 1) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   else // Assign the element to best bin
   bin_rem[bi] -= weight1[i];
   }
   return res;
}
// Driver program
int main(){
   int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in Best Fit : "
   <<bestFit(weight1, m, C);
   return 0;
}

ผลลัพธ์

Number of bins required in Best Fit : 4

Best Fit ยังสามารถนำไปใช้ใน O(m log m) เวลาที่ใช้ Self-Balancing Binary Search Trees

อัลกอริธึมออฟไลน์

ในกรณีของเวอร์ชันออฟไลน์ เรามีองค์ประกอบทั้งหมดล่วงหน้า ปัญหาของอัลกอริธึมออนไลน์คือการบรรจุองค์ประกอบขนาดใหญ่เป็นเรื่องยาก โดยเฉพาะอย่างยิ่งหากเกิดขึ้นในช่วงท้ายของลำดับ เราสามารถเอาชนะสิ่งนี้ได้ด้วยการจัดเรียงลำดับอินพุต และวางองค์ประกอบขนาดใหญ่ไว้ก่อน

การลดขนาดพอดีครั้งแรก -

ตัวอย่าง

// C++ program to locate number of bins needed implementing First Fit Decreasing algorithm.
#include <bits/stdc++.h>
using namespace std;
/* We copy firstFit() from above */
int firstFit(int weight1[], int m, int C){
   // We have to initialize result (Count of bins)
   int res = 0;
   // We have to create an array to store remaining space in bins there can be maximum n bins
   int bin_rem[m];
   // We have to place elements one by one
   for (int i = 0; i < m; i++) {
      // We have to find the first bin that can accommodate weight1[i]
      int j;
      for (j = 0; j < res; j++) {
         if (bin_rem[j] >= weight1[i]) {
         bin_rem[j] = bin_rem[j] - weight1[i];
         break;
      }
   }
   // If no bin could accommodate weight1[i]
      if (j == res) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   }
return res;
}
// We have to returns number of bins required implementing first fit decreasing offline algorithm
int firstFitDec(int weight1[], int m, int C){
   // At first we sort all weights in decreasing order
   sort(weight1, weight1 + m, std::greater<int>());
   // Now we call first fit for sorted items
   return firstFit(weight1, m, C);
}
// Driver program
int main(){
   int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in First Fit "
   << "Decreasing : " << firstFitDec(weight1, m, C);
   return 0;
}

ผลลัพธ์

Number of bins required in First Fit Decreasing : 3

การลดพอดีครั้งแรกจะสร้างผลลัพธ์ที่ดีที่สุดสำหรับอินพุตตัวอย่าง เนื่องจากการจัดเรียงองค์ประกอบก่อน

การลดพอดีครั้งแรกยังสามารถใช้ใน O(m log m) เวลาที่ใช้ต้นไม้การค้นหาไบนารีที่ปรับสมดุลตนเองได้