求一组和等于'M‘的'N’数的有效一通算法？

Question

对于给定的问题陈述，什么是有效的算法？(java首选)

找出N个数的集合S，使得它们的和等于M。集合S中的每一个数必须在给定的偏差'D‘内，与平均M/N。

int M= 100;
int N= 10;
int D= 3;

这里的平均值M/N = 10。因此，当偏差为3时，N可以是{7,8,9,10,11,12,13}中的一个数。

结果必须类似于这一组：

11 11 9 8 11 11 11 9 10

在下面的节目里，我说到目前为止：

    public class RandomNumberGenerator {

    public static void main(String args[]) {
        Random r = new Random();
        int sum = 100;
        int numbers = 10;
        int deviation = 3;

        int iterator = 0;
        int sumTemp = 0;
        int storeArray[] = new int[numbers];
        int average = Math.round((float) sum / (float) numbers);
        int numberOfAttempts = 0;
        int discardedBecauseGreater = 0;
        System.out.println("Average is " + average);

        while (iterator < numbers) {
            int temp = r.nextInt(average + deviation);
            if (temp > average - deviation) {
                storeArray[iterator] = temp;
                sumTemp += temp;
                iterator++;
            }
            if (iterator == numbers) {
                if (sumTemp == sum) {
                    System.out.println("Got the result " + sumTemp);
                    System.out
                            .println("Number of attempts " + numberOfAttempts);
                    System.out.println("Discarded because of greater "
                            + discardedBecauseGreater);
                    for (int i = 0; i < numbers; i++) {
                        System.out.println(storeArray[i]);
                    }

                    break;
                } else {
                    numberOfAttempts++;
                    sumTemp = 0;
                    iterator = 0;
                }
            }

            if (sumTemp > sum) {
                discardedBecauseGreater++;
                sumTemp = 0;
                iterator = 0;
            }

        }
    }
}

Answer 1

我认为这个问题是一个变化/类似于注水问题。

拼图

您可以选择n个杯子，每个m{i}容量，以倒出所需的水量。

因此，选择"n“数字和为"m”。

您可以找到解决方案并将其裁剪到您的用例。

以下是一个可能的解决方案：

https://gist.github.com/setrar/77fc1c301266afde9f7f