本文目錄一覽：
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語言的窮舉法的背包問題
根據題目c1，c2是一組01組合的數組，也就是2個n位2進位數。
所以我的代碼邏輯就是，c1，c2初值分別是 00000….以及111111….，之後循環執行c1+1；c2-1（2進位加減運算），最大執行次數 2的n次方-1（n位2進位數最大數）
代碼實現功能，窮舉所有可能方案，返回:第一個 /最後一個找到的可行方案。
函數int qj(BAG c1,BAG c2,int n,int *bws,int flag);
當flag=1 返回第一個可行方案，flag=0 查找所有方案並返回最後一個可行方案
我測試時，flag傳值0，需要自己改！！
由於迭代順序，同樣實驗數據，返回的結構和你案例結構不一樣，我在下圖標註了。
#includestdio.h
#includemath.h
#includemalloc.h
#includestring.h
typedef struct bag
{
int bweight;
char *books;
}BAG;
int qj(BAG c1,BAG c2,int n,int *bws,int flag);//窮舉所有n位2進位組合，返回最後一個可行方案（可能有多個方案）。
//參數：c1背包1，c2背包2，n書本個數，bws所有書本重量，標識：flag=1 找到第一個可行方案截止，flag=0查找所有方案
int checkOverLoad(BAG c1,BAG c2,int *bws,int n);
void add2(char *nums);//2進位字元串+1運算
void sub2(char *nums);//2進位字元串-1運算
int main()
{
BAG c1,c2;
int i,n,*bws,sum=0;
printf(“請輸入兩個背包的最大載重：\n”);
scanf(“%d%d”,c1.bweight,c2.bweight);
printf(“請輸入書本的數量：\n”);
scanf(“%d”,n);
c1.books=(char *)malloc(sizeof(char)*(n+1));
c2.books=(char *)malloc(sizeof(char)*(n+1));
c1.books[0]=0;
c2.books[0]=0;
bws=(int *)malloc(sizeof(int)*n);
while(1)
{
sum=0;
printf(“請輸入每本書的重量：\n”);
for(i=0;in;i++)
{
scanf(“%d”,bws[i]);
sum+=bws[i];
}
if(sum=c1.bweight+c2.bweight)
break;
else
printf(“書本重量和超過背包負重和！請重新輸入\n\n”);
}
qj(c1,c2,4,bws,0);
//——————————列印結果—————————–
printf(“\n輸出：\n”);
printf(“book “);
for(i=0;in;i++)
printf(“%d “,bws[i]);
printf(“\n”);
printf(“c1 %s\n”,c1.books);
printf(“c2 %s\n”,c2.books);
}
int qj(BAG c1,BAG c2,int n,int *bws,int flag)// 窮舉 所有n位二進位數,
{
int i,max=(int)pow(2,n)-1;
char *nums1,*nums2;
nums1=(char *)malloc(sizeof(char)*(n+1));
nums2=(char *)malloc(sizeof(char)*(n+1));
printf(“———開始窮舉所有可能的組合———-\n”);
memset(c1.books,’0′,n);
memset(c2.books,’1′,n);
c1.books[n]=c2.books[n]=0;
printf(“%s\n”,c1.books);
printf(“%s\n”,c2.books);
if(checkOverLoad(c1,c2,bws,n)==0)
{
memset(nums1,0,n+1);
memset(nums2,0,n+1);
strcpy(nums1,c1.books);
strcpy(nums2,c2.books);
if(flag==1)
return 0;
}
printf(“\n”);
for(i=0;imax;i++)
{
add2(c1.books);
sub2(c2.books);
printf(“%s\n”,c1.books);
printf(“%s\n”,c2.books);
if(checkOverLoad(c1,c2,bws,n)==0)
{
memset(nums1,0,n+1);
memset(nums2,0,n+1);
strcpy(nums1,c1.books);
strcpy(nums2,c2.books);
if(flag==1)
return 0;
}
printf(“\n”);
}
printf(“—————–窮舉結束——————\n”);
memset(c1.books,0,n+1);
memset(c2.books,0,n+1);
strcpy(c1.books,nums1);
strcpy(c2.books,nums2);
free(nums1);
free(nums2);
return 0;
}
void add2(char *nums)//2進位字元串加1
{
int i,n=strlen(nums),jin=0;
for(i=n-1;i=0;i–)
{
if(nums[i]==’0′ i==n-1)
{
nums[i]=’1′;
break;
}
else if(nums[i]-‘0’+jin==1 in-1)
{
nums[i]=’1′;
break;
}
else
{
jin=1;
nums[i]=’0′;
}
}
}
void sub2(char *nums)//2進位字元串減1
{
int i,n=strlen(nums),j=0;
for(i=n-1;i=0;i–)
{
if(nums[i]==’1′ i==n-1)
{
nums[i]=’0′;
break;
}
else if(nums[i]-‘0’-j==0 i!=n-1)
{
nums[i]=’0′;
break;
}
else
{
nums[i]=’1′;
j=1;
}
}
}
int checkOverLoad(BAG c1,BAG c2,int *bws,int n)//檢查是否超載。超載返回1，否返回0
{
int i,sum1=0,sum2=0;
for(i=0;in;i++)
if(c1.books[i]==’1′)
sum1=sum1+bws[i];
else
sum2=sum2+bws[i];
if(sum1c1.bweight)
{
printf(“背包1超載！\n”);
return 1;
}
if(sum2c2.bweight)
{
printf(“背包2超載！\n”);
return 1;
}
printf(“方案可行！\n”);
return 0;
}
C語言：背包問題(數據結構)
詳細程序代碼如下:
用VC6.0編譯.保存代碼時,以.C為後綴名
下面是一組測試數據:
請輸入背包能容納的最大重量：20
請輸入物品個數：10
請輸入每一個物品的重量和價值：1,11,2,22, 3,33…..10,100
結果是正確的.
#includestdio.h
#includeconio.h
#includemalloc.h
#define NUMBER 20/*最大物品數量*/
#define TRUE 1
#define FALSE 0
struct Record/*本結構體用於保存每一次結果*/
{
int totalWeight;/*本次結果的總價值*/
int goods[NUMBER];/*本次結果對應的下標*/
struct Record *next;
};
struct Record *headLink;
struct Record result;
int stack[NUMBER];
int top;
int weight[NUMBER];/*保存物品重量的數組*/
int value[NUMBER];/*保存對應（下標相同）物品的價值*/
int knapproblen(int n,int maxweight,int weight[]);
void CreateHeadLink(void);
struct Record *MallocNode(void);
void InsertOneNode(struct Record *t);
void GetResult(void);
void ShowResult(void);
void main()
{
int n,i;
int maxWeight;/*背包能容納的最大重量*/
printf(“請輸入背包能容納的最大重量：\n”);
scanf(“%d”,maxWeight);
printf(“請輸入物品個數：\n”);
scanf(“%d”,n);
printf(“請輸入每一個物品的重量和價值：\n”);
for(i=0;in;i++)
{
printf(“請輸入第%d個物品重量\n”,i+1);
scanf(“%d”,(weight[i]));
printf(“請輸入第%d個物品價值\n”,i+1);
scanf(“%d”,(value[i]));
}
if(knapproblen(n,maxWeight,weight)==TRUE)/*調用背包處理函數，如果成功就輸出「答案」*/
{
GetResult();/*遍歷鏈表，查找最佳的結果*/
ShowResult();/*顯示結果*/
}
free(headLink);
getch();
}
/*調用背包處理函數*/
int knapproblen(int n,int maxweight,int weight[])
{
struct Record *p;
int i=1,j;
int tempTop=0;
top=0;/*先賦棧指針為0*/
CreateHeadLink();/*先建立鏈頭*/
while((maxweight0)(i=n))/*當還可以裝下物品，且物品沒有用完時*/
{
if((maxweight-weight[i]==0)||(maxweight-weight[i]0)(in))/*正好裝完物品或還能容納物品且物品沒有用完時*/
{
stack[++top]=i;/*把對應物品的處標保存到棧中*/
p=MallocNode();/*每一次得到一個結果後，就將該結果保存到鏈表中*/
for(tempTop=top,j=0;tempTop0;tempTop–,j++)
{
p-totalWeight+=value[stack[tempTop]];/*得到本次結果的總價值*/
p-goods[j]=stack[tempTop];/*得到本次結果對應的物品下標*/
}
InsertOneNode(p);/*加到鏈表中*/
maxweight=maxweight-weight[i];
}
if(maxweight==0)/*能裝入包中*/
{
return TRUE;
}
else if((i==n)(top0))/*繼續測試*/
{
i=stack[top];
top=top-1;
maxweight=maxweight+weight[i];
}
i++;
}
return FALSE;
}
/************************************
函數功能：建立鏈表表頭
************************************/
void CreateHeadLink(void)
{
struct Record *p;
p=(struct Record*)malloc(sizeof(struct Record));
headLink=p;
p-next=NULL;
}
/************************************
函數功能：申請一個新結點，並將其初始化
************************************/
struct Record *MallocNode(void)
{
struct Record *p;
int i;
p=(struct Record*)malloc(sizeof(struct Record));
if(p==NULL)
return NULL;
p-totalWeight=0;/*初始化總價值為0*/
for(i=0;iNUMBER;i++)
p-goods[i]=-1;/*初始化下標為-1，即無效*/
p-next=NULL;
return p;
}
/************************************
函數功能：在鏈表的結尾處增加一個結點
************************************/
void InsertOneNode(struct Record *t)
{
struct Record *p;
p=headLink;
while(p-next)
{
p=p-next;
}
p-next=t;
}
/************************************
函數功能：遍歷鏈表，找總價值最大的結點保存到
result中
************************************/
void GetResult(void)
{
struct Record *p;
int i;
result.totalWeight=headLink-next-totalWeight;/*先將第一個結點當作”最佳”結果*/
for(i=0;iNUMBER;i++)
{
if(headLink-next-goods[i]==-1)
break;
result.goods[i]=headLink-next-goods[i];
}
p=headLink-next-next;
while(p)/*查找最佳結果*/
{
if(p-totalWeightresult.totalWeight)/*如果發現p點價值比當前結果還大，則將p又作為最佳結果*/
{
result.totalWeight=p-totalWeight;
for(i=0;iNUMBER;i++)
result.goods[i]=-1;
for(i=0;iNUMBER;i++)
{
if(p-goods[i]==-1)
break;
result.goods[i]=p-goods[i];
}
}
p=p-next;
}
}
/***************************
顯示最佳結果
*******************************/
void ShowResult(void)
{
int i;
printf(“最佳裝載如下：\n”);
for(i=0;iNUMBER;i++)
{
if(result.goods[i]==-1)
break;
printf(“weight[%d]=%d\tvalue[%d]=%d\t”,result.goods[i],weight[result.goods[i]],result.goods[i],value[result.goods[i]]);
if((i+1)%2==0)
printf(“\n”);
}
printf(“\n總價值是：\n%d”,result.totalWeight);
}
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語言)
我copy一下別人的遞歸演算法，假如你有時間限時的話，那我就用動態規劃幫你重新code一個
#include stdio.h
#define N 100 //物品總種數不是常量，沒法根據它來決定數組的長度，只有先定義個長度了
int n;//物品總種數
double limitW;//限制的總重量
double totV;//全部物品的總價值
double maxv;//解的總價值
int option[N];//解的選擇
int cop[N];//當前解的選擇
struct {//物品結構
double weight;
double value;
}a[N];
//參數為物品i,當前選擇已經達到的重量和tw,本方案可能達到的總價值
void find(int i,double tw,double tv)
{
int k;
//物品i包含在當前方案的可能性
if(tw+a[i].weight = limitW){
cop[i]=1;
if(in-1)find(i+1,tw+a[i].weight,tv);
else{
for(k=0;kn;++k)
option[k]=cop[k];
maxv=tv;
}
}
cop[i]=0;
//物品i不包含在當前方案的可能性
if(tv-a[i].valuemaxv){
if(in-1)find(i+1,tw,tv-a[i].value);
else{
for(k=0;kn;++k)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}
}
void main()
{
int k;
double w,v;
printf(“輸入物品種數:”);
scanf(“%d”,n);
printf(“輸入各物品的重量和價值:”);
for(totV=0.0,k=0;kn;++k){
scanf(“%lf %lf”,w,v);
a[k].weight = w;a[k].value = v;
totV += v;
}
printf(“輸入限制重量:”);
scanf(“%lf”,limitW);
maxv=0.0;
for(k=0;kn;++k)cop[k]=0;
find(0,0.0,totV);
for(k=0;kn;++k)
if(option[k])printf(“%4d”,k+1);
printf(“總價值為: %2f”,maxv);
}
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/232551.html
微信掃一掃 
支付寶掃一掃 