冬日飘雪

0/1背包——非递归解法


#include 
"iostream"

using namespace std;

#define  N 7
#define  W 15

int weight[N+1= {9,1,4,3,4,5,7,8};

int flag[N+1= {0,0,0,0,0,0,0,0};

int knap()
{
    
int i=0;
    
int m = 0;

    
while (1)
    
{
        
if (m < W && i <=N)
        
{
            m 
+= weight[i];
            flag[i] 
= 1;
        }

        
else
        
{
            i
--;
            
while (flag[i]==0 && i>=0)
            
{
                i
--;
            }

            
if (i<0)
            
{
                cout
<<"Not found"<<endl;
                
return 0;
            }

            m 
-= weight[i];
            flag[i] 
= 0;
        }

        
if (m == W)
        
{
            
for(int k=0; k<=N; k++)
            
{
                
if (flag[k] == 1)
                
{
                    cout
<<weight[k]<<" ";
                }

            }

            
return 1;
        }

        i
++;
    }

}


void main()
{
    knap();
    getchar();
}



















posted on 2010-05-15 21:43 Bomb 阅读(86) 评论(0)  编辑 收藏 引用 所属分类: C++


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜