信息学奥赛一本通1917：【01NOIP普及组】装箱问题
1917：【01NOIP普及组】装箱问题
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 4178 通过数: 2473
【题目描述】
有一个箱子容量为VV(正整数，0≤V≤200000≤V≤20000），同时有n个物品（0≤n≤300≤n≤30),每个物品有一个体积（正整数）。要求从nn个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
【输入】
第一行是箱子的容量,第二行是nn(表示nn有nn个物品),接下来nn行是nn个物品的体积。
【输出】
最小空间
【输入样例】
24
6
8
3
12
7
9
7
【输出样例】
0
思路：
很明显，这是一道动态规划题
我们看别人的代码，可以知道这里要用二维数组
所以：
dp[i][j]表示在前i个物品中选择物品放入大小为j的箱子的方案中剩余空间最小的方案的剩余空间
我们来举个例子，来计算dp【3】【5】
我们要如何将物品放入箱子呢
我们有两种方案：
1、放入a【3】物品（此时dp【3】【5】=dp【2】【5- a[3] 】）
因为我们放入了物品，剩余的空间相当于将前2件放入空间为5-a【3】的箱子中（因为放了东西，所以要 -a【3】，很合理）
2、不放入a【3】物品（此时dp【3】【5】= dp【2】【5】 ）
因为我们没有放入物品，剩余的空间相当于将前2件放入空间为5的箱子中（因为没放东西，所以不用 -a【3】，很合理）
还有些特殊情况：
还是计算dp【3】【5】，a【3】>5，这时候，我们就不能将a【3】放进箱子了，只能选择2号方案
这是很久以前开始写的题解，今天看到了就写完吧
这个代码肯定是从哪里借鉴抄来的，但我忘记抄的哪里的
代码：
//抄的
#include<bits/stdc++.h>
using namespace std;
#define N 35//让N永远等于35
#define V 20005
int v, n, dp[N][V], a[N];//dp[i][j]：在前i个物品中选择物品放入大小为j的箱子的方案中剩余空间最小的方案的剩余空间
int main()
{cin >> v >> n;for(int i = 1; i <= n; ++i)cin >> a[i];//a[i]：第i物品的体积 for(int j = 0; j <= v; ++j)//设初值，前0个物品放入大小为j的箱子，剩余空间为j dp[0][j] = j;for(int i = 1; i <= n; ++i)for(int j = 0; j <= v; ++j){if(j >= a[i])dp[i][j] = min(dp[i-1][j], dp[i-1][j-a[i]]);elsedp[i][j] = dp[i-1][j];}cout << dp[n][v];return 0;
}