dp

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
bitset<N> f;
int n, c, x;
int main() {
	cin >> n >> c, f[0] = 1;
	for (int i = 1; i <= n; i ++)
		cin >> x, f |= f << x;
	for (int i = c; ; i --)
		if (f[i]) cout << i << '\n', exit(0);
	return 0;
}

dfs(c++11)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N=45;
int cnt,res,n,m,a[N];
bool vis[N];
inline void dfs(int x) {
	if(res==m)
		return ;
	for(register int i=1;i<=n;++i) {
		if(!vis[i] && cnt+a[i]<=m) {
			cnt+=a[i];
			vis[i]=true;
			res=max(res,cnt);
			dfs(x+1);
			cnt-=a[i];
			vis[i]=false;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(register int i=1;i<=n;++i)
		cin>>a[i],cnt+=a[i];
	if(cnt<=m)
		return cout<<cnt<<endl,0;
	cnt=0;
	sort(a+1,a+1+n,[&] (int x,int y){
		return x>y;
	});//从大到小排序
	dfs(1);
	cout<<res;
	return 0;
}

01背包

#include<bits/stdc++.h>
using namespace std;
long n,m,i,j,b[20005],a[20005],f[20005];
int main()
{
	cin>>n>>m;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n;i++)
		for(j=m;j>=a[i];j--)
			f[j]=max(f[j],f[j-a[i]]+a[i]);
	cout<<f[m];
	return 0;
}