[01背包] 装箱问题(01背包)

文章目录

0. 前言

相关：

• [背包] 背包问题算法模板(模板)

1. 01背包裸题

1024. 装箱问题

裸题。体积当做价值来用，最少剩余容量等于最大利用体积(价值)，最后记得得相减。

时间复杂度为背包数量 * 物品数量， O ( n m ) O(nm) O(nm)。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e4+5;

int n, m;
int v[N];
int f[N];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; ++i) cin >> v[i];
    
    for (int i = 1; i <= n; ++i) 
        for (int j = m; j >= v[i]; --j)
            f[j] = max(f[j], f[j - v[i]] + v[i]);
    cout << m - f[m] << endl;
    return 0;
}

精简代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e4+5;

int n, m;
int f[N];

int main() {
    cin >> m >> n;
    
    for (int i = 1; i <= n; ++i) {
        int v;
        cin >> v;
        for (int j = m; j >= v; --j)
            f[j] = max(f[j], f[j - v] + v);
    }
    
    cout << m - f[m] << endl;
    return 0;
}

二维代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20005, M = 35;

int n, m;
int v[N];
int f[M][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> v[i];
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + v[i]);
        }
    }
    cout << n - f[m][n] << endl;
}