数据结构基础 背包问题（一） 之 非递归解
分类：数据结构与算法
【问题描述】
“背包题目”的基本描述是：有一个背包，能盛放的物品总重量为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 的循环更新；
【屌丝源码】
// —————————————————// 注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;}}// 本次重量,初始化0int 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（字符串）
详址：
代码
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);}elseif( 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（图和暴力枚举）
详址：
代码
// 现采用迭代方式实现，之后在对非迭代方式处理 // 算法思想：从根节点 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 都是 0void 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、贪心算法：贪心算法基于的思想是每一次选择都作当前最好的选择，这样最后的结果虽然不一定是最优解，但是也不会比最优解差很多。
让你的心情地落到极点，一直学习生活等各个方面都做不好，最终害的还是自己。
