ZOJ 3631 Watashi's BG(01dp)

01dp不过由于数组过于大,开不开,学了搜索过了,先记录下 还有一种方法

#include<stdio.h>
#include<algorithm>
using namespace std;

const int MAXN=10000010;
int a[MAXN];
int n,m,ans;

bool cmp(int a,int b)
{
    return a>b;
}

int max(int a,int b)
{
    return a>b?a:b;
}

void DFS(int s,int num)
{
    if(s>m) return ;
    if(num>=n) //
    {
        ans=max(s,ans);
        return ;
    }    
    int temp=s;
    for (int i=num;i<n;i++)//若后面的所有数都加进去还比最大的小,就不用比较了
        temp+=a[i];
    if(temp<ans) return;
    /*01背包的精髓,放与不放*/
    DFS(s+a[num],num+1);
    DFS(s,num+1);
}

int main()
{
    
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ans=0;
        for (int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n,cmp);//剪枝
        DFS(0,0);
        printf("%d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GIS讲堂

ArcGIS Image Server简介以及OL2中的加载

本文讲述Arcgis Image Server相关以及在OL2中如何加载Arcgis Server发布的影像服务。

12620
来自专栏一棹烟波

ffmpeg中avframe的YUV格式数据到OpenCV中Mat的BGR格式转换

ffmpeg实现音视频编解码是非常常用的工具,视频解码出来的raw数据是yuv格式,用来进行后续的图像处理一般是RGB格式的。所以需要从yuv到rgb或者bgr...

48790
来自专栏Python小屋

Python两种方法求解登楼梯问题(京东2016笔试题)

问题:假设一段楼梯共15个台阶,小明一步最多能上3个台阶,那么小明上这段楼梯一共有多少种方法? 解析:从第15个台阶上往回看,有3种方法可以上来(从第14个台阶...

47490
来自专栏一棹烟波

NV12格式转RGB的CUDA实现

NV12格式是yuv420格式的一种,NV12格式的u,v排布顺序为交错排布,假如一幅图像尺寸为W*H,则先Y分量有W*H个,然后U分量和V分量交错排布,U分...

60190
来自专栏开发与安全

数据结构:图的存储结构之邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息...

70180
来自专栏用户2442861的专栏

Python-OpenCV 处理图像(二):滤镜和图像运算

喜欢自拍的人肯定都知道滤镜了,下面代码尝试使用一些简单的滤镜,包括图片的平滑处理、灰度化、二值化等:

24410
来自专栏xingoo, 一个梦想做发明家的程序员

n后问题-回溯法

问题描述:   在n*n的棋盘上放置彼此不受攻击的n个皇后。按国际象棋的规则,皇后可以与之处在同一行或者同一列或同一斜线上的棋子。   n后问题等价于在n*n格...

19260
来自专栏空间大数据可视化

GIS基础算法之Kruskal算法(2015.10.15)

12850
来自专栏HansBug's Lab

算法模板——单个值欧拉函数

输入N,输出phi(N) 这样的单个值欧拉函数程序一般见于部分数论题,以及有时候求逆元且取模的数不是质数的情况(逆元:A/B=A*Bphi(p)-1 (mod ...

35850
来自专栏专知

【代码资源】GAN | 七份最热GAN文章及代码分享(Github 1000+Stars)

【导读】专知团队整理了七份当前最热的GAN相关文章和代码,每篇文章代码均在Github上开源,Stars数量超1000+。

16260

扫码关注云+社区

领取腾讯云代金券