牛客在线编程_牛牛的背包问题

题目地址

给n个物品的体积和背包的总容量，问能装下的方案数。

• 搜索+剪枝，当剩余容量小于后缀最小值时直接返回1，即全不选，当剩余容量大于后缀和时直接返回1<<len。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=32;
int n;
ll w,v[N],mn[N],suf[N];
ll dfs(int idx,ll rem){
    if(rem<mn[idx]){
        return 1;
    }
    if(rem>=suf[idx]){
        return 1ll<<n-idx+1;
    }
    if(idx==n){
        if(rem>=v[idx]){
            return 2;
        }else{
            return 1;
        }
    }
    ll ans=0;
    if(rem>=v[idx]){
        ans+=dfs(idx+1,rem-v[idx]);
    }
    ans+=dfs(idx+1,rem);
    return ans;
}
int main(){
    scanf("%d%lld",&n,&w);
    for(int i=1;i<=n;i++){
        scanf("%lld",&v[i]);
    }
    mn[n+1]=0x3f3f3f3f;
    for(int i=n;i>=1;i--){
        mn[i]=min(mn[i+1],v[i]);
        suf[i]=suf[i+1]+v[i];
    }
    ll ans=dfs(1,w);
    printf("%lld\n",ans);
    return 0;
}