codevs——1570 去看电影
2024-08-29 23:38:38
题目描述 Description
农夫约翰带着他的一些奶牛去看电影。而他的卡车最多只能载重C(100<=C<=5000)
公斤,总体上来说,他想在不超过限制的前提下尽可能多地带走牛。
给出N (1 <= N <= 16)头奶牛的体重W_i,计算约翰可以带去看电影的奶牛的最大
重量。
输入描述 Input Description
* 第 1 行: 2个用空格隔开的整数 C , N
* 第 2 至 N+1 行: 分别表示每头奶牛的体重 W_i
输出描述 Output Description
* 一个整数,表示可以带去看电影的奶牛的最大重量
样例输入 Sample Input
259 5
81
58
42
33
61
样例输出 Sample Output
242
数据范围及提示 Data Size & Hint
81+58+42+61 = 242; 这个是最大重量
简单明了的01背包
不过,用搜索怎么做???
我们分为两种情况来讨论,一种是选当前牛,一种是不选。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 50 using namespace std; ]; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } int main() { zv=read(),n=read(); ;i<=n;i++) v[i]=read(); ;i<=n;i++) ;j--) if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+v[i]); printf("%d",f[zv]); ; }
01背包
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 50 using namespace std; int zv,n,v[N],ans; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } void dfs(int now,int sum) { ) { ans=max(ans,sum); return; } dfs(now+,sum); if(sum+v[now]<=zv) dfs(now+,sum+v[now]); } int main() { zv=read(),n=read(); ;i<=n;i++) v[i]=read(); dfs(,); printf("%d",ans); ; }
最新文章
- WCF学习笔记一
- jquery中select的应用
- sql server 执行计划(execution plan)介绍
- bootstrap-datetimepicker.js 设置开始时间的Bug。
- Qt之QHeaderView自定义排序(获取正确的QModelIndex)
- 解析XML文档之三:使用DOM解析
- 修改netbeans模版头部的说明
- hdu2066一个人的旅行(dijkstra)
- Leetcode:minimum_depth_of_binary_tree解决问题的方法
- javascript dom页面中的location属性
- 关于Android 8.0java.lang.SecurityException: Permission Denial错误的解决方法
- Eclipse安装lombok及常用注解
- JAVA首次课堂测试总结
- 同时执行多个$.getJSON() 数据混乱的问题的解决
- PRTG安装
- spark快速开发之scala基础之2控制流程
- 我常用的 Python 调试工具 - 博客 - 伯乐在线
- PHP获取文件大小详解
- CentOS 6.0 VNC远程桌面配置方法(转帖)
- How to put a relative path for a DLL statically loaded?