题目描述 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);
;
}