使用动态规划,我必须找到一个有效的算法来解决以下问题:
作为输入,我们接收一个大小为N
的随机数数组,其中int k
是所选数字之间的最小距离,而int n
是我们必须选择的数字总数。
问题的目标是找出所选数字的最小可能和。
我不知道如何解决这个问题。
例如,如果我们有以下数组:
arr = [5, 5, 3, 3, 2, 2, 3, 3, 5, 5, 5, 5, 5, 3, 2, 5]
N = 16
k = 4
n = 3
通过选择索引2、7和14处的数字,输出将
n
。 最佳答案
我已经用c++编写了解决方案,代码大部分是可读的,但是如果您在理解过程中有任何歧义,请在下面进行注释。
#include<iostream>
#include<vector>
using namespace std;
int number_of_elements_to_be_picked, number_of_elements, k;
int main(){
cin >> number_of_elements >> k >> number_of_elements_to_be_picked;
vector<int> a(number_of_elements);
vector<vector<int> > store(number_of_elements, vector<int> (number_of_elements_to_be_picked+1));
for(int i = 0; i < number_of_elements; i++){
cin >> a[i];
store[i][1] = a[i];
}
for(int i = 0; i < number_of_elements; i++){
for(int j = 2; j <= number_of_elements_to_be_picked; j++){
if(i == k*(j-1))
store[i][j] = store[i-k][j-1]+a[i];
else if(i > k*(j-1))
store[i][j] = min(store[i-k][j-1]+a[i], store[i-1][j]);
}
}
cout << store[number_of_elements-1][number_of_elements_to_be_picked] << "\n";
return 0;
}
编辑:根据作者的注释,我的变量命名不正确:-
N=元素个数,N=要选取的元素个数,k=k
关于java - 大小为N的给定数组之间的k个空格之间的n个数字的最小和,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/55485123/