网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
简单背包问题2
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 10:50 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 10:50 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 10:50 |
输入文件 | pack2.in | 输出文件 | pack2.out |
【题目描述】简单背包问题2(pack2.cpp/c/pas) NOIP 2001
张琪曼:“为什么背包一定要完全装满呢?尽可能多装不就行了吗?”
李旭琳:“你说得对,这和墨老师曾告诉我们的‘日中则昃,月满则亏’是一个道理。”所以,现在的问题是,她们有一个背包容量为v(正整数,0≤v≤20000),同时有n个魔法石(0≤n≤30),每个魔法石有一个体积 (正整数)。要求从n个魔法石中,任取若干个装入包内,使背包的剩余空间为最小。
【输入格式】
第一行为一个整数,表示背包容量,第二行为一个整数,表示有n个魔法石,接下来n行,分别表示这n个魔法石的各自体积。
【输出格式】
只有一个整数,表示背包剩余空间。
【输入样例】
24
6
8
3
12
7
9
7
【输出样例】
0