java - 添加整数但选择最接近我想要的数字

Question

我正坐在这里尝试完成这项任务。
( https://open.kattis.com/problems/walrusweights )

The first input contains the number of plates I should use (ints).
The ints after are the plates (weights) and each of them should be <= than 1000.
Add the ints together and try come so close to 1000 as possible, BUT
in case there exist two such numbers which are equally close to 1000, (998 and 1002) then choose the greater one.

假设我有 4 个盘子，第一个是 4、900、500、498。
添加它们，以便您尽可能接近 1000。 498+500 = 998.
500+498+4=1002.
在本例中，选择 1002。

int sum=0;
 Scanner scan = new Scanner(System.in);
 int count = scan.next();
 for(int i = 0; i < count; i++)
 {
   sum = sum + scan.next();
 }

或

Scanner scan = new Scanner(System.in);
int count = scan.nextInt();

while(count > 0) {
//your logic
count--;
}

我试过但不明白如何比较相加数字的逻辑/算法，如果它们相等，则选择较大的一个。 我得到的只是我可以放入计数器和权重，它会把它加起来，有人能解释一下如何制作算法吗？我应该阅读什么来理解这一点？

谢谢。

Answer 1

这是一个动态规划问题，如果您不熟悉这种方法，首先要用 Google 搜索。此任务的想法是创建一个大小为 2001 的数组 A(请注意，任何可能的答案都小于或等于 2000)。最初，A[0] = true 并且对于所有其他索引 A[i] = false。然后，对于每个盘子，您从 1000 向下迭代到 0，如果 A[i] == true 则 A[i + currentWeight] = true。通过这种方式，您可以计算出您的盘子可以获得哪些总重量。最后，您找到索引 x 使得 A[x] == true 和 (x - 1000) 尽可能小(在平局的情况下，你取最大的 x)。