dfs算法选择k个数使和为m元素平方和最大

dfs算法应用，n个元素中选择k个数，使其和为m，并且每个元素的平方和最大

1. 原文

输入n,m,k。分别为数组个数，选择的数之和，选择的元素个数。

4 6 2
2 3 3 4

2. 解析思路

分为选index号元素的 dfs(idx+1,cnt+1,sum+num[idx],squ+num[idx]*num[idx]);

和不选择index号的dfs(idx+1,cnt,sum,squ);

当元素个数为k，和为m，比较选择最大的平方和保留

tempath只有在选择index号时才加入num[index]，而后及时剔除，以免影响不选index号的分支

3. 代码

#include<cstdio>
#include<vector>
using namespace std;
vector<int> tempath,path;
int num[100010];
int n,m,k;
int maxsqu = -1;
void dfs(int idx,int cnt,int sum,int squ){
	if (cnt==k&&sum==m)
	{
		if (squ>maxsqu)
		{
			maxsqu=squ;
			path = tempath;
		}
		return;
	}
	if (idx==n||cnt>k||sum>m)
	{
		return;
	}
	tempath.push_back(num[idx]);
	dfs(idx+1,cnt+1,sum+num[idx],squ+num[idx]*num[idx]);
	tempath.pop_back();

	dfs(idx+1,cnt,sum,squ);
}
int main(){
	freopen("A0000.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d",&num[i]);
	}
	dfs(0,0,0,0);
	for (int i = 0; i < path.size(); ++i)
	{
		if (i!=0)
		{
			printf(" ");
		}
		printf("%d",path[i]);
	}
	printf("\n");
	return 0;
}