1)登山算法
用登山算法求解背包問題 function []=DengShan(n,G,P,W) %n是背包的個數，G是背包的總容量，P是價值向量，W是物體的重量向量 %n=3;G=20;P=[25,24,15];W2=[18,15,10];%輸入量 W2=W; [Y,I]=sort(-P./W2);W1=[];X=[];X1=[]; for i=1:length(I) W1(i)=W2(I(i)); end W=W1; for i=1:n X(i)=0; RES=G;%背包的剩余容量 j=1; while W(j)<=RES X(j)=1; RES=RES-W(j); j=j+1; end X(j)=RES/W(j); end for i=1:length(I) X1(I(i))=X(i); end X=X1; disp('裝包的方法是');disp(X);disp(X.*W2);disp('總的價值是：');disp(P*X');
時間復雜度是非指數的
2)遞歸法
先看完全背包問題
壹個旅行者有壹個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,
每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max{f(x-i)+c[i]} 當x>=w[i] 1<=i<=n
可使用遞歸法解決問題程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,編程很簡單,但當m較大時,容易超時.
4.2 改進的遞歸法
改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函數的值保存起來,開辟壹個
壹維數組即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
3)貪婪算法
改進的背包問題：給定壹個超遞增序列和壹個背包的容量，然後在超遞增序列中選（只能選壹次）或不選每壹個數值，使得選中的數值的和正好等於背包的容量。
代碼思路：從最大的元素開始遍歷超遞增序列中的每個元素，若背包還有大於或等於當前元素值的空間，則放入，然後繼續判斷下壹個元素；若背包剩余空間小於當前元素值，則判斷下壹個元素
簡單模擬如下：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{/*產生超遞增序列*/
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{/*輸出當前的超遞增序列*/
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}
void beibao(long array[],int cankao[],long value,int count)
{/*背包問題求解*/
int i;
long r=value;
for(i=count-1;i>=0;i--)/*遍歷超遞增序列中的每個元素*/
{
if(r>=array[i])/*如果當前元素還可以放入背包，即背包剩余空間還大於當前元素*/
{
r=r-array[i];
cankao[i]=1;
}
else/*背包剩余空間小於當前元素值*/
cankao[i]=0;
}
}
void main()
{
long array[N];
int cankao[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)/*所有已經選中的元素之和*/
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
貪婪算法的另壹種寫法，beibao函數是以前的代碼，用來比較兩種算法：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}
void beibao(long array[],int cankao[],long value,int count)
{
int i;
long r=value;
for(i=count-1;i>=0;i--)
{
if(r>=array[i])
{
r=r-array[i];
cankao[i]=1;
}
else
cankao[i]=0;
}
}
int beibao1(long array[],int cankao[],long value,int n)
{/*貪婪算法*/
int i;
long value1=0;
for(i=n-1;i>=0;i--)/*先放大的物體，再考慮小的物體*/
if((value1+array[i])<=value)/*如果當前物體可以放入*/
{
cankao[i]=1;/*1表示放入*/
value1+=array[i];/*背包剩余容量減少*/
}
else
cankao[i]=0;
if(value1==value)
return 1;
return 0;
}
void main()
{
long array[N];
int cankao[N]={0};
int cankao1[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
printf("\nSecond method:\n");
if(beibao1(array,cankao1,value,N)==1)
{
for(i=0;i<N;i++)
if(cankao1[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
4)動態規劃算法
解決0/1背包問題的方法有多種，最常用的有貪婪法和動態規劃法。其中貪婪法無法得到問題的最優解，而動態規劃法都可以得到最優解，下面是用動態規劃法來解決0/1背包問題。
動態規劃算法與分治法類似，其基本思想是將待求解問題分解成若幹個子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的，若用分治法解這類問題，則分解得到的子問題數目太多，以至於最後解決原問題需要耗費過多的時間。動態規劃法又和貪婪算法有些壹樣，在動態規劃中，可將壹個問題的解決方案視為壹系列決策的結果。不同的是，在貪婪算法中，每采用壹次貪婪準則便做出壹個不可撤回的決策，而在動態規劃中，還要考察每個最優決策序列中是否包含壹個最優子序列。
0/1背包問題
在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對於可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示選取物品i) 取得最大值。
在該問題中需要決定x1 .. xn的值。假設按i = 1，2，...，n 的次序來確定xi 的值。如果置x1 = 0，則問題轉變為相對於其余物品(即物品2，3，.，n)，背包容量仍為c 的背包問題。若置x1 = 1，問題就變為關於最大背包容量為c-w1 的問題。現設r?{c，c-w1 } 為剩余的背包容量。
在第壹次決策之後，剩下的問題便是考慮背包容量為r 時的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第壹次決策之後的壹個最優方案，如果不是，則會有壹個更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是壹個更好的方案。
假設n=3, w=[100,14,10], p=[20,18,15], c= 116。若設x1 = 1，則在本次決策之後，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因為[x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 並非最優策略。即x= [ 1，0，1] 可改進為x= [ 1，1，0 ]。若設x1 = 0，則對於剩下的兩種物品而言，容量限制條件為116。總之，如果子問題的結果[x2，x3 ]不是剩余情況下的壹個最優解，則[x1，x2，x3 ]也不會是總體的最優解。在此問題中，最優決策序列由最優決策子序列組成。假設f (i,y) 表示剩余容量為y，剩余物品為i，i + 1，...，n 時的最優解的值，即：利用最優序列由最優子序列構成的結論，可得到f 的遞歸式為：
當j>=wi時： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式
當0<=j<wi時：f(i,j)=f(i+1,j) ②式
fn( 1 ,c) 是初始時背包問題的最優解。
以本題為例：若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。因此最優解f ( 1 , 11 6 ) = m a x {f(2，11 6)，f(2，11 6 - w1)+ p1} = m a x {f(2，11 6)，f(2，1 6)+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
現在計算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩余容量c-w1中尋求最優解，用f (2, c-w1) 表示最優解。依此類推，可得到所有的xi (i= 1.n) 值。
在該例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計算x2 及x3，此時r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。