coreBugZJ

此 blog 已弃。

子集和问题 & 机器设计——算法作业 5.1 & 5.2,EOJ 1053 & 1054

子集和问题
 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4#define  L  109
 5
 6int n, a[ L ], s[ L ], x, ans;
 7
 8void dfs( int i, int tmp ) {
 9        if ( tmp == x ) {
10                ++ans;
11                return;
12        }

13        if ( ( i > n ) || ( tmp > x ) || ( s[ n ] - s[ i - 1 ] + tmp < x ) ) return;
14        dfs( i + 1, tmp + a[ i ] );
15        dfs( i + 1, tmp );
16}

17
18int cmp( const void * a, const void * b ) {
19        return *((int*)b) - *((int*)a);
20}

21
22int main() {
23        int td, i;
24        s[ 0 ] = a[ 0 ] = 0;
25        scanf( "%d"&td );
26        while ( td-- ) {
27                scanf( "%d%d"&n, &x );
28                for ( i = 1; i <= n; ++i ) {
29                        scanf( "%d", a + i );
30                }

31                qsort( a + 1, n, sizeof(a[0]), cmp );
32                for ( i = 1; i <= n; ++i ) {
33                        s[ i ] = s[ i - 1 ] + a[ i ];
34                }

35                ans = 0;
36                dfs( 10 );
37                printf( "%d\n", ans );
38        }

39        return 0;
40}

41




机器设计
 1#include <stdio.h>
 2
 3#define  N  100
 4#define  INF  0X3f3f3f3f
 5
 6int n, m, w[ N ][ 3 ], c[ N ][ 3 ];
 7
 8int tc, tw, aw;
 9void dfs( int i ) {
10        int j;
11        if ( i >= n ) {
12                aw = tw;
13                return;
14        }

15        for ( j = 0; j < 3++j ) {
16                tc += c[ i ][ j ];
17                tw += w[ i ][ j ];
18                if ( (tc<m) && (tw<aw) ) {
19                        dfs( i + 1 );
20                }

21                tc -= c[ i ][ j ];
22                tw -= w[ i ][ j ];
23        }

24}

25
26int main() {
27        int i, j;
28        while ( scanf( "%d%d"&n, &m ) == 2 ) {
29                for ( i = 0; i < n; ++i ) {
30                        for ( j = 0; j < 3++j ) {
31                                scanf( "%d%d"&(w[i][j]), &(c[i][j]) );
32                        }

33                }

34                tc = tw = 0;
35                aw = INF;
36                dfs( 0 );
37                printf( "%d\n", aw );
38        }

39        return 0;
40

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


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