Csharp 无浪费地找到最适合多件的算法

我建议保留一个数据 struct 来保存所有结果数据，这样就不必保持两个数据 struct 对齐.

此外，我建议使用类似List或类似的数据 struct ，因为它比数组更灵活.你不知道，一个箱子里会有多少个箱子，有多少东西.因此，分配不可调整大小的数组可能不是最好的方法，因为您要么必须使它们足够大以容纳所有元素(并且浪费大量内存)，要么总是必须判断它们的大小并在必要时重新分配.

此外，正如 comments 中所解释的那样，我建议将降下来的物品分类，然后再将它们分配到垃圾箱中，因为这样一来，无法放入一个垃圾箱的重物品将首先被分发，然后轻物品可以用来填补剩余的缺口.如果你先分发轻物品，它们会被紧紧地塞进最初的几个垃圾桶里.然后，每个沉重的物品都需要一个垃圾箱，留下大量未使用的容量.

有关该方法的简单实现，请参阅以下代码

//the default capacity of an empty bin
private static in CAPACITY = 3000;

//this is the structure that will represent a single bin, exposing the
//remaining capacity and the items currently contained
class Bin {
    public int capacityLeft {get; set;}
    public List<int> items { get; set;}
}

//alternatively you can also pass an int[] here
//doesn't make any difference
static List<Bin> distributeItems(List<int> items) {
  //create new result list of bins
  var result = new List<Bin>(); 
  //sort the items according to comments above
  //try also just with OrderBy(x => x) to sort ascending and see
  //the effect on the result
  var sortedItems = items.OrderByDescending(x => x);
    
  foreach (var x in sortedItems) {
      if (x > CAPACITY) {
          //skip items that are too heavy, or throw an error if you want
          //throw new Error($"item {x} is too heavy");
          continue; 
      }

      //the smallest remaining capacity so far
      var min = CAPACITY + 1;
      //the index of the bin where to put the current item to
      var index = result.Count;

      //check through all existing bins
      //for the first item, this list will be empty, so the loop's body
      //won't be executed at all
      for (int i = 0; i < result.Count; i++) {
          //does the current bin have enough capacity left
          //and is that remaining capacity minimal?
          if (result[i].capacityLeft >= x && result[i].capacityLeft < min) {
              //define the current bin to be the target for the item
              min = result[i].capacityLeft;
              index = i;
          }
      }
      
      //if no fitting bin was found, index will still be result.Count
      //ie pointing "after" the last element in the result list.
      //this also works for the empty list, as result.Count == index == 0
      //if thats the case, append a new empty bin to the result
      if (index == result.Count) {
          result.Add(new Bin{capacityLeft = CAPACITY, items = new List<int>()});
      }
      
      //put the current item in the respective bin (either the one found
      //in the loop, or the one newly added to the list)
      result[index].capacityLeft -= x;
      result[index].items.Add(x);
  }
    
  return result;
}

另请参阅此fiddle以获取完整的工作示例...