网站托管就业做网站知道访客ip

# [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;}}
}