文章目錄

注明：題目要求只能使用蠻力法

算法標簽：全排列，枚舉，二進制，dfs，數(shù)組

題目簡介

思路

AC代碼

方法一：字符串蠻力

方法二：二進制枚舉

方法三：DFS

三.２閆老板思考角度

方法四：全排列

方法五：數(shù)組蠻力

答案

注明：題目要求只能使用蠻力法

算法標簽：全排列，枚舉，二進制，dfs，數(shù)組

題目簡介

0/1背包問題【算法中非常經(jīng)典的一個例題，多種不同的算法可以來實現(xiàn)】

有n個重量分別是w1,w2…,wn的物品(物品編號為1-n)

它們的價值分別為v1,v2,…,vn

給定一個容量為W的背包。設(shè)計從這些物品中選取一部分放入該背包的方案。

每個物品要么選中要么不選中【每種物品是唯一的】，

要求選中的物品不僅能夠放在背包中【能放得下】，而且具有最大的價值。

并對如下所展示的5個物品求出W=10時的最佳解。

物品編號 重量 價值

1 2 6

2 2 3

3 6 5

4 5 4

5 4 6

分析：并對如的5個物品求出W不超過10時的最佳解。

思路

我們設(shè)定有五個物品

五個物品一開始都不選

用string表示為 00000

用j來控制狀態(tài)選擇

1

我們可以利用窮舉寫出5個變量的全排列

而5個變量分別可以代表的當(dāng)前狀態(tài)下的當(dāng)前位子的選擇

于是我們建立新的字符串，全排列的中的狀態(tài)賦值即可，這樣我們就得到了所有可能的選擇狀態(tài)。

然后更新maxv和str即可

2

用二進制枚舉

形如1000001

11110001

1表示選擇，0表示未選擇的方式

可參考我寫的得到整數(shù)X

AC代碼

方法一：字符串蠻力

#include

#include

#include

using namespace std;

int main()

{

int W = 10, n = 5;

int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };

string pres = "00000";

int ww = 0, vv = 0, maxv = 0;

string str;

char s[1000];

for (int j = 0; j < 5; j++)

for (int a = 0; a < 5; a++)

for (int b = 0; b < 5; b++)

for (int c = 0; c < 5; c++)

for (int d = 0; d < 5; d++)

for (int e = 0; e < 5; e++)

{

if (a != b && a != c && a != d && a != e);

if (b != c && b != d && b != e);

if (c != d && c != e);

if (d != e);

pres[j]='1';

s[0] = pres[a];

s[1] = pres[b];

s[2] = pres[c];

s[3] = pres[d];

s[4] = pres[e];

//cout << s[0] << " " << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << " " << endl;

for (int i = 0; i < 5; i++)ww += (s[i] - '0')*w[i], vv += (s[i] - '0')*v[i];

//當(dāng)前背包重量不超過容量，且vv當(dāng)前背包價值大于最大價值

if (ww <= W && vv > maxv)maxv = vv, str = s;//記錄此時的s的組合

vv = 0, ww = 0;

}

for (int i = 0; i < 5; i++)cout << str[i];

cout << endl;

cout << maxv << endl;

return 0;

}

方法二：二進制枚舉

#include

using namespace std;

int ww,vv,maxv,strres;

int main()

{

int W = 10;

int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };

for(int i=0;i<1<<5;i++)//二進制最大可能選擇數(shù)

{

for(int j=0;j<5;j++)ww += (i>>j&1)*w[j], vv += (i>>j&1)*v[j];/判斷當(dāng)前位子是否被選擇,更新0或1倍目標值的數(shù)值

if (ww <= W && vv > maxv)maxv = vv,strres=i;//更新

vv = 0, ww = 0;

}

for(int i=0;i<5;i++)cout<>i&1);//因為是選擇情況，所以直接輸出

cout<

cout << maxv;

return 0;

}

方法三：DFS

無法保存最大路徑

#include

using namespace std;

int ww,vv,maxv,strres;

int W = 10;

int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };

int str[5];

int ans[5];

void dfs(int tw,int ans)

{

if(tw<=W&&ans > maxv){maxv = ans;return ;}

for(int i=0;i<5;i++)

if(!str[i]&&tw>=w[i])

{

str[i]=1;

dfs(tw-w[i],ans+v[i]);

str[i]=0;

}

}

int main()

{

dfs(W,0);

cout << maxv;

return 0;

}

三.２閆老板思考角度

#include

using namespace std;

int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };

int x[5];

int maxv = 0;

int ans[5];

void dfs(int i, int ww, int vv)

{

if (i == 5)

if (ww <= 10 && vv > maxv) { maxv = vv; for(int i=0;i<5;i++)ans[i]=x[i];return; }//記錄最優(yōu)狀態(tài)

else return;//這里給他加了個退出

x[i] = 1;

dfs(i + 1, ww + w[i], vv + v[i]);

x[i]=0;

dfs(i + 1, ww, vv);

}

int main()

{

dfs(0, 0, 0);

for(auto x:ans)cout<

cout<

cout << maxv;

return 0;

}

方法四：全排列

利用next_permuatation的特性，全排列，而我們只需要截取前面五位的狀態(tài)即可

#include

#include

#include

using namespace std;

int main()

{

int W = 10, n = 5;

int w[5] = {2, 2, 6, 5, 4}, v[5] = {6, 3, 5, 4, 6};

string s = "0000011111";

int ww = 0, vv = 0, maxv = 0;

string str;

for (int j = 0; j < n; j++)

{

do

{

for (int i = 0; i < n; i++)ww += (s[i] - '0') * w[i], vv += (s[i] - '0') * v[i];

//當(dāng)前背包重量不超過容量，且vv當(dāng)前背包價值大于最大價值

if (ww <= W && vv > maxv)maxv = vv, str = s; //記錄此時的s的組合

vv = 0, ww = 0;

} while (next_permutation(s.begin(),s.end()));

}

for(int i=0;i<5;i++)cout << str[i];

cout<

cout << maxv;

return 0;

}

方法五：數(shù)組蠻力

利用數(shù)組表示01

#include

#include

#include

using namespace std;

int s[5];

int main()

{

int W = 10, n = 5;

int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 };

int ww = 0, vv = 0, maxv = 0;

string str;

for (s[0]=0; s[0] < 2; s[0]++)

for (s[1]=0; s[1] < 2; s[1]++)

for (s[2]=0; s[2] < 2; s[2]++)

for (s[3]=0; s[3] < 2; s[3]++)

for (s[4]=0; s[4] < 2; s[4]++)

{

for (int i = 0; i < 5; i++)ww += (s[i])*w[i], vv += (s[i])*v[i];

if (ww <= W && vv > maxv)maxv = vv;

vv = 0, ww = 0;

}

cout << maxv << endl;

getchar(); getchar();

return 0;

}

答案

11001

15

總結(jié)

以上是生活随笔為你收集整理的java蛮力法背包问题_[算法课]五种蛮力法解决01背包问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。