装箱问题

题目描述

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

$n\leq 30$，$0\leq V\leq 20000$。

分析

由于$n$非常小，可以尝试用穷举的方法计算每种情况。但是最坏情况下的时间复杂度大致为$O(10^9)$，这个会直接TLE。不过确实是一种求法啦^ _ ^。

但实际上，这就是一个01背包问题（zht学了还是不会写唉），是个带有体积限制和物品有其价值（也就是体积）的背包。并不是一个直观上的一维函数可以解决的背包。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 31, M = 20001;
int n, v;
int f[N][M];
int a[N];
int main() {
    scanf("%d%d", &v, &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= v; ++j) {
            f[i][j] = max(f[i][j], f[i-1][j]);
            if(a[i] <= j) f[i][j] = max(f[i][j], f[i-1][j-a[i]] + a[i]);
        }
    }
    printf("%d", v - f[n][v]);
    return 0;
}