背包问题的非递归解法

老师写的太乱了，真是看晕了，改天再看。

 

#include "stdio.h" #define LEN 5 #define S0 10 #define N0 5 typedef struct { int s; int n; int job; } KNAPTP ; int w[LEN+1] = {0,1,4,4,5,7}; KNAPTP stack[100]; int top; /*===================*/ void ps() { int i; for (i=top; i>=1; i--) printf("%d %d %d/n",stack[i].s, stack[i].n, stack[i].job); printf("=======/n"); } /*===================*/ int knap(int s, int n) { KNAPTP x; int k; /* 布置初始任务 */ x.s = s; x.n = n; x.job = 0; top = 1; stack[top] = x; /* push */ k = 0; while ( (top >= 1) && !k ) { /* 取得一项任务 */ x = stack[top]; /* 对栈顶任务递推求解 */ while ( !k ) { if ( x.s == 0 ) k = 1 ; else if ( x.s<0 || x.n<=0 ) break; else { /* 布置下层包含w[n]重量的任务 job=1 */ x.s = x.s-w[x.n]; x.n--; x.job = 1; stack[++top] = x; /* push */ } } // printf("-- test1 --/n"); ps(); (void)getchar(); if ( !k ) { while ( ( top >= 1 ) ) { x = stack[top--]; /* pop */ if ( x.job == 1 ) { /* 布置本层不包含w[n]重量的任务 */ x.s += w[x.n+1]; x.job = 2; stack[++top] = x; /* push */ break; } } // printf("-- test2 --/n"); ps(); (void)getchar(); } } /* 求解结果的处理 */ if ( k ) { while ( top >= 1 ) { x = stack[top--]; /* pop */ if (x.job ==1 ) printf("%d ", w[x.n+1] ); } } return (k); } /*===================*/ main() { if ( knap(S0,N0) ) printf("此'背包问题'有解!/n"); else printf("此'背包问题'无解!/n"); } . 

 

 

---

 

老师写的好像有错误，下面是我写的，大概摸清了意思,注意看注释

 

// 简单背包的非递归算法 #include <stdio.h> #define MAX_ARRAY 0xff #define LEN 5 #define S0 10 #define N0 5 typedef struct _workState { int s,n,isPushed; }workState; int w[LEN+1] = {0,1,4,4,5,7}; workState myWork[MAX_ARRAY] = {0}; int TOP=0; int knap(int s, int n) { int isOK = 0; // 成功标志 workState ini_workState; ini_workState.isPushed = 0; ini_workState.n = n; ini_workState.s = s; myWork[TOP++] = ini_workState; // Push the initial state in stack while (TOP>0 && !isOK) // if there are some states in stack { // take the TOP state ini_workState = myWork[--TOP]; while (TOP>0 && !isOK) { if(ini_workState.s == 0) isOK = 1; else if(ini_workState.n < 0 || ini_workState.s < 0) { isOK=0; break; } // 如果当前状态不成功，那么就会跳出来 else { ini_workState.isPushed = 1; // 表示当前状态 是成功路径 ini_workState.s -= w[ini_workState.n]; --ini_workState.n; myWork[TOP++] = ini_workState; // Push the new state in stack } } ////////////////////////////////////////////////////////////////////////// // 这种情况是当前状态的修改，即去掉一个当前状态，所以不用 ini_workState.n 做++或-- if(!isOK) { while (TOP>0) { // 这种情况下可以出栈，先出栈修改才能进栈，但 是如果为零的结点全出栈了，好像也不会有问题 ini_workState = myWork[--TOP]; if (ini_workState.isPushed == 1) // 若当前状 态是可行状态 { ini_workState.s += w [ini_workState.n]; // 去掉当前状态的重量 ini_workState.isPushed = 0; myWork[TOP++] = ini_workState; break; } } } } return isOK; } int main() { if ( knap(S0,N0) ) printf("此'背包问题'有解!/n"); else printf("此'背包问题'无解!/n"); return 0; }