题目名称：装箱问题
来源：2011年NOIP普及组
# 链接
## 博客链接
- [CSDN](https://blog.csdn.net/weixin_43890363/article/details/100805393)
- [博客园](https://www.cnblogs.com/Alvin-Tree/p/11603174.html)
## 题目链接
- Vijos [题目](https://vijos.org/p/1133) [递交](https://vijos.org/p/1133/submit) [讨论](https://vijos.org/discuss/10/1133) [题解](https://vijos.org/p/1133/solution)
- 洛谷(P1049) [题目](https://www.luogu.org/problem/P1049) [提交代码](https://www.luogu.org/problem/P1049#submit) [提交记录](https://www.luogu.org/record/list?pid=P1049) [讨论列表](https://www.luogu.org/discuss/lists?forumname=P1049) [查看题解](https://www.luogu.org/problemnew/solution/P1049)
# 前缀知识
- [01背包](https://blog.csdn.net/weixin_43890363/article/details/101603562)
# 题解
这是一道01背包裸题，先进行01背包，在找到比$v$小但是可以得到的数，输出$v$与这个数的差。
```cpp
//C++
#include<bits/locale_facets.h>
#include<bitset>
#include<stdio.h>
#define downto(name,i,u,d) for(name i=u;i>=d;i--)
inline void output(long long o);
inline long long input();
std::bitset<20001>full;
int main(){
short v=input(),n=input(),volume;
full[0]=true;
while(n--){
volume=input();
downto(short,i,v,volume)full[i]=full[i]|full[i-volume];
}for(short i=0;;i++)
if(full[v-i])return output(i),0;
}inline void output(long long o){
if(o<0)putchar('-'),o=-o;
if(o>=10)output(o/10);
putchar(o%10^'0');
}inline long long input(){
bool minus=false;
char now=getchar();
long long i=0;
for(;!isdigit(now);now=getchar())
if(now=='-')minus=!minus;
for(;isdigit(now);now=getchar())i=(i<<3)+(i<<1)+(now^'0');
return minus?-i:i;
}
```
```pas
//pascal
type box=0..20000;
var
i,n:1..30;
j,v,volume:box;
full:array[box] of boolean;
begin
readln(v);
readln(n);
full[0]:=true;
for j:=1 to v do full[j]:=false;
for i:=1 to n do begin
readln(volume);
for j:=v downto volume do full[j]:=full[j] or full[j-volume];
end;for j:=0 to v do
if full[v-j] then break;
write(j);
end.
```