如何从向量中求和到给定数目的元素的最小数目 [英] c++ How to find the minimum number of elements from a vector that sum to a given number

问题描述

我想从数组中查找其总和等于给定数目的最小元素。

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

推荐答案

看起来像一个简单的动态编程任务。

Looks like an easy dynamic programming task.

假设数组 A 中有 N 个元素，以获得最小数量的元素，其总和为 S 。然后我们可以轻松地解决 O（N x S）时间复杂度的问题。

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

考虑 dp [i] [j] -第一个 i 个元素中的最小元素个数之和为 j ， 1< = i< = N 和 0< = j< = S 。然后对于 A [i]< = j< = S ：

Consider dp[i][j] - the minimum number of elements among first i elements which sum 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]]）。

我们可以假设 0< dp [0] [0] = 0 ， dp [0] [j] =无限。 j< = S 。

We can assume that dp[0][0] = 0, dp[0][j] = infinity for 0 < j <= S.

这篇关于如何从向量中求和到给定数目的元素的最小数目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！