Week3 A - 选数问题

2023-12-15 03:48

文章标签 问题 week3 选数

本文主要是介绍Week3 A - 选数问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：
给定n个正数，从中选取K个数相加得到和sum，问有多少种选取法。

输入输出：

Input：第一个数T（T≤100）表示测试数据用例，对每一组测试数据，有两行数据，第一行数据表示数据个数n，选取数量K，累加和S，第二行是n个正数。

output：对每一组数据输出有多少种选取符合要求

解题思路：
此题可采取类似于全排列的思想，每个数据有两种选择，选或不选，达到条件的选取方法是，已选取的数据总数为K，且这K个数相加，和恰好为S。利用递归函数，传递参数i（表示数组第i个数)，目标累加和sum，以及已选取的数据总数length。当length>k，sum<0或者i>=n函数返回，此为可行性剪枝（继续遍历下去也是不符合条件的）。当length=k&&sum=0时，tot++（记录多少种选取方法满足条件）且函数返回。

实验代码：

#include<iostream>
using namespace std;int n,k,sum,tot=0;		//m为测试数据组数 
int a[16];
void solve1(int i,int sum,int length)
{if(length==k&&sum==0){tot++;return;}//搜索边界 if(i>=n)	return;//可行性剪枝if(length>k||sum<0)return;solve1(i+1,sum,length);		//不选solve1(i+1,sum-a[i],length+1);		//选		 
}
int main(void)
{int m;cin>>m;for(int i=0;i<m;i++){tot=0;cin>>n>>k>>sum;for(int i=0;i<n;i++)cin>>a[i];solve1(0,sum,0);cout<<tot<<endl;}return 0;		
}