首页 > 代码库 > Codevs 1570 去看电影
Codevs 1570 去看电影
1570 去看电影
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 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; 这个是最大重量
#include<iostream>#include<cstdio>using namespace std;int n,m,w[20],ans;bool vis[20];void dfs(int x,int sum){ if(x==n+1){ ans=max(ans,sum); return; } if(sum+w[x]<=m)dfs(x+1,sum+w[x]); dfs(x+1,sum);}int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++)scanf("%d",&w[i]); dfs(1,0); printf("%d",ans);}
#include<iostream>#include<cstdio>using namespace std;int n,m,dp[80010],w[20];int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+w[i]); printf("%d",dp[m]);}
Codevs 1570 去看电影
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。