【说明】
【C程序1】用回溯算法来产生由0或1组成的2m个二进位串，使该串满足以下要求。
视串为首尾相连的环，则由m位二进制数字组成的2m个子序列，每个可能的子序列都互不相同。例如，如果m=3，在串11101000首尾相连构成的环中，由3位二进制数字组成的每个可能的子序列都在环中恰好出现一次，它们依次是111，110，101，010，100，000，001，011，如图2-14所示。
【C程序2】是求“背包问题”的一组解的递归算法程序。“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为W1，W2，…，Wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。
【C程序1】
#define N 1024
#define M 10
int b [N+M-1]
int equal(int k, int j int m) {
int i;
for(i=0; i＜m; i++
if ( b[ k + i] (1) )
return 0;
return 1; }
int exchange (int k, int m, int v){
while ( b[ k + m - 1 ) == v ) {
b[ kncm--i]=! v (2) ;
}
(3) =v;
return k;
}
init ( iht v) {
int k
for( k = 0;K = N + M - 1;k++)
b[k] = v;
}
main ( ) {
int m, v, k, n, j;
printf (’Enter m (l＜m＜10) , v v=0, v=1)\ n") ;
scanf (" %d%d , &m, &v);
n = 0x01 ＜＜ m;
init (!v);
k=0;
while( (4) ＜ n)
for (j=0;j＜k;j++)
if (equal (k, j, m)) {
k=exchange (k, m, v)
j= (5) ;
}
for (k= 0 ;k＜n ;k++ )
print{ (" %d\ n" , b[k]) ;
}
}
【C程序2】
#include＜stdio. h＞
#define N 7
#define S 15
int w[N+1] = {0, 1, 4, 3, 4, 5, 2, 7};
int knap (int S, int n){
if (S == 0)
return 1;
if (s＜0 || (s＞0 && n＜1))
return 0;
if ( (6) )) {
printf( "4d", w[n]);
return 1;
}
return (7)
}
main ( ) {
if (knap (S, N)
printf("OK:\n");
else
printf("NO!\n")
}
