2024.4.24 民生科技笔试题目

25道选择题

2道编程题

第一道是字符串排序

小红准备购买一些基金，共有n个基金，第i个基金的收益为ai，由于精力所限，小红最多选择k个基金，
她想直到有多少种不同的选择方案可以满足总收益不低于x? 
第一行三个正整数 n k x 
第二行输入n个正整数代表基金的收益 
比如输入： 
4 3 10  
1 3 5 7  
输出为5 
说明 选择两个基金的方案： [3,7] 和【5，7】
三个基金的方案 【3，5，7】 【1 3 7】 【1 5 7】

输入：
3 2 6
3 3 3
输出：
3
*/
//解题思路：使用递归回溯的方式排列组合解题
#include<iostream>
#include<vector>

using namespace std;
//结果的个数
int result = 0;
//回溯的参数 包括 数组， k选择几个基金， target 目标是多少（终止回溯递归的条件），sum(当前回溯分支的收益总和)，startIndex（当前遍历到数组的位置）
void backtracking(vector<int> &cadinate, int k, int target, int sum, int startIndex){
    if(k==0){//根据题意 当k=3 的时候 如果收益满足题意，也可以获得一种方案
        if(sum>=target){
            result++;
        }
        return;
    }
    else{ // 或者k==2 k==1 
        if(sum>=target){
            result++;
        }
    }
    for(int i=startIndex; i<cadinate.size(); i++){
        sum+=cadinate[i];
        backtracking(cadinate, k-1, target, sum, i+1);//注意这里不能使用k--否则k的值一直不变 可以使用--k
        sum-=cadinate[i];//回溯
    }
}
int main(){
    int n,k,x;
    cin>>n>>k>>x;
    vector<int> v;
    while(n--){
        int l;
        cin>>l;
        v.push_back(l);
    }
    backtracking(v, k, x, 0, 0); //初始值
    cout<<result;
    return 0;
}