【正确答案】(1)数据结构
   #define N 4
   #define M 15
   #define ENTRY(i,j)(*(pentry+(i)*(m+1)+(j)))
   struct Entry{
       int p;
       int isslct;
       int m：
   };
   typedef struct Entry*PEntry;
   (2)思路
   假设0/1背包问题的解用f(n，m)表示，它可以分成两种情况，一种是x_n=1，另一种是x_n=0，则有如下的递推式：f(n,m)=max{f(n-1，m)，f(n-1，m-w_n-1)+p_n-1}，其中f(n-1，m)表示只有前n-1个物体，对m求背包问题的解。
   把以上公式加以推广，得：f(i,j)=max{f(i-1，j),f(i-1，j-w[i-1])+p[i-1]}，让i从0到n，j从0到m，依次求出f(i,j)直到求出f(n，m)。
   为此，创建一个大小为(n+1)(m+1)的数组，其中的每一个元素都是struct Entry类型，这个(n+1)(m+1)的数组用来存放中间结果以避免重复计算。
   (3)代价分析
   一共要计算n×m次，所以时间代价为O(n×m)。
   (4)完整程序
   #include＜stdio.h＞
   #include＜stdlib.h＞
   #define N 8
   #define M 110
   #define ENTRY(i,j)(*(pentry+(i)*(m+1)+(j)))
   struct Entry{
       intp;
       int isslct;
       intm;
   };
   typedef struct Entry*PEntry;
   intknap_dynamic(intn,intm,int*w,int*p,int*x){
   /*用动态规划法求解0/1背包问题*/
       PEntry pentry;
       int i,j,p1,p2,maxp;
       pentry=(PEntry)malloc((n+1)*(m+1)*sizeof(struct Entry));
       if(pentry==NULL)
           return-1;
       for(i=0;i＜=n;i++)
           ENTRY(i,0).p=0;    /*赋初值*/
       for(i=0;i＜=m;i++)
           ENTRY(0,i).p=0;
       for(i=1;i＜=n;i++){    /*逐层构建解*/
           for(j=1;j＜=In;j++){    /*i,j对应公式中的i,j*/
             p1=ENTRY(i-1,j).p;
             if(j-w[i-1]＞=0&&(p2=ENTRY(i-1,j-w{i-1]).p+
               p[i-1])＞p1){
               ENTRY(i,j).p=p2;
               ENTRY(i,j).isslct=1：
             ENTRY(i,j).m=j-w[i-1];
           }
           else{
             ENTRY(i,j).p=p1;
             ENTRY(i,j).isslct=0：
             ENTRY(ij).m=j;
           }
         }
       }
       maxp=ENTRY(n,m).p;
       j=m;
       for(i=n;i＞0;i--){
           x[i-1]=ENTRY(i,j).isslct;
           j=ENTRY(i,j).m;
       }
       free(pentry);
       return maxp;
   }
   void main(){
       int w[]={1,11,21,23,33,43,45,55};
       int p[]={11,21,31,33,43,53,55,65};
       int x[N];
       int maxp,1;
       maxp=knap_dynamic(N,M,w,p,x);
       if(maxp==-1)
           printf("Not enough menory!\n");
       else{
           printf("max value=/%d\nx=(/%d"maxp,x[0]);
           for(i=1;i＜N;i++)printf(",/%d",x[i]);
           printf(")\n");
       }
   }
   (5)调试结果
   max value=159
   x=(1,1,1,0,1,1,0,0)