c++ 平分石头

平分石头

题目描述

给你N颗石头，给出N（0 < N < 200），M( 0 < M < 10000)，和N颗石头的质量，质量为不超过300的整数，问从中拿出若干块石头质量和与M最接近，输出石头的质量和。

输入

第一行输入两个整数N和M；

接下来N行，输入N颗石头的质量。

输出

输出最后的结果

样例输入

5 10
1
2
3
4
5

样例输出

10

AC代码

//
//  main.cpp
//  noip
//
//  Created by fengyanhua on 2019/8/31.
//  Copyright © 2019年 fengyanhua. All rights reserved.
//

#include <iostream>
using namespace std;
#define MAX 201
int deta,ans,t[MAX],a[MAX],s,m,n;
void dfs(int u,int s)// u表示要选择的数为a[u] s表示在选a[u]之前的所有数的和
{
    cout<<u<<" ";
    cout<<s<<endl;
    
    if(abs(s-m)<deta)//求离m最近的数
    {
        deta=abs(s-m);//deta为s与10相差多少
        ans=s;//s即为要求的数
        cout<<"s: "<<s<<endl;
    }
    if(u>n) return;//u>n表示选择的是这五个数以外的数 如a[6]
    if(s-m>deta) return;//s(超过10时)不是离m最近的数时不用再向前选数
    if(s+t[n]-t[u-1]<m-deta) return;//表示如果加上元素 u 到 n 的和，依然比当前最优方案距离 m 要远，就舍弃掉它
    dfs(u+1,s+a[u]);//选择下一个数a[u+1]，s+a[u]：表示选a[u+1]之前所有的数的和，满足条件 就一直选择下一个数，不满足就返回
    dfs(u+1,s);//回退到上一次的选择，此处需要回退两次
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);//将5个数存入数组
        t[i]=t[i-1]+a[i];//t[i]存储前i个数的和
    }
    deta=m;// s是离m的距离，初始没有选择数  s=0  所以离m的距离为m
    dfs(1,0);//选择第a[1]个数  s表示选择a[1]之前的所有数的和
    cout<<ans<<endl;
    return 0;
}