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

站长

发表文章数:3062

Elastcisearch.Nest 7.x 系列`伪`官方翻译:通过 NEST 来快捷试用 Elasticsearch

题目地址

shell 条件测试

给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;
}

java8 stream自定义分组求和并排序

未经允许不得转载:www.xssyun.com作者:站长, 转载或复制请以 超链接形式 并注明出处 xss云之家-资源网,新人技术交流平台,一个湖北娃的个人博客
原文地址:《牛客在线编程_牛牛的背包问题》 发布于2020-01-24

分享到:
赞(0) 生成海报

长按图片转发给朋友

投稿赚钱
2020年在家赚取零花钱
切换注册

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录
切换登录

注册