织梦高清电影网站模板,店铺推广方法,中山网站建设优化,php网站开发书# [NOIP2001 普及组] 装箱问题
## 题目描述
有一个箱子容量为 $V$#xff0c;同时有 $n$ 个物品#xff0c;每个物品有一个体积。
现在从 $n$ 个物品中#xff0c;任取若干个装入箱内#xff08;也可以不取#xff09;#xff0c;使箱子的剩余空间最小。输出这个最小值。…# [NOIP2001 普及组] 装箱问题
## 题目描述
有一个箱子容量为 $V$同时有 $n$ 个物品每个物品有一个体积。
现在从 $n$ 个物品中任取若干个装入箱内也可以不取使箱子的剩余空间最小。输出这个最小值。
## 输入格式
第一行共一个整数 $V$表示箱子容量。
第二行共一个整数 $n$表示物品总数。
接下来 $n$ 行每行有一个正整数表示第 $i$ 个物品的体积。
## 输出格式
- 共一行一个整数表示箱子最小剩余空间。
https://www.luogu.com.cn/problem/P1049
一个背包问题用较为普遍的方法也就是dp二维数组将体积看作价值可以过但空间占用的较多。
#includebits/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背包问题的解法这样只用定义一个一维数组空间占用少。
#includeiostream
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;}}
}
