C ++ How to find the minimum number of elements from a vector that sums with a given number

Question

I want to find the minimum number of elements from an array so that their sum is equal to the given number.

Answer 1

Looks like an easy dynamic programming task.

Suppose that there are N elements in array A, and you want to get the minimum number of elements whose sum is S. Then we can easily solve the problem with time complexity O (N x S).

Consider dp [i] [j] - the minimum number of elements among the first elements i, the sum of which is j, 1 <= i <= N and 0 <= j <= S. Then for A [i] <= j <= S :

dp [i] [j] = min (, dp [i - 1, j], 1 + dp [i - 1] [j - A [i]]).

, dp [0] [0] = 0, dp [0] [j] = 0 < j <= S.

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;
}

Answer 3

Try to sort it in ascending order, and while you repeat it, make a temporary amount into which you add each element until you reach the required amount. If, adding a new element, you go to the amount, continuing without adding the current element. Try something like this:

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;

Not the most elegant method or the most effective, but it should work