C++如何找到向量中最少的元素，使它们的总和等于给定的数字

Question

我希望找到一个数组中元素数量最少的组合，使得它们的和等于给定的数字。

- C. Cristi

---

数组可以有负数吗？ - Millie Smith

这就像用C++解决世界和平与幸福问题。首先你找到一个解决方案，然后在C++中编写代码（这是容易的一步）。 - n. m.

听起来像是一项作业任务。至少要尝试一下。 - dmg

@dmg 我尝试过将它们从高到低排序，然后相加，但这不是正确的解决方案。 - C. Cristi

Answer 1

看起来是一道简单的动态规划问题。

假设数组 A 中有 N 个元素，您想要获得求和为 S 的最小元素数量。那么我们可以轻松地用时间复杂度为 O(N x S) 的方法解决这个问题。

考虑 dp[i][j] - 在前 i 个元素中求和为 j 的最小元素数量，其中 1 <= i <= N，0 <= j <= S。当 A[i] <= j <= S 时：

dp[i][j] = min(正无穷, dp[i - 1, j], 1 + dp[i - 1][j - A[i]])。

我们可以假设 dp[0][0] = 0，对于 0 < j <= S，dp[0][j] = 正无穷。

- Edgar Rokjān

---

@M.Alaggan，你认为我们不能用动态规划来解决NP难题，是吗？ - Edgar Rokjān

你的公式需要改进以考虑和为负数的情况。 - AndyG

我感觉你正在描述这个伪多项式时间解决子集和问题的方案。链接 - AndyG

@AndyG 这是子集和问题的某种变体。你完全正确，如果存在负数和的情况，这个解决方案应该稍作修改。 - Edgar Rokjān

Answer 2

最简单的方法是通过递归来解决它。

find_sum(goal, sorted_list) {
    int best_result = infinity;
   for each (remaining_largest : sorted_list){
    result = find_sum(goal - remaining_largest, sorted_list_without_remaining_largest) + 1;
    if result < best_result then best_result = result;
  }
  return best_result;
}

有许多方法可以优化这个算法，可能还有更好的基本算法，但我试图保持它非常简单。

一种优化方法是将到达给定数字的最佳组合存储在哈希表中。天真的算法与递归斐波那契求解器遇到相同问题，即不断重新解决重复的子问题。

我实际上还没有运行过这个算法：

#include <vector>
#include <map>
using namespace std;
  // value, num values to sum for value
  map<int,int> cache;

// returns -1 on no result, >= 0 is found result
int find(int goal, vector<int> sorted_list, int starting_position = 0) {

  // recursive base case
  if (goal== 0) return 0;

  // check the cache as to not re-compute solved sub-problems
  auto cache_result = cache.find(goal);
  if (cache_result != cache.end()) {
   return cache_result->second;


    // find the best possibility
    int best_result = -1;
    for (int i = starting_position; i < sorted_list.size(); i++) {
         if (sorted_list[starting_position] <= goal) {
            auto maybe_result = find(goal- sorted_list[starting_position], sorted_list, i++); 
            if (maybe_result >= 0 && maybe_result < best_result) {
                best_result = maybe_result + 1;
            }
        }
    }

    // cache the computed result so it can be re-used if needed
    cache[goal] = best_result;

    return best_result;
}

- xaxxon

---

如何将“for each”转换为简单的“for”？ - C. Cristi

@C.Cristi 我写了一些可能有效的 C++ 代码，但我还没有机会运行它。 - xaxxon

Answer 3

尝试按升序排序，同时在迭代过程中创建一个临时总和，在达到所需总和之前将每个元素相加。如果通过添加新元素超过总和，则继续而不添加当前元素。可以尝试以下类似的方法：

for(i=0;i<nr_elem;i++)
  minimum = 0;
  temp_sum=0;
  for(j=0;j<nr_elem;j++){
     if(temp_sum + elem[j] > req_sum)
         *ignore*
     else
         temp_sum+=elem[j];
         minimum+=1;}
  if(global_min < minimum)
      global_min = minimum;

不是最优雅的方法，也不是最高效的方法，但它应该能工作。

- Scurtu

---

7、6、4、3，目标是14——你的算法失败了，答案是3。 - xaxxon