javascript - 为k人切割n个蛋糕，浪费最少

给定一个半径为n个蛋糕的数组，以及一个表示您需要多少人（或切片）的整数（k），您可以用最少的浪费从蛋糕上切下的最大面积是多少？
数学不是我的强项，所以我很难精确地指出我需要使用的算法，以便每次都得到正确的面积我试着对半径进行排序，然后将最大区域除以2，直到它小于下一个区域，但这并不能给出一致的结果。
我就在这里：

  // get areas of each cake
  const pi = 3.14159265359;
  let areas = [];
  let size;

  radii.sort(function(a, b){return a - b});

  for (let i = 0; i < radii.length; i++) {
    areas.push(pi * radii[i] * radii[i]);
  }
  // divide largest in half
  for (let i = areas.length-1; i > 0; i--) {
    if (areas[areas.length-1] / 2 < areas[i-1]) {
    }
  }
  // if that number is smaller than the next smallest cake
  // and you can get 6 equal pieces
    // size = largest cake area / 2
  // if you cannot get 6 equal pieces
    // divide the largest cake area by 4
    // check that that number can fit into the next cakes
    // until there are 6 pieces - size = largest cake / 4
};```

input: [1,1,1,2,2,3],6
Expected output: 7.0686

input: [1,5],5
Expected output: 15.7079

最佳答案

好的，所以我提出的解决方案基本上是一个贪婪的算法，它跟踪每个蛋糕应该取多少片，然后在下一个尝试找出最好的蛋糕添加一片。
我用来判断哪个蛋糕最好的方法是问一个问题，如果我要和其他蛋糕一起分享的话，哪个蛋糕可能有最大的一块蛋糕然后我会在蛋糕上加一片。
除此之外，我们还需要跟踪最小切片大小，因为所有切片的大小都必须相等。
不管怎样，这是算法希望这有帮助:)

function findBiggestSlice(areas){
    let index = 0
    let largestSlice = 0
    for(let i = 0; i < areas.length; i++){
        let sliceSize = areas[i].total/(areas[i].slices + 1)
        if(sliceSize > largestSlice){
            index = i
            largestSlice = sliceSize
        }
    }
    return index
}

function nCakeskSlices(radii, slices){
    // get areas of each cake
    const pi = 3.14159265359;
    let areas = [];
    let sliceSize = Infinity;

    radii.sort(function(a, b){return a - b});

    for (let i = 0; i < radii.length; i++) {
        totalArea = pi * radii[i] * radii[i];
        areas.push({
            'total': totalArea,
            'slices': 0,
        });
    }

    for(let person = 0; person < slices; person++){
        sliceCakeIndex = findBiggestSlice(areas)
        areas[sliceCakeIndex].slices += 1;
        newSliceSize = areas[sliceCakeIndex].total/(areas[sliceCakeIndex].slices)
        sliceSize = Math.min(newSliceSize, sliceSize);
    }

    return sliceSize
};

关于javascript - 为k人切割n个蛋糕，浪费最少，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57128066/