背包優化演算法
A. 背包問題用分治演算法怎麼解決
分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。
我的想法是，比如背包承重是m，物品t[]分別是t1,t2,...tn,
演算法pakage(m,t[],p[])，最簡單的演算法思路就是把物品ti(1<=i<=n)放入背包，然後問題就變成在背包m-ti的承重下，盛放物品newt[](newt[]=t[]-ti)，用遞歸方法可以很簡單的描述，最後p[]就是得到的結果.但是這么做演算法復雜度非常高，所以必須優化。只是給你提供一個思路，希望有用
pakage(m,t[],p[]){
if(m==0||t.length()==0){
return;
}
if(null!=t){
for(int i=0;i<t.length;i++){
//把t[i]放入背包
//newt[]=t-t[i];
package(m-t[i],newt[],p[]);
}
}
}
B. 背包問題的發展歷程及研究現狀
背包問題是組合優化學科中一個經典而著名的問題，它的研究價值不言而喻，吸引了眾多專家學者從各個角度開展對其的研究工作，各種演算法設計思想也應運而生。由於背包問題的NP完全性，如何在演算法的時間效率和求解精度上取得有效的平衡，成為背包問題演算法設計主要的考慮因素。數據挖掘是近幾年信息領域發展最快的技術之一。由於數據挖掘具有強大的發現有用知識的功能，可以利用它來發現背包問題解的相似的狀態空間，然後進行約減，從而克服背包問題的NP困難性。
背包問題，是用來介紹動態規劃演算法最經典的例子，網上關於01背包問題的講解也很多，我寫這篇文章力爭做到用最簡單的方式，最少的公式把01背包問題講解透徹。
01背包的狀態轉換方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]表示在前i件物品中選擇若干件放在承重為 j 的背包中，可以取得的最大價值。
Pi表示第i件物品的價值。
決策：為了背包中物品總價值最大化，第 i件物品應該放入背包中嗎 ？
C. C語言演算法求助：背包問題
//如果每種商品只有一件，是0-1背包問題
讀入的數據N代表物品個數
V代表背包容量。
//對於你的例子
，輸入為
//5
16
//2
3
//3
2
//4
3
//5
7
//6
9
//輸出為21
#include
<iostream>
using
namespace
std;
#define
MAXSIZE
1000
int
f[MAXSIZE
+
1],
c[MAXSIZE
+
1],
w[MAXSIZE
+
1];
int
main()
{
int
N,
V;
cin
>>
N
>>
V;
int
i
=
1;
for
(;
i
<=
N;
++i)
{
cin
>>
c[i]
>>
w[i];
}
for
(i
=
1;
i
<=
N;
++i)
{
for
(int
v
=
V;
v
>=
c[i];
--v)
//c[i]可優化為bound,
bound
=
max
{V
-
sum
c[i,...n],
c[i]}
{
f[v]
=
(f[v]
>
f[v
-
c[i]]
+
w[i]
?
f[v]
:
f[v
-
c[i]]
+
w[i]);
}
}
//當i=N時，可以跳出循環單獨計算F[V]
cout
<<
f[V]
<<
'\n';
system("pause");
return
0;
}
//如果每種可以有多個，是完全背包問題，
D. 用C/C++實現組合演算法，背包問題以及優化演算法
我有大量演算法代碼。。搞ACM的飄過~~
我695033480，咱們可互相探討演算法知識。
E. 背包動態規劃演算法怎麼輸出選擇了哪個物品，將選擇的物品一一輸出，怎麼寫代碼
抽象之後問題轉化為求一個最優化數組，x1，x2，...，xn的0-1序列
具體的步驟：
定義v[i，w]為把前i個物體中的若干個，放到容量為w的背包里產生的最大價值
wi為第i個物品的大小
vi為第i個物品的價值
1）v[0,w] = 0, 背包裡面沒有東西，背包容量為w, 價值為0
2）v[i, 0] = 0, 背包容量為0，不論i為多少，價值均為0
3）對於第i個物品有兩種選擇，放進背包或者不放
如果wi > w, 即背包容量不夠放進第i個物品 v[i,w] = v[i-1,w];
如果wi<= w, 即背包容量還可以放進第i個物品，可以選擇放或者不放，選擇的標准就是讓總價值最大
v[i,w] = max( v[i-1,w], ( v[i-1, w - wi ] + vi ) );
同時，記錄v[i,w]的x1、x2、x3...xn的值（每個是0或者1）。這里需要用一個三維數組保存了。
不知道lz看懂沒有
F. 背包問題的目標函數和貪心演算法最優化量度相同嗎
背包問題的目標函數和貪心演算法最優化量度相同嗎？
不相同。目標函數：獲得最大利潤。最優量度：最大利潤/重量比
G. 什麼是背包演算法啊可以說的詳細一點嗎謝謝大家了```
該演算法是根據數學上的背包問題設計的。背包問題是一個最優化問題，即對一個給定空間或負重的背包和許多大小不一的物體，哪些物體放入背包才能使得浪費的背包空間或負重最小？在背包很小和物體數目較少時，這個問題還比較容易解決；但當背包很大且有很多個物體時，問題的求解就十分困難。通常，這個問題會有一個或者多個解，也有可能根本沒有解。
1977年，Merkle與Hellman合作設計了使用背包問題實現信息加密的方法。其工作原理是：假定甲想加密，則先產生一個較易求解的背包問題，並用它的解作為專用密鑰；然後從這個問題出發，生成另一個難解的背包問題，並作為公共密鑰。如果乙想向甲發送報文，乙就可以使用難解的背包問題對報文進行加密，由於這個問題十分難解，所以一般沒有人能夠破譯密文；甲收到密文後，可以使用易解的專用密鑰解密。
該演算法提出以後，經過多年的探討和研究，最終發現了它的一個致命錯誤，使之失去了任何保密的實用價值。