coreBugZJ

此 blog 已弃。

装箱问题——算法作业 3.5,EOJ 1113

装箱问题

Time Limit:1000MS Memory Limit:30000KB
Total Submit:660 Accepted:296

Description

有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0<n≤30),每个物品有一个体积(正整数)。要求从n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

Input

输入有多组测试数据,第一行一个正整数V,表示箱子的容量
第二行一个数据n表示物品个数。
第三行有n个数据,描述每个物品的体积

Output

每个输出占一行,输出箱子最后剩下的最小体积

Sample Input

24 一个整数,表示箱子容量
6 一个整数,表示有n个物品
8 3 12 7 9 7分别表示这n个物品的各自体积

Sample Output

0 一个整数,表示箱子剩余空间


hint:汉字是不需要处理的,只是为了描述题目

你也可以考虑其他的方法。

Source

ECNU算法作业


0-1 背包:

 1 #include <iostream>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 const int L = 20003;
 7 bool have[ L ];
 8 
 9 int main(){
10         int v, n, w, j;
11         while( cin >> v ){
12                 memset( have, 0sizeof(have) );
13                 have[ 0 ] = true;
14                 cin >> n;
15                 while( n-- ){
16                         cin >> w;
17                         for( j = v; j >= w; --j ){
18                                 have[ j ] = have[ j ] || have[ j - w ];
19                         }
20                 }
21                 for( j = v; ! have[ j ]; --j )
22                         ;
23                 cout << v - j << endl;
24         }
25         return 0;
26 }
27 


posted on 2011-04-18 16:18 coreBugZJ 阅读(410) 评论(0)  编辑 收藏 引用 所属分类: 课内作业


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理