# [NOIP2001 普及组] 装箱问题
## 题目描述
有一个箱子容量为 $V$,同时有 $n$ 个物品,每个物品有一个体积。
现在从 $n$ 个物品中,任取若干个装入箱内(也可以不取),使箱子的剩余空间最小。输出这个最小值。
## 输入格式
第一行共一个整数 $V$,表示箱子容量。
第二行共一个整数 $n$,表示物品总数。
接下来 $n$ 行,每行有一个正整数,表示第 $i$ 个物品的体积。
## 输出格式
- 共一行一个整数,表示箱子最小剩余空间。
https://www.luogu.com.cn/problem/P1049
一个背包问题,用较为普遍的方法也就是dp二维数组(将体积看作价值)可以过但空间占用的较多。
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0)
const int N = 20000;
int c[N];
int dp[30][N];
int solve(int n, int C) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= C; j++) {if (c[i] > j)dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + c[i]);}}return (C - dp[n][C]);
}int main() {IO;int C, n;cin >> C >> n;for (int i = 1; i <= n; i++)cin >> c[i];memset(dp, 0, sizeof(dp));cout << solve(n, C) << endl;return 0;
}
既然这道题不涉及价值那么我们可以用01背包问题的解法,这样只用定义一个一维数组,空间占用少。
#include<iostream>
using namespace std;
int v, n;
int a[40];
int dp[20100];int main() {cin >> v >> n;for (int i = 1; i <= n; i++) cin >> a[i];dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = v; j >= a[i]; j--) {dp[j] = dp[j] || dp[j - a[i]];}}for (int j = v; j >= 0; j--) {if (dp[j]) {cout << v - j;break;}}
}