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

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

• ​​一、任务描述​​
• ​​二、步骤描述​​
• ​​三、运行结果截图​​
• ​​四、源代码（C++）​​

一、任务描述

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

二、步骤描述

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

三、运行结果截图

四、源代码（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;
}