给定n个不同重量的物品和每个容量为c的箱子，将每个物品分配给一个箱子，以使使用的箱子总数最小化。可以假设所有物品的重量都小于料仓容量。 例子：
null
Input: weight[] = {4, 8, 1, 4, 2, 1} Bin Capacity c = 10Output: 2We need minimum 2 bins to accommodate all itemsFirst bin contains {4, 4, 2} and second bin {8, 1, 1}Input: weight[] = {9, 8, 2, 2, 5, 4} Bin Capacity c = 10Output: 4We need minimum 4 bins to accommodate all items. Input: weight[] = {2, 5, 4, 7, 1, 3, 8}; Bin Capacity c = 10Output: 3
下限 我们总能找到所需的最小垃圾箱数量的下限。下限可给出如下：
Min no. of bins >= Ceil ((Total Weight) / (Bin Capacity))
在上述示例中，第一示例的下限为“ceil（4+8+1+4+2+1）/10”=2，第二示例的下限为“ceil（9+8+2+2+5+4）/10”=3。 这个问题是一个NP难问题，找到精确的最小箱子数需要指数时间。下面是这个问题的近似算法。 应用
- 像卡车一样装载集装箱。
- 将数据放在多个磁盘上。
- 作业调度。
- 在固定长度的电台/电视台包装广告。
- 将大量音乐收藏在磁带/CD等上。
在线算法 这些算法适用于物品一次到达一个箱子（顺序未知）的箱子包装问题，在考虑下一个物品之前，每个物品都必须放在箱子里。 1.下一次试穿： 处理下一个项目时，检查它是否与上一个项目放在同一个箱子中。只有在没有垃圾桶的情况下，才使用新垃圾桶。 下面是C++实现该算法。
C++
// C++ program to find number of bins required using // next fit algorithm. #include <bits/stdc++.h> using namespace std; // Returns number of bins required using next fit // online algorithm int nextFit( int weight[], int n, int c) { // Initialize result (Count of bins) and remaining // capacity in current bin. int res = 0, bin_rem = c; // Place items one by one for ( int i = 0; i < n; i++) { // If this item can't fit in current bin if (weight[i] > bin_rem) { res++; // Use a new bin bin_rem = c - weight[i]; } else bin_rem -= weight[i]; } return res; } // Driver program int main() { int weight[] = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = sizeof (weight) / sizeof (weight[0]); cout << "Number of bins required in Next Fit : " << nextFit(weight, n, c); return 0; } |
JAVA
// Java program to find number // of bins required using // next fit algorithm. class GFG { // Returns number of bins required // using next fit online algorithm static int nextFit( int weight[], int n, int c) { // Initialize result (Count of bins) and remaining // capacity in current bin. int res = 0 , bin_rem = c; // Place items one by one for ( int i = 0 ; i < n; i++) { // If this item can't fit in current bin if (weight[i] > bin_rem) { res++; // Use a new bin bin_rem = c - weight[i]; } else bin_rem -= weight[i]; } return res; } // Driver program public static void main(String[] args) { int weight[] = { 2 , 5 , 4 , 7 , 1 , 3 , 8 }; int c = 10 ; int n = weight.length; System.out.println( "Number of bins required in Next Fit : " + nextFit(weight, n, c)); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation for above approach def nextfit(weight, c): res = 0 rem = c for _ in range ( len (weight)): if rem > = weight[_]: rem = rem - weight[_] else : res + = 1 rem = c - weight[_] return res # Driver Code weight = [ 2 , 5 , 4 , 7 , 1 , 3 , 8 ] c = 10 print ( "Number of bins required in Next Fit :" , nextfit(weight, c)) # This code is contributed by code_freak |
C#
// C# program to find number // of bins required using // next fit algorithm. using System; class GFG { // Returns number of bins required // using next fit online algorithm static int nextFit( int []weight, int n, int c) { // Initialize result (Count of bins) and remaining // capacity in current bin. int res = 0, bin_rem = c; // Place items one by one for ( int i = 0; i < n; i++) { // If this item can't fit in current bin if (weight[i] > bin_rem) { res++; // Use a new bin bin_rem = c - weight[i]; } else bin_rem -= weight[i]; } return res; } // Driver program public static void Main(String[] args) { int []weight = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = weight.Length; Console.WriteLine( "Number of bins required" + " in Next Fit : " + nextFit(weight, n, c)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to find number // of bins required using // next fit algorithm. // Returns number of bins required // using next fit online algorithm function nextFit(weight, n, c) { // Initialize result (Count of bins) and remaining // capacity in current bin. let res = 0, bin_rem = c; // Place items one by one for (let i = 0; i < n; i++) { // If this item can't fit in current bin if (weight[i] > bin_rem) { res++; // Use a new bin bin_rem = c - weight[i]; } else bin_rem -= weight[i]; } return res; } // Driver Code let weight = [ 2, 5, 4, 7, 1, 3, 8 ]; let c = 10; let n = weight.length; document.write( "Number of bins required in Next Fit : " + nextFit(weight, n, c)); // This code is contributed by target_2. </script> |
输出：
Number of bins required in Next Fit : 4
下一步是一个简单的算法。它只需要O（n）个时间和O（1）个额外的空间来处理n个项目。 下一次拟合为2近似值，即该算法使用的箱子数量以最优值的两倍为界。考虑任何两个相邻的容器。这两个箱子中的物品总和必须大于c；否则，NextFit会将第二个箱子中的所有物品放入第一个箱子。其他所有垃圾箱也是如此。因此，最多浪费了一半的空间，因此如果M是最优的，Next Fit最多使用200万个垃圾箱。 2.首次试穿： 处理下一个项目时，按顺序扫描之前的箱子，并将项目放入第一个适合的箱子中。仅当新垃圾箱不适合任何现有垃圾箱时，才启动新垃圾箱。
C++
// C++ program to find number of bins required using // First Fit algorithm. #include <bits/stdc++.h> using namespace std; // Returns number of bins required using first fit // online algorithm int firstFit( int weight[], int n, int c) { // Initialize result (Count of bins) int res = 0; // Create an array to store remaining space in bins // there can be at most n bins int bin_rem[n]; // Place items one by one for ( int i = 0; i < n; i++) { // Find the first bin that can accommodate // weight[i] int j; for (j = 0; j < res; j++) { if (bin_rem[j] >= weight[i]) { bin_rem[j] = bin_rem[j] - weight[i]; break ; } } // If no bin could accommodate weight[i] if (j == res) { bin_rem[res] = c - weight[i]; res++; } } return res; } // Driver program int main() { int weight[] = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = sizeof (weight) / sizeof (weight[0]); cout << "Number of bins required in First Fit : " << firstFit(weight, n, c); return 0; } |
JAVA
// Java program to find number of bins required using // First Fit algorithm. class GFG { // Returns number of bins required using first fit // online algorithm static int firstFit( int weight[], int n, int c) { // Initialize result (Count of bins) int res = 0 ; // Create an array to store remaining space in bins // there can be at most n bins int []bin_rem = new int [n]; // Place items one by one for ( int i = 0 ; i < n; i++) { // Find the first bin that can accommodate // weight[i] int j; for (j = 0 ; j < res; j++) { if (bin_rem[j] >= weight[i]) { bin_rem[j] = bin_rem[j] - weight[i]; break ; } } // If no bin could accommodate weight[i] if (j == res) { bin_rem[res] = c - weight[i]; res++; } } return res; } // Driver program public static void main(String[] args) { int weight[] = { 2 , 5 , 4 , 7 , 1 , 3 , 8 }; int c = 10 ; int n = weight.length; System.out.print( "Number of bins required in First Fit : " + firstFit(weight, n, c)); } } // This code is contributed by Rajput-Ji |
Python3
# Python program to find number of bins required using # First Fit algorithm. # Returns number of bins required using first fit # online algorithm def firstFit(weight, n, c): # Initialize result (Count of bins) res = 0 # Create an array to store remaining space in bins # there can be at most n bins bin_rem = [ 0 ] * n # Place items one by one for i in range (n): # Find the first bin that can accommodate # weight[i] j = 0 while ( j < res): if (bin_rem[j] > = weight[i]): bin_rem[j] = bin_rem[j] - weight[i] break j + = 1 # If no bin could accommodate weight[i] if (j = = res): bin_rem[res] = c - weight[i] res = res + 1 return res # Driver program weight = [ 2 , 5 , 4 , 7 , 1 , 3 , 8 ] c = 10 n = len (weight) print ( "Number of bins required in First Fit : " ,firstFit(weight, n, c)) # This code is contributed by shubhamsingh10 |
C#
// C# program to find number of bins required using // First Fit algorithm. using System; class GFG { // Returns number of bins required using first fit // online algorithm static int firstFit( int []weight, int n, int c) { // Initialize result (Count of bins) int res = 0; // Create an array to store remaining space in bins // there can be at most n bins int []bin_rem = new int [n]; // Place items one by one for ( int i = 0; i < n; i++) { // Find the first bin that can accommodate // weight[i] int j; for (j = 0; j < res; j++) { if (bin_rem[j] >= weight[i]) { bin_rem[j] = bin_rem[j] - weight[i]; break ; } } // If no bin could accommodate weight[i] if (j == res) { bin_rem[res] = c - weight[i]; res++; } } return res; } // Driver code public static void Main(String[] args) { int []weight = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = weight.Length; Console.Write( "Number of bins required in First Fit : " + firstFit(weight, n, c)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find number of bins required using // First Fit algorithm. // Returns number of bins required using first fit // online algorithm function firstFit(weight,n,c) { // Initialize result (Count of bins) let res = 0; // Create an array to store remaining space in bins // there can be at most n bins let bin_rem = new Array(n); // Place items one by one for (let i = 0; i < n; i++) { // Find the first bin that can accommodate // weight[i] let j; for (j = 0; j < res; j++) { if (bin_rem[j] >= weight[i]) { bin_rem[j] = bin_rem[j] - weight[i]; break ; } } // If no bin could accommodate weight[i] if (j == res) { bin_rem[res] = c - weight[i]; res++; } } return res; } // Driver program let weight=[ 2, 5, 4, 7, 1, 3, 8]; let c = 10; let n = weight.length; document.write( "Number of bins required in First Fit : " + firstFit(weight, n, c)); // This code is contributed by patel2127 </script> |
输出：
Number of bins required in First Fit : 4
上述首次拟合的实施需要O（n 2. )时间，但第一次拟合可以使用自平衡二叉搜索树在O（n logn）时间内实现。 如果M是箱子的最佳数量，那么First Fit使用的箱子永远不会超过170万个。因此，就垃圾箱数量上限而言，第一次拟合优于下一次拟合。 3.最佳匹配： 这样做的目的是把下一件物品放在“最紧”的地方。也就是说，把它放进垃圾箱，这样就剩下了最小的空间。
C++
// C++ program to find number // of bins required using // Best fit algorithm. #include <bits/stdc++.h> using namespace std; // Returns number of bins required using best fit // online algorithm int bestFit( int weight[], int n, int c) { // Initialize result (Count of bins) int res = 0; // Create an array to store // remaining space in bins // there can be at most n bins int bin_rem[n]; // Place items one by one for ( int i = 0; i < n; i++) { // Find the best bin that can accommodate // weight[i] int j; // 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] >= weight[i] && bin_rem[j] - weight[i] < min) { bi = j; min = bin_rem[j] - weight[i]; } } // If no bin could accommodate weight[i], // create a new bin if (min == c + 1) { bin_rem[res] = c - weight[i]; res++; } else // Assign the item to best bin bin_rem[bi] -= weight[i]; } return res; } // Driver program int main() { int weight[] = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = sizeof (weight) / sizeof (weight[0]); cout << "Number of bins required in Best Fit : " << bestFit(weight, n, c); return 0; } |
JAVA
// Java program to find number // of bins required using // Best fit algorithm. class GFG { // Returns number of bins // required using best fit // online algorithm static int bestFit( int weight[], int n, int c) { // Initialize result (Count of bins) int res = 0 ; // Create an array to store // remaining space in bins // there can be at most n bins int []bin_rem = new int [n]; // Place items one by one for ( int i = 0 ; i < n; i++) { // Find the best bin that // can accommodate // weight[i] int j; // 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] >= weight[i] && bin_rem[j] - weight[i] < min) { bi = j; min = bin_rem[j] - weight[i]; } } // If no bin could accommodate weight[i], // create a new bin if (min == c + 1 ) { bin_rem[res] = c - weight[i]; res++; } else // Assign the item to best bin bin_rem[bi] -= weight[i]; } return res; } // Driver code public static void main(String[] args) { int []weight = { 2 , 5 , 4 , 7 , 1 , 3 , 8 }; int c = 10 ; int n = weight.length; System.out.print( "Number of bins required in Best Fit : " + bestFit(weight, n, c)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find number # of bins required using # First Fit algorithm. # Returns number of bins required # using first fit # online algorithm def firstFit(weight, n, c): # Initialize result (Count of bins) res = 0 ; # Create an array to store # remaining space in bins # there can be at most n bins bin_rem = [ 0 ] * n; # Place items one by one for i in range (n): # Find the first bin that # can accommodate # weight[i] j = 0 ; # Initialize minimum space # left and index # of best bin min = c + 1 ; bi = 0 ; for j in range (res): if (bin_rem[j] > = weight[i] and bin_rem[j] - weight[i] < min ): bi = j; min = bin_rem[j] - weight[i]; # If no bin could accommodate weight[i], # create a new bin if ( min = = c + 1 ): bin_rem[res] = c - weight[i]; res + = 1 ; else : # Assign the item to best bin bin_rem[bi] - = weight[i]; return res; # Driver code if __name__ = = '__main__' : weight = [ 2 , 5 , 4 , 7 , 1 , 3 , 8 ]; c = 10 ; n = len (weight); print ( "Number of bins required in First Fit : " , firstFit(weight, n, c)); # This code is contributed by Rajput-Ji |
C#
// C# program to find number // of bins required using // Best fit algorithm. using System; class GFG { // Returns number of bins // required using best fit // online algorithm static int bestFit( int [] weight, int n, int c) { // Initialize result (Count of bins) int res = 0; // Create an array to store // remaining space in bins // there can be at most n bins int [] bin_rem = new int [n]; // Place items one by one for ( int i = 0; i < n; i++) { // Find the best bin that // can accommodate // weight[i] int j; // 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] >= weight[i] && bin_rem[j] - weight[i] < min) { bi = j; min = bin_rem[j] - weight[i]; } } // If no bin could accommodate weight[i], // create a new bin if (min == c + 1) { bin_rem[res] = c - weight[i]; res++; } // Assign the item to best bin else bin_rem[bi] -= weight[i]; } return res; } // Driver code public static void Main(String[] args) { int [] weight = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = weight.Length; Console.Write( "Number of bins required in Best Fit : " + bestFit(weight, n, c)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // javascript program to find number // of bins required using // Best fit algorithm. // Returns number of bins // required using best fit // online algorithm function bestFit(weight , n , c) { // Initialize result (Count of bins) var res = 0; // Create an array to store // remaining space in bins // there can be at most n bins var bin_rem = Array(n).fill(0); // Place items one by one for (i = 0; i < n; i++) { // Find the best bin that // can accommodate // weight[i] var j; // Initialize minimum space // left and index // of best bin var min = c + 1, bi = 0; for (j = 0; j < res; j++) { if (bin_rem[j] >= weight[i] && bin_rem[j] - weight[i] < min) { bi = j; min = bin_rem[j] - weight[i]; } } // If no bin could accommodate weight[i], // create a new bin if (min == c + 1) { bin_rem[res] = c - weight[i]; res++; } else // Assign the item to best bin bin_rem[bi] -= weight[i]; } return res; } // Driver code var weight = [ 2, 5, 4, 7, 1, 3, 8 ]; var c = 10; var n = weight.length; document.write( "Number of bins required in Best Fit : " + bestFit(weight, n, c)); // This code contributed by gauravrajput1 </script> |
输出：
Number of bins required in Best Fit : 4
最佳拟合也可以通过使用自平衡二进制搜索树在O（n logn）时间内实现。 如果M是箱子的最佳数量，那么Best Fit不会使用超过170万个箱子。所以，最佳拟合与第一次拟合相同，在箱子数量上限方面优于下一次拟合。 4.最不适合： 这样做的目的是将下一个物品放在最不紧的地方，以平衡垃圾箱。也就是说，把它放进垃圾箱，这样就可以留下大部分的空间。
C++
// C++ program to find number of bins required using // Worst fit algorithm. #include <bits/stdc++.h> using namespace std; // Returns number of bins required using worst fit // online algorithm int worstFit( int weight[], int n, int c) { // Initialize result (Count of bins) int res = 0; // Create an array to store remaining space in bins // there can be at most n bins int bin_rem[n]; // Place items one by one for ( int i = 0; i < n; i++) { // Find the best bin that ca accommodate // weight[i] int j; // Initialize maximum space left and index // of worst bin int mx = -1, wi = 0; for (j = 0; j < res; j++) { if (bin_rem[j] >= weight[i] && bin_rem[j] - weight[i] > mx) { wi = j; mx = bin_rem[j] - weight[i]; } } // If no bin could accommodate weight[i], // create a new bin if (mx == -1) { bin_rem[res] = c - weight[i]; res++; } else // Assign the item to best bin bin_rem[wi] -= weight[i]; } return res; } // Driver program int main() { int weight[] = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = sizeof (weight) / sizeof (weight[0]); cout << "Number of bins required in Worst Fit : " << worstFit(weight, n, c); return 0; } // This code is contributed by gromperen |
JAVA
// Java program to find number of bins required using // Worst fit algorithm. class GFG { // Returns number of bins required using worst fit // online algorithm static int worstFit( int weight[], int n, int c) { // Initialize result (Count of bins) int res = 0 ; // Create an array to store remaining space in bins // there can be at most n bins int bin_rem[]= new int [n]; // Place items one by one for ( int i = 0 ; i < n; i++) { // Find the best bin that ca accommodate // weight[i] int j; // Initialize maximum space left and index // of worst bin int mx = - 1 , wi = 0 ; for (j = 0 ; j < res; j++) { if (bin_rem[j] >= weight[i] && bin_rem[j] - weight[i] > mx) { wi = j; mx = bin_rem[j] - weight[i]; } } // If no bin could accommodate weight[i], // create a new bin if (mx == - 1 ) { bin_rem[res] = c - weight[i]; res++; } else // Assign the item to best bin bin_rem[wi] -= weight[i]; } return res; } // Driver program public static void main(String[] args) { int weight[] = { 2 , 5 , 4 , 7 , 1 , 3 , 8 }; int c = 10 ; int n = weight.length; System.out.print( "Number of bins required in Worst Fit : " +worstFit(weight, n, c)); } } // This code is contributed by shivanisinghss2110 |
C#
// C# program to find number of bins required using // Worst fit algorithm. using System; class GFG { // Returns number of bins required using worst fit // online algorithm static int worstFit( int []weight, int n, int c) { // Initialize result (Count of bins) int res = 0; // Create an array to store remaining space in bins // there can be at most n bins int []bin_rem= new int [n]; // Place items one by one for ( int i = 0; i < n; i++) { // Find the best bin that ca accommodate // weight[i] int j; // Initialize maximum space left and index // of worst bin int mx = -1, wi = 0; for (j = 0; j < res; j++) { if (bin_rem[j] >= weight[i] && bin_rem[j] - weight[i] > mx) { wi = j; mx = bin_rem[j] - weight[i]; } } // If no bin could accommodate weight[i], // create a new bin if (mx == -1) { bin_rem[res] = c - weight[i]; res++; } else // Assign the item to best bin bin_rem[wi] -= weight[i]; } return res; } // Driver program public static void Main(String[] args) { int []weight = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = weight.Length; Console.Write( "Number of bins required in Worst Fit : " +worstFit(weight, n, c)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // javascript program to find number of bins required using // Worst fit algorithm. // Returns number of bins required using worst fit // online algorithm function worstFit( weight, n, c) { // Initialize result (Count of bins) var res = 0; // Create an array to store remaining space in bins // there can be at most n bins var bin_rem = Array(n).fill(0); // Place items one by one for ( var i = 0; i < n; i++) { // Find the best bin that ca accommodate // weight[i] var j; // Initialize maximum space left and index // of worst bin var mx = -1, wi = 0; for (j = 0; j < res; j++) { if (bin_rem[j] >= weight[i] && bin_rem[j] - weight[i] > mx) { wi = j; mx = bin_rem[j] - weight[i]; } } // If no bin could accommodate weight[i], // create a new bin if (mx == -1) { bin_rem[res] = c - weight[i]; res++; } else // Assign the item to best bin bin_rem[wi] -= weight[i]; } return res; } // Driver program var weight = [ 2, 5, 4, 7, 1, 3, 8 ]; var c = 10; var n = weight.length; document.write( "Number of bins required in Worst Fit : " +worstFit(weight, n, c)); // This code is contributed by shivanisinghss2110 </script> |
输出：
Number of bins required in Worst Fit : 4
最差拟合也可以通过使用自平衡二叉搜索树在O（n logn）时间内实现。 如果M是最佳的垃圾箱数量，那么Best Fit不会使用超过2M-2个垃圾箱。所以最差拟合和下一次拟合在箱子数量上限方面是一样的。 离线算法 在离线版本中，我们提前准备了所有项目。不幸的是离线版本也是NP完全的，但我们有一个更好的近似算法。如果最佳值为M，则First Fit Desculation最多使用（4M+1）/3个箱子。 4.第一次拟合： 在线算法的一个问题是，打包大型物品很困难，尤其是如果它们在序列中出现的较晚。我们可以通过对输入序列进行排序，并将大项目放在第一位来避免这种情况。通过排序，我们得到了First Fit Desculation和Best Fit Desculation，作为在线First Fit和Best Fit的离线类似物。
C++
// C++ program to find number of bins required using // First Fit Decreasing algorithm. #include <bits/stdc++.h> using namespace std; /* Copy firstFit() from above */ // Returns number of bins required using first fit // decreasing offline algorithm int firstFitDec( int weight[], int n, int c) { // First sort all weights in decreasing order sort(weight, weight + n, std::greater< int >()); // Now call first fit for sorted items return firstFit(weight, n, c); } // Driver program int main() { int weight[] = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = sizeof (weight) / sizeof (weight[0]); cout << "Number of bins required in First Fit " << "Decreasing : " << firstFitDec(weight, n, c); return 0; } |
JAVA
// Java program to find number of bins required using // First Fit Decreasing algorithm. import java.util.*; class GFG { /* Copy firstFit() from above */ // Returns number of bins required using first fit // decreasing offline algorithm static int firstFitDec(Integer weight[], int n, int c) { // First sort all weights in decreasing order Arrays.sort(weight, Collections.reverseOrder()); // Now call first fit for sorted items return firstFit(weight, n, c); } // Driver code public static void main(String[] args) { Integer weight[] = { 2 , 5 , 4 , 7 , 1 , 3 , 8 }; int c = 10 ; int n = weight.length; System.out.print( "Number of bins required in First Fit " + "Decreasing : " + firstFitDec(weight, n, c)); } } // This code is contributed by Rajput-Ji |
C#
// C# program to find number of bins required using // First Fit Decreasing algorithm. using System; public class GFG { /* Copy firstFit() from above */ // Returns number of bins required using first fit // decreasing offline algorithm static int firstFitDec( int []weight, int n, int c) { // First sort all weights in decreasing order Array.Sort(weight); Array.Reverse(weight); // Now call first fit for sorted items return firstFit(weight, n, c); } static int firstFit( int []weight, int n, int c) { // Initialize result (Count of bins) int res = 0; // Create an array to store remaining space in bins // there can be at most n bins int []bin_rem = new int [n]; // Place items one by one for ( int i = 0; i < n; i++) { // Find the first bin that can accommodate // weight[i] int j; for (j = 0; j < res; j++) { if (bin_rem[j] >= weight[i]) { bin_rem[j] = bin_rem[j] - weight[i]; break ; } } // If no bin could accommodate weight[i] if (j == res) { bin_rem[res] = c - weight[i]; res++; } } return res; } // Driver code public static void Main(String[] args) { int []weight = { 2, 5, 4, 7, 1, 3, 8 }; int c = 10; int n = weight.Length; Console.Write( "Number of bins required in First Fit " + "Decreasing : " + firstFitDec(weight, n, c)); } } // This code is contributed by 29AjayKumar |
输出：
Number of bins required in First Fit Decreasing : 3
First Fit Desculation为样本输入生成最佳结果，因为项目是先排序的。 首次拟合递减也可以通过使用自平衡二叉搜索树在O（n logn）时间内实现。 本文由 德埃拉吉·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
