c語言背包遞歸,c語言遞歸漢羅塔

本文目錄一覽：

• 1、C語言背包問題遞歸算法
• 2、C語言 簡單的背包問題 遞歸 求大神幫忙看看 十分感謝啊
• 3、C語言 背包問題 遞歸算法
• 4、C語言，背包問題，用遞歸算法，下面這個怎麼編程，謝謝！

C語言背包問題遞歸算法

你學過數據結構了嗎？如果學過，那就比較好理解，該算法的思路和求二叉樹的高度的算法的思路是十分類似的。把取這i個物體看成i個階段，則該二叉樹有i+1層。其中空背包時為根結點，左孩子則為放棄了第1個物品後的背包，右孩子為選取了第1個物品後的背包。今後在對第i個物品進行選擇時，向左表示放棄，向右表示選取。則遞歸算法可如下：

int fun(int s, int i, int n) //s傳入的是背包容量, i是進行第i個物品的選取，n為剩餘物品的件數

{

if(s == 0) return 有解；

else if(剩餘的每件物品都裝不進|| n == 0) return 無解；

L = fun(s, i + 1, n – 1); //放棄第i個物品，則下一步的背包容量仍為s，然後看其是否有解，(遞歸調用進入左子樹)

R = fun(s – wi, i + 1, n – 1); //選取第i個物品，則下一步的背包容量為s-wi，然後看其是否有解，(遞歸調用進入右子樹)

return (l, r); //綜合考慮左右兩邊，看哪邊是正解或都無解。其實應該返回 return (L||R);

}

C語言 簡單的背包問題 遞歸 求大神幫忙看看 十分感謝啊

我改變了在VC + +6.0，你看它。主要的問題是要找到一個素數算法。 = N/10; B = N％10 = B + A = N/10改變; B = N％10，C = 10 * B + A ==;

BR / ＃＃包括“stdafx.h中”

“包括”math.h的“

無效的蘇薯（N）

{INT I，K1，K2，A，乙，C;

K1 =開方（N）;

（I = 2; N + +）

= 0）; /如果（我 = K1 +1）

{= N/10，B = N％10，C = 10 * B + A;

K2 = SQRT（C）; BR /（= 2 C，I + +）

（C == 0）;

（ = K +1）

printf的（4D，N）;

}

a

}

無效的主要（）

{N;

（= 10，N 100，N +）

蘇薯（N）;

getchar函數（）;

}

C語言 背包問題 遞歸算法

提問者的這程序中用了遞歸算法，不過邏輯上有個小bug，就是在判斷到n==0時，如果還有容量，那麼返回的應該是第一個物品的重量而不是0。你可以改變容量C或物品參數來檢驗算法的邏輯正確性。

關於輸出選擇的物品，我加了一個數組，用來標記選擇的物品。因為做完所有遞歸後只有最外層的標記是有效的，所以最後用了一個for循環來完成各層的標記。下面是改動後的程序：

    int a[5]={0};

int MaxW(int n, int C, int *Volunme, int *Weight)

{

int W=0,W1=0,W2=0;

if (n == 0)

{

if(C = Volunme[0])

{

a[0]=1;

return W=1;

}

else

return 0;

}

else if(C = Volunme[n])//背包剩餘空間可以放下物品n

{

W1 = MaxW(n-1, C-Volunme[n],Volunme,Weight) + Weight[n]; //放入n所能得到的重量

W2 = MaxW(n-1,C,Volunme,Weight); //不放n所能得到的重量

W=(W1W2?W1:W2);

a[n]=(W1W2?1:0);

}

else//背包空間放不下n,返回判斷放n-1的情況

{

return MaxW(n-1,C,Volunme,Weight);

}

return W;

}

int main(void)

{

int n=5;int C=7;

int Volunme[] = {1,2,3,4,5};

int Weight[] = {1,2,5,7,8};

printf(“最大重量為%d\n”,MaxW(n-1,C,Volunme,Weight));

for(int i=n-2;i=0;i–)

{

a[i]=0;

if(a[i+1]==1)

{

C-=Volunme[i+1];

Weight[i+1]=0;

}

MaxW(i,C,Volunme,Weight);

}

printf(“選擇的物品號是：”);

for(int i=0;i5;i++)

{

if(a[i]==1)

printf(“#%d  “,i+1);

}

printf(“\n”);

return 0;

}

C語言，背包問題，用遞歸算法，下面這個怎麼編程，謝謝！

#include stdio.h

#define V 500 //最多體積

#define W 100 //最多重量

#define N 5 //物品種類

typedef struct data{

int v; //體積

int w; //重量

int n; //數量

int x; //價值

}DATA;

DATA s[N]={

{30,3,10,4},

{50,8,10,5},

{10,2,10,2},

{23,5,8,3},

{130,20,5,11}

};

//返回a方案的價值

int xfangan(int *a,int n){

int sum=0,i;

for(i=0;in;i++)

sum+=s[i].x*a[i];

return sum;

}

//返回a方案的重量

int wfangan(int *a,int n){

int sum=0,i;

for(i=0;in;i++)

sum+=s[i].w*a[i];

return sum;

}

//返回a方案的體積

int vfangan(int *a,int n){

int sum=0,i;

for(i=0;in;i++)

sum+=s[i].v*a[i];

return sum;

}

//顯示max方案的信息

void showmax(int *max){

int i;

for(i=0;iN;i++) printf(“%d “,max[i]);

printf(“重量=%d 體積=%d 價值=%d\n”,wfangan(max,N),vfangan(max,N),xfangan(max,N));

}

//選擇方案

void dofangan(int *max,int *fa,int n){

int i;

if (n=N) return;

for(fa[n]=0;fa[n]=s[n].n;fa[n]++){

if (vfangan(fa,n+1)V) break; //超大

if (wfangan(fa,n+1)W) break; //超重

if (xfangan(fa,n+1)xfangan(max,N)){ //更有價值

for(i=0;i=n;i++) max[i]=fa[i];

for(i=n+1;iN;i++) max[i]=0;

}

dofangan(max,fa,n+1);

}

}

int main(){

int max[N],fa[N],i;

for(i=0;iN;i++) max[i]=0; //最高價值方案初值

dofangan(max,fa,0); //遞歸查找價值最高方案

showmax(max); //顯示最高價值方案

}