⑴ 用分治法處理0-1背包的演算法
設有一個背包，可以放入的重量為s。現在n件物品，重量分別為w1,w2,…,wn，並假設wi(1≤i≤n)均為正整數
program kic;
const M=10;{物品的件數}
var
w:array [1..M] of integer;{W[i]—第i件物品的重量}
x,y,i:integer;{x,y—選中的物品的重量和及其件數}
f:boolean; }
function knap(s,n:integer):boolean;
begin
if s=0 then knap:=true
else if (s<0) or ((s>0) and (n<1))
{產生的不合理結果說明方案不可能存在}
then knap:=false
else begin
if knap(s-w[n],n-1)=true {選中物品n}
then begin
writeln('number:',n:4,' weight:',w[n]:4);
knap:=true;
end
else knap:=knap(s,n-1);
{在除物品n外的n-1件物品中遞歸選擇}
end;
end;
begin
fillchar(w,sizeof(w),0);{初始化}
write('object number=');{輸入選中的物品的件數}
repeat readln(y); until y<=M;
write('total weight=');{輸入選中物品的重量和}
readln(x);
for i:=1 to y do read(w[i]);{輸入每物品的重量}
f:=knap(x,y);{遞歸求解背包問題}
if not(f) then writeln('not find');
{若背包中放不下重量和為X的Y件物品,則輸出無解信息}
end.
⑵ 什麼是0-1背包問題和背包問題，適用什麼演算法求解
動態規劃、貪心法、回溯法、分支限界法
⑶ 用動態規劃演算法怎樣求解01背包問題
動態規劃主要解決的是多階段的決策問題。
01背包中，狀態為背包剩餘的容量，階段是每一個物品，決策是是否選擇當前的物品。
所以用動態規劃來解決是非常貼切的。
我們設f[V]表示已經使用容量為V時所能獲得的最大價值，w[i]表示i物品的質量，c[i]表示i物品的價值。
for(inti=1;i<=n;i++)
for(intj=V;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);
這便是所謂的一個狀態轉移方程。
f[j]表示在已經使用容量為j時的最大價值，f[j-w[i]]表示在已經使用容量為j-w[i]時的最大價值。
f[j]可以由f[j-w[i]]這個狀態轉移到達，表示選取w[i]這個物品，並從而獲得價值為c[i]。
而每次f[j]會在選與不選中決策選出最優的方案。
從每一個物品，也就是每一個階段的局部最優推出最後的全局最優值。這樣就解決了01背包問題
⑷ 求解釋01背包問題
這個是狀態轉移方程
f[v] 表示背包剩餘容量V時候積累的價值總和
你這個是優化版本的只用了一維數組 有個更基本的方法我解釋給你聽
有n件物品 假設當前到第i件了
{ f[i - 1][v];
f[i][v](到第i件時 此時容量為v ) = {
{ f[i - 1][v - w[i]] + p[i];（v>=w[i]）
(兩者中較大的那個)
「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」，價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
⑸ 動態規劃的0-1背包問題，請高手解釋下代碼
這是清華演算法設計C++描述上的代碼吧？呵呵 我正巧讀過。
簡單解釋一下吧 在解釋之前你要知道動態規劃是一個自底向上的過程
這個演算法用到了一個二維數組m[][] 來存儲各個坐標的價值信息 所以橫坐標表示背包號碼 縱坐標表示背包容量從1到c
注意該演算法只能限制c是整數且每個背包的重量也是整數.
然後int jMax=min(w[n]-1,c);找出w[n]-1和 c之間的小者。
for(int j=0;j<=jMax;j++) m[n][j]=0;表示第n個物品不選 那麼所以價值為0
for(int j=w[n];j<=c;j++) m[n][j]=v[n];表示第n個物品選擇 所以價值為v[n]
for(int i=n-1;i>1;i--){
jMax=min(w[i]-1,c);
for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
表示自n-1到2逐層計算各m[i][j]的值 每一個m[i][j]的值都是根據上一層也就是m[i][j+1] 得到的 最後處理個第一層的邊界條件 m[1][c]就是所得答案了
⑹ 解決0-1背包問題需要排序的有哪些演算法
用貪心演算法求解0-1背包問題的步驟是，首先計算每種物品單位重量的價值vi/wi；然後，將物品的vi/wi的大小進行降序進行排列，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包後，背包內的物品總量未超過c，則選擇單位重量價值次高的物品並盡可能多地裝入背包。依此策略一直進行下去，直到背包裝滿為止。
⑺ 01背包問題
能不能用性價比來做呢
動態規劃看不懂啊
----------------------------------------------------------------------
如果不是0-1問題的話，當然可以通過比較性價比來做，這時候可考慮用貪心演算法；但如果是0-1問題的話就不能單純「用性價比來做」了，因為有可能背包空出一大塊。舉個簡單的例子：一個背包的容量是10KG，
物品A重7KG，價值為14元，
物品B重6KG，價值為11元，
物品C中4KG，價值為7元，
從性價比來看，A最高，但是將A放到背包里以後，無法放進其他物品了，此時總價值為14元；顯然，本問題的最佳方案為將B、C放入背包，總價值為18元。
這就是0-1背包問題為什麼能用動態規劃演算法，而不能用貪心演算法的原因。共同學習:-D
⑻ 01背包問題，程序求解
把這一句：int f[maxn],t[maxn],v[maxn];
放到main()的前面去，或者定義後就立即賦值為0。
因為局部變數初始化的值是不確定的，但保證全局變數都被初始化為0。
還有你最後：cout<<f[T];這個含義是否正確取決於題目怎麼說，如果要求正好填滿背包，那麼這就是對的。
⑼ 0-1背包問題用什麼實現演算法最好
我們書上給的0-1背包問題是是用動態規劃方法做的這個演算法是動態規劃的典型應用所以你把動態規劃的思想搞清楚就應該可以理解了下面我把動態規劃的思想給你說一下,希望對你有所幫助.哦..不好意思..時間不多了..你自己到網上找一下這方面的思想..然後結合一個實例認真研讀一下..弄懂之後..你對動態規劃..0-1背包問題就會有比較深入的理解.建議好好學一下演算法..這對計算機專業學生來說很重要..我越來越覺得祝學有所成