<—点个赞吧QwQ

宣传一下算法提高课整理

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

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

输入格式

第一行是一个整数 V，表示箱子容量。

第二行是一个整数 n，表示物品数。

接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

输出格式

一个整数，表示箱子剩余空间。

数据范围

$0 < V \le 20000$,
$0 < n \le 30$

输入样例：

24
6
8
3
12
7
9
7

输出样例：

0

思路1

这道题是$0/1$背包问题，我们把体积作为价值，这样求出来的$f_i$就是体积为$i$的最大装入空间。

代码1

#include <iostream>
using namespace std;
const int N = 20010;
int n,m;
int f[N];
int main () {
    cin >> m >> n;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        for (int j = m;j >= x;j--) f[j] = max (f[j],f[j - x] + x);
    }
    cout << m - f[m] << endl;
    return 0;
}

思路2

或许用 $f_i$ 表示是否能凑出体积为 $i$ 会更好？

思路1复杂了，但鉴于是之前写的就留着当纪念了

状态转移方程：$f_i=f_i\operatorname{or}f_{i-x}$。

代码2

#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cassert>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\incra\\Desktop\\"
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
bool LAST = false;
istream& operator >> (istream& in,char* s) {
    if (LAST) return in;
    char ch = in.get ();
    while ((isspace (ch) || ch == '\n') && ch != EOF) ch = in.get ();
    int n = 0;
    while (!(isspace (ch) || ch == '\n') && ch != EOF) s[n++] = ch,ch = in.get ();
    s[n] = '\0';
    if (ch == EOF) LAST = true;
    return in;
}
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
    if (y > x) return x = y,true;
    return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
    if (y < x) return x = y,true;
    return false;
}
LL power (LL a,LL b,LL p) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
const int N = 20010;
int m,n;
bool f[N];
int main () {
    cin >> m >> n;
    f[0] = true;
    while (n--) {
        int x;
        cin >> x;
        for (int i = m;i >= x;i--) f[i] |= f[i - x];
    }
    int ans = m;
    while (!f[ans]) ans--;
    cout << m - ans << endl;
    return 0;
}