简单背包问题:

 有一个背包，能盛放的物品总重量为s，设有n件物品，其重量分别为w1,w2,…,wn.希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于s。

 

递归算法：

 1 // 背包问题-递归.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include “stdafx.h“
 5 int w[5] = {1, 4, 4, 5, 7};
 6 int knap(int s, int n)
 7 {
 8     if(s == 0)
 9     {
10         return(1);
11     }
12     else
13     {
14         if( s < 0 || (s > 0 && n < 1))
15         {
16             return(0);
17         }
18         else
19             if(knap(s – w[n – 1],n – 1) == 1)
20             {
21                 printf(“result: n = %d, w[%d] = %d \n“, n , n – 1, w[n–1]);
22                 return (1);
23             }
24             else
25             {
26                 return(knap(s, n – 1));
27             }
28 
29     }
30 }
31 
32 int _tmain(int argc, _TCHAR* argv[])
33 {
34     knap(10, 5);
35     return 0;
36 }

运行结果： 

 result: n = 1, w[0] = 1

result: n = 3, w[2] = 4 

result: n = 4, w[3] = 5 

非递归算法：(参考 http://blog.csdn.net/alex197963/archive/2007/05/11/1604462.aspx)

  1 #include “stdafx.h“

 2 #include <stdio.h>
 3 #define N 7
 4 #define S 15
 5 
 6 typedef struct 
 7 {
 8     int s;                                                    /*s表示考查过（就是装入）该物品后，背包所能盛放的物品的重量*/
 9     int n;                                                    /*n表示待考查的下一个物品在数组w中的下标*/
10     int job;                                                 /*job表示当前物品的状态*/                          
11 } KNAPTP;             
12 int w[N+1] = {0,1,4,3,4,5,2,7};                                 /*w表示待考查 一组物品的重量，当然现实中没有重量为0的物体*/
13  
14 int knap(int s,int n)                                        /*求出一组物品的解并在屏幕上打印它们*/                                
15 {
16     KNAPTP stack[100],x;                                    /*定义一个stack数组（用于保存已查过的物品）及x，其数据类型为typedef*/
17     int top, k;                                                /*top是stack栈顶标志；k为是否求得解的标志；rep也是标志变量，意义见下面*/
18     x.s = s; x.n = n;                                        /*对工作节点x的s、n分量分别付初值*/
19     x.job = 0;                                                 /*x.job分量为0表示开始背包中没有放入任何物品，赋初值*/
20     top = 1; stack[top] = x;                                /*置top标志为1，将x节点压入stack栈*/
21     k = 0;                                                    /*k也赋初值，当然这时候没有解*/
22     while ( top>0 && k == 0 )                                /*考查各个物品i的选择情况*/
23     { 
24         x = stack[top];                                        /*从栈顶取出物品，放入工作节点x*/
25                                                             /*rep表示是否继续，赋初值1表示继续进行*/                                   
26         while ( !k)                                            /*当k等于0且rep为1时继续循环*/
27         { 
28             if(x.s==0)
29                 k=1;                                        /*x.s为0表示如果背包所能盛放的物品的重量为0（即装满），则已求得一组解*/
30             else 
31                 if (x.s<0||x.n<=0) 
32                     break;                                      /*否则当x.s小于0或x.n小于等于0，则rep为0，表示停止动作*/
33                  else 
34                  {
35                      x.s=x.s–w[x.n—]; 
36                      x.job=1;                                 /*否则将背包的可承重量减去选中的当前物品重量，同时选择下个物品（n–），x.job置为1表示当前物品可以放入*/
37                      stack[++top]= x;                         /*stack的top标志加1，并将工作节点（选中的下个物品）x放入栈顶*/
38                  }
39         }
40         if ( !k )                                             /*如果k等于0，暗含rep此时为0，就是处理所考查的物品不满足放入背包的条件时的情况*/                  
41         {                            
42             while (top>=1)          
43             { 
44                 x = stack[top—];                             /*将栈顶物品放入工作节点x*/
45                 if(x.job==1)                                 /*如果该物品的job状态等于1，这时也一定为1*/
46                 {
47                     x.s+=w[x.n+1];                             /*将x工作节点s分量即当前背包的可承载重量恢复，即将（上一个）不满足条件的物品的重量加回去*/
48                     x.job=2;                                       /*置x的job分量为2，表示该物品不能放入背包，在以后的选择中将不考虑该物品*/
49                     stack[++top] = x;                         /*将x压入栈顶*/
50                     break;
51                 }
52             } 
53         } 
54     } 
55     if (k)
56     {                                                        /*输出一组解*/ 
57         while (top>=1)
58         {
59             x =stack [top—];
60             if ( x.job==1 )
61                 printf (“%d “,w[x.n+1] ); /*一定要下标加1*/
62         } 
63     } 
64     return k;
65 }
66 void main()
67 { 
68     if (!knap(S,N)) 
69         printf(“\n无解“); 
70           
71 }

版权声明：本文为LarmanYuan原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/LarmanYuan/archive/2009/05/27/1491024.html