本文共 744 字，大约阅读时间需要 2 分钟。

题目链接:

题目描述

现在有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背包。

#include 
   
    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;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/91046487 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！