背包问题详解编程语言

#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(knap(s-w[n],n-1)){ 
  printf("%4d",w[n]); 
  return 1; 
 } 
 return knap(s,n-1); 
} 
main() 
{ 
 if(knap(S,N)) printf("/nOK!/n"); 
 else printf("NO!/n"); 
}

#include <stdio.h> 
#define N 7 
#define S 15 
typedef struct{ 
 int s; 
 int n; 
 int job; 
}KNAPTP; 
int w[N+1]={0,1,4,3,4,5,2,7}; 
int knap(int s,int n); 
main() 
{ 
 if(knap(S,N)) printf("OK!/n"); 
 else printf("NO!/n"); 
} 
int knap(int s,int n) 
{ 
 KNAPTP stack[100],x; 
 int top,k,rep; 
 x.s=s; x.n=n; 
 x.job=0; 
 top=1; stack[top]=x; 
 k=0; 
 while(top>=1&&!k){ 
  x=stack[top]; 
  rep=1; 
  while(!k && rep){ 
   if(x.s==0) k=1; 
   else if(x.s<0 || x.n<=0) rep=0; 
   else{ 
    x.s=x.s-w[x.n--]; 
    x.job=1; 
    stack[++top]=x; 
   } 
  } 
  if(!k){ 
   rep=1; 
   while(top>=1 && rep){ 
    x=stack[top--]; 
    if(x.job==1){ 
     x.s+=w[x.n+1]; 
     x.job=2; 
     stack[++top]=x; 
     rep=0; 
    } 
   } 
  } 
 } 
 if(k){ 
  while(top >=1){ 
   x=stack[top--]; 
   if(x.job==1) printf("%4d/t",w[x.n+1]); 
  } 
 } 
 return k; 
}