冬日飘雪

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 阅读(286) 评论(0)  编辑 收藏 引用 所属分类: C++


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


My Links

Blog Stats

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜