回溯法--背包问题

题目：   

有 N 个物体，重为 w[0],w[1]...,有一个背包，只能装重为 S 的物体．问背包应装入哪些物体，是重量刚好为 S.题目要求非递归解法．

 

思路：每一个物体都有两种可能放入或者不放入，不放入不产生影响，放入的话有可能造成=S S

(1)继续放下一个物体

(2)>S==>拿出，继续放该物体的下一个物体，这里要注意放入最后一个物体时的影响==>当放入最后一个物体时不能达到S，或者超出S的限制的时候，需要将其取出，并回溯到前一个放入的物体，将其取出，从下一个物体重新开始。

(3)=S==>输出，回溯

 

代码：

 

#include "stdafx.h"
#include <iostream>
#define N 7
#define S 15
int w[N+1] = {9,1,4,3,4,5,2,7};
int knap()
{
    int flag[N+1] = {0,0,0,0,0,0,0,0};
    int i = 0;
    int m = 0;
    while(1)
    {
        if (m == S)//如果找到物体，输出 
        {
            int j = 0;
            for(j = 0;j < i;j++) //i表示的放入物体的下一个物体
            {
                if (flag[j]==1)
                {
                    std::cout<<w[j]<<"+";
                }
            }
            std::cout<<"="<<S;
            std::cout<<std::endl;
            //回溯
            i = i - 1;
            m = m - w[i];
            flag[i] = 0;
        }
        else if (m < S && i <= N)
        {
            m += w[i];
            flag[i] = 1;
        }
        else if (m > S || i > N) //超重或所有的物体都加入背包还不满足条件，回溯 
        {
            if (i > N)
            {
                if (flag[N] == 1)
                {
                    m = m - w[N];
                    flag[N] = 0;
                }
                i = N - 1;
            }
            while(flag[i]==0&&i>=0)//回溯到上一个选择的物体 
            {
                i--;
            }
            if (i < 0) //回溯到第一个以前，则没有满足要求的 
            {
                std::cout<< "No More";
                return 0;
            }
            m = m - w[i];
            flag[i] = 0;
        }
        i++;//处理下一个物体 
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    knap();
    getchar();
    return 0;
}