c语言背包问题非递归算法,数据结构基础 背包问题（一） 之 非递归解
source insight代碼對齊Tab鍵終極版以前也寫過一個source insight代碼對齊，由于自己理解不夠深刻，只能解決部分問題，不能根治在source insight中對齊的代碼在X
數據結構基礎 背包問題(一) 之 非遞歸解
分類：
數據結構與算法
【問題描述】
“背包題目”的基本描述是：有一個背包，能盛放的物品總重量為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
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(字符串)
詳址：
代碼
vector knapsack(int *w, int N, int S){
stack 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 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> Get_Res(int n,int S,vector &w){
vector> res;
stack path;
myfun(path,res,S,0,w,0,n);
return res;
}
// path 表示添加的路徑；
// res 表示路徑集合；
// wei 當前路徑下的重量
// Level 當前層數
// 初態下 Level和wei 都是 0
void myfun(stack &path,vector> &res,int S,int wei,vector &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、貪心算法：貪心算法基于的思想是每一次選擇都作當前最好的選擇，這樣最后的結果雖然不一定是最優解，但是也不會比最優解差很多。
總結
以上是生活随笔為你收集整理的c语言背包问题非递归算法,数据结构基础 背包问题（一） 之 非递归解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 第三十七期:为什么2019年人工智能算法
- 下一篇： 浪潮世科和浪潮软件什么关系_社交图形浪潮