用回溯法求01揹包問題，怎樣使用C啊，迫切求指點

1樓：匿名使用者

#include

using namespace std;

class knap

;int knap::bound(int i)//剩餘物品取部分來裝滿揹包

if(i<=n)

b+=p[i]/w[i]*cleft;

return b;

}void knap::backtrack(int i)}class object

private:

int id;

float d;//單位重量價值

};int knapsack(int p,int w,int c,int n)

if(w<=c)

return p;//裝入所有物品

//依物品單位重量排序

float f;

for( i=0;i

for(int j=i;j

}knap k;

k.p = new int[n+1];

k.w = new int[n+1];

k.x = new int[n+1];

k.bestx = new int[n+1];

k.x[0]=0;

k.bestx[0]=0;

for( i=1;i<=n;i++)

k.cp=0;

k.cw=0;

k.c=c;

k.n=n;

k.bestp=0;

//回溯搜尋

k.backtrack(1);

k.print();

delete q;

delete k.w;

delete k.p;

return k.bestp;

}void main()

最簡單的揹包問題！用c++！

2樓：傲世修羅王

求所有解可以用回溯法，求最優解一般用動態規劃或者貪心策略。

因為題目要求所有解，故採用回溯。

先建模：

此題目等價於自然數拆分，給定一個自然數n，將n拆分成n1 + n2 + ...+ nn,使得n1 + n2 + ...+ nn = n，且n1, n2, ...

nn中無重複數，求所有可能的拆分情況。這裡n相當於t，n1, n2,...nn相當於w1，w2，。。。

wn。建模完畢！

上**：

#include

using namespace std ;

// 儲存可行解

int a[100] ;

// 輸出一個可行解

void output(int *a, int n)// 驗證當前解是否可行

bool isok(int* a, int curindex, int curvalue)

// 對自然數n進行拆分，t用來控制拆分個數void partition(int n, int t, int *b) }

} int main(void)

;// 揹包容量為10，從b中選若干件物品，使這些物品總量為10partition(10, 0, b) ;

system("pause") ;

return 0 ;}

3樓：魔尊

#include"stdio.h"

const int n=10; //設定物體個數const int no=2;

#define weight 10 //限制質量#define num 100

int d[num]; //總質量int c[num][weight]; //對應的物體位置void best(int a,int n)}int k0=0,k1=k;

while(ko) //ko是物體個數的統計，當不能再多時賦值為0，退出迴圈

}if(k==k1)ko=-1; //物體個數不能再多時k0=k1;k1=k;ko++;

}int ok=0;

for(i=0;i

if(m==no)

printf("\n");

} }}

if(!ok) printf("no\n");

}void main()

相應的字母沒有完全按照你這題目來，希望你能看懂！

4樓：匿名使用者

這些問題自己想想或者查一下資料再做不是比問人更好嗎？

0-1揹包問題的回溯法中，剪枝用的上界函式問題

5樓：匿名使用者

不知道你**看的**，01揹包的分支限界法一般有2種剪枝

1、當去了i後體積超過揹包版容量，那麼剪去權該子樹，體積都超了價值再大也沒用。

2、當前價值+i子樹中所有物品的價值<=記錄的最優值，應該就是你說的把。

按單位價值貪心雖然不知道你具體指什麼，我的理解是i的單位價值很低就剪了，這應該是不對的，萬一i後面有個單位價值很高的怎麼辦。

另外，01揹包哪有人會用回溯法啊，這是多麼沒有效率的演算法啊，雖然有剪枝，但時間複雜度還是指數級的啊，你想想如果有10件物品的話，你的葉節點就有1024個了，如果100件的話，我。。。。。。！！

0-1揹包問題的多種解法**（動態規劃、貪心法、回溯法、分支限界法）

6樓：匿名使用者

一.動態規劃求解0-1揹包問題

/* 0-1揹包問題：

華為手機怎麼用回撤鍵，華為手機輸入法的換行鍵在哪裡？

華為手機由於實體的按鍵會讓下巴變得更寬，而現在的手機幾乎每一部新手機都是以全面屏為主要買點的，不得不用螢幕內的虛擬按鍵代替，從而讓手機變得更美觀 華為前置指紋解鎖前置擁有回撤鍵，例如榮耀9 mate 9 pro p10和p10 plus等。還有一種採用的是虛擬導航欄，可以在設定中設定導航欄樣式，代表...

limx 0 1 cosx 21 cos x 求極限過程

括號加得不太明確，應該是這樣吧？利用等價無窮小替換 lim x 0 1 cos x lim x 0 x 2 2 2 lim x 0 x 2 2。1 cosx 2 1 cos x sinx 2 1 cos x 4 sinx 2 2 cos x 2 2 2 sinx 2 2 2 cos x 2 原式 l...

什麼是交叉法求平均值法，什麼是十字交叉法求平均值法

十字交叉法是進行二組分混合物平均量與組分計算的一種簡便方法。詳見 十字交叉法 這是利用化合價書寫物質化學式的方法，它適用於兩種元素或兩種基團組成的化合物。其根據的原理是化合價法則 正價總數與負價總數的代數和為0或正價總數與負價總數的絕對值相等。現以下例看其操作步驟。二 十字交叉相比法 我們常說的十字...