SYZOJ — [機智]毒瘤背包(01背包)

題目連結: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

樣例輸出

資料範圍與提示

解題思路

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