题目链接:https://syzoj.com/problem/110
内存限制：512 MiB 时间限制：1000 ms

题目描述

现在有n个物品，每个物品都有他的编号，从0开始0..n-1。他们都有各自对应的体积v(i)。现在要把这n个物品尝试着放入一个体积为V的容器中，请问最多能放进去的体积之和是多少？

输入格式

第一行2个整数n，V，表示共有n个物品，容器体积为V

第二行n个整数，表示v(0)..v(n-1)

输出格式

一行，一个整数，表示装进去的体积的最大和

样例输入

2 4294967296
2147483648 233

样例输出

2147483881

数据范围与提示

2 <= n <= 20
2^31 <= v(i), V <= 2^40

解题思路

01背包问题，为体积过大，数量较小，可以直接递归求01背包。
Accepted Code:

#include <bits/stdc++.h>
using namespace std;
long long v[25];
long long dp(int n, long long m) {
    if (n < 1)
        return 0;
    if (v[n] > m)
        return dp(n - 1, m);
    return max(dp(n - 1, m), dp(n - 1, m - v[n]) + v[n]);
}
int main() {
    int n;
    long long m;
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &v[i]);
    printf("%lld\n", dp(n, m));
    return 0;
}