【算法】选择元素个数最少解算法(C++源码)

时间:2022-10-18 07:22:34


【算法】选择元素个数最少解算法(C++源码)

一、任务描述

给定若干个正整数a0、a1、….、an-1,从中选出若干个数,使它们的和恰好为k,要求找出选择元素个数最少的解。要求:
1、选取一组正整数以及k测试所设计的算法
2、设计相应的剪枝函数,对上述算法进行优化

二、步骤描述

求子集和问题的解:
(1)定义两个全局数组,a数组为符合条件的数存储,b数组负责判断是否符合条件和最优解;
(2)在主函数中输入数组的大小n,目标和k,以及数组的各元素,最终输出最优解。

三、运行结果截图

【算法】选择元素个数最少解算法(C++源码)


【算法】选择元素个数最少解算法(C++源码)


【算法】选择元素个数最少解算法(C++源码)

四、源代码(C++)

#include<iostream>

using namespace std;

int n,k,a[25],b[25];

int dfs(int i,int sum)
{
if(sum>k)
{
return 0;
}
if(i==n)
{
return sum==k;
}
if(dfs(i+1,sum))
{
b[i]=0;
return 1;
}
if(dfs(i+1,sum+a[i]))
{
b[i]=1;
return 1;
}
return 0;
}

int main()
{
cout<<"Please enter the 'length of the array' and 'the target sum' :";
cin>>n>>k;
cout<<"Please enter an array of length :"<<n<<endl;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
if(dfs(0,0))
{
cout<<"The result is YES!"<<endl;
for(int i=0;i<n;i++)
{
if(b[i])
{
cout<<a[i]<<" ";
}
}
cout<<endl;
}
else
{
cout<<"The result is NO!"<<endl;
}
return 0;
}