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( 1, 0 );
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 阅读(472) 评论(0)  编辑 收藏 引用 所属分类: 课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理