装箱问题

01背包问题

本题要求的是最小的剩余空间，相反，其实求的也就是最大的背包填充量，总容量 - 最大填充量 即为最小剩余体积

1.$f[i,j]$的含义

$f[i,j]$在本题的含义为挑选第i个物品时，背包容量为j时能塞的最大体积

2.$f[i,j]$的递推逻辑

(1)如果不往背包里面塞东西，那么背包的最大体积为$f[i-1,j]$
(2)如果往背包里面塞东西，那么背包的最大体积为$max(f[i,j],f[i-v[i]] + v[i])$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30010;

int n, V;
int v[N],d[N];

int main()
{
    scanf("%d%d", &V, &n);
    for(int i = 1; i <= n; i ++ )
        scanf("%d", &v[i]);
    for(int i =1; i <= n ; i ++ )
    {
        for(int j = V; j >= v[i]; j -- )
            d[j] = max(d[j], d[j-v[i]] + v[i]);
    }
    printf("%d", V - d[V]);
    return 0;
}