题目

我一开始的错误写法

#include <bits/stdc++.h>
using namespace std;


const int N=1007;
int res[N];
int n;
int ans;
int a[N];
int c;
int curw;

void dfs(int u)
{
    if(curw<=c) ans=max(ans,curw);
    if(u==n){
        //没得再往深度递归了
        return ;
    }

    //第u个砝码不选
    dfs(u+1);

    //这里存在错误!!!!!!!!
    //第u个砝码选
    curw+=a[u];
    if(curw>c) return; //对于第u层的，我选上后，判断如果超过c了，直接返回了，那么第u个物品的重量在次之后就会一直存在，没有减去
    dfs(u+1);
    curw-=a[u];
}

int main()
{
    scanf("%d%d",&n,&c);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    dfs(0);
    printf("%d\n",ans);
    return 0;
}

对这一部分修改后的写法

这个提交后，百分之六十正确了，百分之四十TLE了

#include <bits/stdc++.h>
using namespace std;


const int N=1007;
int res[N];
int n;
int ans;
int a[N];
int c;
int curw;

void dfs(int u)
{
    if(curw<=c) ans=max(ans,curw);
    if(u==n){
        //没得再往深度递归了
        return ;
    }

    //第u个砝码不选
    dfs(u+1);

    //这里存在错误
    /*//第u个砝码选
    curw+=a[u];
    if(curw>c) return; //对于第u层的，我选上后，判断如果超过c了，直接返回了，那么第u个物品的重量在次之后就会一直存在，没有减去
    dfs(u+1);
    curw-=a[u];*/

    //正确写法
    if(curw+a[u]<=c){
        curw+=a[u];
        dfs(u+1);
        curw-=a[u];
    }
}

int main()
{
    scanf("%d%d",&n,&c);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    dfs(0);
    printf("%d\n",ans);
    return 0;
}

两个优化后全部ac了

注意开long long
理解优化1的操作，导致优化2有可能实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1007;
int n;
ll ans;
int a[N];
ll c;
ll curw;
ll sum[N];//如果没开long long，会超界，导致答案错误WA！！！


void dfs(int u)
{
    if(curw<=c) ans=max(ans,curw);//我把这个max选择放到这里了
    if(u==n){
        //没得再往深度递归了
        return ;
    }

    //优化2！！！！！
    //如果当前的总重量curw+剩下的所有砝码都选的重量都<=c
    //那么直接在这里一次性全部选走（对ans取个max，return），一锅端走
    //不用在剩下的砝码一个个地选了
    if(curw+sum[u]<=c){
        //这里没有改动到curw，只是对ans取了大值
        //所以return到u-1层时，依旧是当时的curw
        ans=max(ans,curw+sum[u]);
        return;
    }

    //第u个砝码不选
    dfs(u+1);
    //第u个砝码选
    if(curw+a[u]<=c){
        curw+=a[u];
        dfs(u+1);
        curw-=a[u];
    }
}

int main()
{
    scanf("%d%d",&n,&c);
    //优化1
    //原本的数是从小到大输入
    //但是存的时候从大到小存
    //也就是遍历的时候，先遍历大的砝码（因为要求的是最大值）
    for(int i=n-1;i>=0;i--) scanf("%d",&a[i]);
    for(int i=n-1;i>=0;i--) sum[i]=sum[i+1]+a[i];//前缀和
    dfs(0);
    printf("%lld\n",ans);
    return 0;
}