数据结构基础背包问题（一）之非递归解

你的名字 2022-08-03 05:24 114阅读 0赞

【问题描述】

“背包题目”的基本描述是：有一个背包，能盛放的物品总重量为S,设有N件物品，其重量分别为w1，w2，…，wn，希望从N件物品中选择若干物品，所选物品的重量之和恰能放进该背包，即所选物品的重量之和即是S。递归和非递归解法都能，试非递归算法求得“背包题目”的一组解

【算法分析】

1.此程序是得到问题的所有解；

2.本题只对背包有重量约束；

3.算法思想（暴力枚举）

1）初始化flag数组，数组长度为背包数目 n，数组为全 0 序列，0,1表示是否添加第 i 个 背包，初始状态下一个背包都不添加；

2）添加背包的排列的可能性为2^n种，n为背包的数目：

a.循环中 flag 每次遇到1则补零进位，遇到0则补一并退出对 flag 的循环更新；

b.将添加背包的序列号写入临时数组，通过判断总重与 S 的关系决定是否打印输出；

【屌丝源码】

// ---------------------------------------------------
    //  注1: 一般要求一个解，此程序是得到所有解
    //  注2: 只对背包有重量约束，此程序更易理解                    
    // ---------------------------------------------------
    
    #include <iostream>
    using namespace std;
    
    // 物品总数
    const int N_ITEM = 5;
    // 背包能装的重量
    const int BAG = 15;
    // 初始化每个物品的重量
    int item[N_ITEM] = {2, 3, 5, 7, 8};
    // 标记数组
    int flag[N_ITEM] = {0, 0, 0, 0, 0};
    // 结果计数器
    int resultCount = 0;
    // 打印结果
    void Print();
    
    int main()
    {
    // 打印已知条件
    	cout << "BAG Weight:" << BAG << endl;
    	cout << "Item Number:" << N_ITEM << endl;
    	for (int i=0; i!=N_ITEM; i++)
    	{
    		cout << "Item." << i+1 << " W=" << item[i] << "\t";
    	}
    	cout << endl;
    
    	unsigned int count = 0;
    	unsigned int all_count = 1;
    
    	for (int i=0; i!=N_ITEM; i++)
    	{
    		all_count *= 2;//all_count记录可能解的个数
    	}
    
    	while (1)
    	{
    		// 模拟递归...列举所有flag数组可能
    		// 其实就这个for循环是关键
    		for (int i=0; i!=N_ITEM; i++)
    		{
    			if ( 0 == flag[i] )
    			{
    				flag[i] = 1;
    				continue;
    			} 
    			else 
    			{
    				flag[i] = 0;
    				break;
    			}
    		}
    
    		// 本次重量,初始化0
    		int temp = 0;
    
    		// 按标记计算所有选中物品重量和
    		for (int i=0; i!=N_ITEM; i++)
    		{
    			if ( 1 == flag[i] )
    			{
    				temp += item[i];
    			}
    		}
    
    		// 满足背包重量就打印
    		if ( temp == BAG )
    		{
    			resultCount++;
    			Print();
    		} 
    
    		// 如果遍历了所有情况就break掉while(1)循环
    		count++;
    		if (count == all_count)
    		{
    			break;
    		}
    	}
    
    	return 0;
    }
    
    void Print()
    {
    	cout << "Result " << resultCount << endl;
    	for (int i=0; i!=N_ITEM; i++)
    	{
    		if ( 1 == flag[i] )
    		{
    			cout << "Item." << i+1 << "  Weight:" << item[i] << "\t";
    		}
    	}
    
    	cout << endl;
    }

只求一个解算法思想——括号算法思想。

详见：LeetCode 之 Valid Palindrome（字符串）

详址：http://blog.csdn.net/u013630349/article/details/46998327

代码

vector<int> knapsack(int *w, int N, int S){
        stack<int> stk;
        int weight = 0;
        int i = 0;
        bool solvable = false;
        while( weight != S && i < N){
            weight += w[i];
            if( weight < S){
                stk.push(i);
            }
    		else 
    			if( weight == S){
    				solvable = true;
    				break;
    			}
    			else{
    				i = stk.top();
    				stk.pop();
    			}
            i++;
        }
        vector<int> ret;
        if( solvable == false)
            return ret;
        while( !stk.empty() ){
            ret.push_back(stk.top());
            stk.pop();
        }
        return ret;
    }

【迭代解的思想与算法】

全部可能解的算法思想——树的“深搜”

详见：[LeetCode 之 Subsets（图和暴力枚举）][LeetCode _ Subsets]

详址：http://blog.csdn.net/u013630349/article/details/47121697

代码

// 现采用迭代方式实现，之后在对非迭代方式处理  
    // 算法思想：从根节点 O 出发，经过n个节点到达满二叉树叶子节点  
    // 第i-1层节点下的左右两个孩子有，左节点表示添加Wi个背包，右节点表示不添加Wi个  
    // 在节点到达重量S的时候录入容器  
    Class Solution  
    {  
    public:  
        vector<vector<int>> Get_Res(int n,int S,vector<int> &w){  
            vector<vector<int>> res;  
            stack<int> path;          
            myfun(path,res,S,0,w,0,n);  
            return res;  
        }  
        // path 表示添加的路径；  
        // res 表示路径集合；  
        // wei 当前路径下的重量  
        // Level 当前层数  
        // 初态下 Level和wei 都是 0   
        void myfun(stack<int> &path,vector<vector<int>> &res,int S,int wei,vector<int> &w,int Level,int n)  
        {  
              
            if(Level>=n)
            {  
                if(S==wei)  
                    res.push_back(path);  
                return;  
            }  
            if(wei==S)  
            {  
                res.push(path);  
            }
            if(wei>S)  
            {  
                return;  
            }		
            myfun(path,res,S,wei,w,Level+1,n);  
            path.push(Level);  
            wei = wei+w[Level];  
            myfun(path,res,S,wei,w,Level+1,n);  
            path.pop();  
            wei = wei-w[Level];  
        }  
    }；

【小结】

1.可以通过全可能性列举，确定循环次数；

2.可以通过标志维数组，确定路径的选择；

3.单一解，括号算法是优先考虑的选择；

3.在迭代许可的条件下，针对全部解的问题，树的“深搜”算法，是很好的选择。

二、解决方法：

1、贪心算法：贪心算法基于的思想是每一次选择都作当前最好的选择，这样最后的结果虽然不一定是最优解，但是也不会比最优解差很多。

举个例子说明可能好懂一些：一帮基友去聚餐，菜是一份一份上的，我每一次夹菜都只夹牛肉/海鲜吃，可能到最后我吃的牛肉/海鲜很多，但不一定代表我吃掉的东西的总价值最高，但是相对来说价值也很高了～

换句话说，对于贪心算法，其核心在于设定一个标准让我们去贪。回到这个问题，这个标准就有三种设法了：1、价值最高的先装进背包；2、重量最低的先装进包；3、性价比（价值和重量的比值）最高的先装进背包。我在这里用的是第三种方法，用快排作了排序。

在装的过程中要注意的就是，当前物品能不能放进背包。这个是需要考虑的。因为背包问题也有好几种，如：0-1背包问题（每种物品只能拿一次）、完全背包问题（每种物品都能拿无限次）、多重背包问题（每种物品都有一定的数量可以拿）。所以在不同情况下贪心算法的一些细节设计也是不一样的，这个需要自己考虑。

2、动态规划算法：贯穿动态规划算法的就是状态和状态转移方程这两个东西，而要得到这两个东西需要我们把我们的问题分解为更小的子问题，通过分析子问题去获得。（[数据结构与算法学习之路：LIS——最长递增序列的动态规划算法和二分思想算法][LIS]）

那么回到我们这个问题，由于每次装东西进背包，我们只考虑能否装进，以及是否当前状态下的最优选择，也就是说，我们需要用背包的容量去设计一个数组，存储每一单位个容量的最大价值是多少，以此类推，获得背包容量下的最大价值是多少。这样说可能说不清楚，看看下面的代码吧～