本文目錄一覽：
c語言背包問題，求高手解答
對01背包求解，方法有回溯法、分支限界法、動態規劃法等。給你一個較容易理解的解法：窮舉搜索。問題求解的結果實際上是一個01序列，0表示該物品未裝入背包，1表示裝入背包。以本題為例，設求解結果為0111011，表示第0個和第4個未裝入，其他均裝入。關鍵就是如何找到這個01序列。設物品數量為n，則解空間為2^n，所以窮舉搜索的時間效率為O(2^n)。
#include stdio.h
#define N 7
int weight[N]={35, 30, 6, 50, 40 10, 25}, cost[N]={10, 40, 30, 50, 35, 40, 30};
char name[] = “ABCDEFG”;
int max = 0, Max[N]; /*max用於存放最大價值，Max用於存放最優解向量*/
int v[N]; /*v：求解時用於存放求解過程向量*/
template class T
void Swap(T a, T b)
{
T tmp = a;
a = b, b = tmp;
}
void Knapsack(int step, int bag, int value1, int value2, int n)
/*step表示第step步的選擇（即第step個物品的選擇），bag為背包剩餘容量，value1表示包中現有物品總價值，value2表示剩餘物品總價值，n為物品總數量*/
{
int i;
if((step = n) || (weight[step] bag) || (value1 + value2 = max)) /*如果所有物品都選擇完畢或剩餘的物品都放不進或者包中物品總價值與剩餘物品總價值之和小於等於目前的已知解，則找到一個解(但不一定是最終解或更優解)*/
{
for(i = step; i n; i++) v[i] = 0; /*剩餘的物品都不放入*/
if(value1 max) /*如果本次求得的解比以往的解更優，則將本次解作為更優解*/
{
max = value1;
for(i = 0; i n; i++) Max[i] = v[i]; /*將更優解保存到Max向量中*/
}
return;
}
v[step] = 0, Knapsack(step + 1, bag, value1, value2 – cost[step], n); /*不將第step個物品放入背包，第step個物品的價值被放棄，進行下一步的選擇*/
v[step] = 1, Knapsack(step + 1, bag – weight[step], value1 + cost[step], value2 – cost[step], n); /*將第step個物品放入背包，進行下一步的選擇*/
}
void main( )
{
/*輸入數據：背包容量、物品數量、重量、價值 代碼略*/
int bag = 150, i, j, min, totalcost;
/*按物品重量從小到大的順序對物品排序，排序時cost向量中的相對順序也要作相應移動*/
for(i = 0; i N – 1; i++) {
for(min = i, j = i + 1; j N; j++)
if(weight[j] weight[min]) min = j;
if(i != min) {
Swap(weight[i], weight[min]);
Swap(cost[i], cost[min]);
Swap(name[i], name[min]);
}
}
for(totalcost = 0, i = 0; i N; i++) totalcost += cost[i]; /*求總價值*/
Knapsack(0, bag, 0, totalcost, N); /*bag為空背包容量, totalcost為物品總價值, N為物品數量*/
/*以下輸出解*/
printf(“最大價值為: %d。\n裝入背包的物品依次為：\n”, max);
for(i = 0; i N; i++)
if(Max[i]) printf(“%c\t”, name[i]);
printf(“\n”);
}
我的回答你滿意嗎？如果滿意，就請採納哦，或者你也可以繼續追問。
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語言 背包問題 遞歸算法
提問者的這程序中用了遞歸算法，不過邏輯上有個小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語言背包問題遞歸算法
你學過數據結構了嗎？如果學過，那就比較好理解，該算法的思路和求二叉樹的高度的算法的思路是十分類似的。把取這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語言01背包問題誰能簡單說下
01背包問題就是有個容量為W的包，然後有一堆的物品(1…n)，其中wi、vi分別為第i個物品的重量和價值，現在需要求的就是使得包中所裝的物品儘可能的價值高。那麼這個物品放不放在包中對應取值0
or
1。其算法為動態規劃，需要證明最優子結構性質。用s[i][j]表示只有前i個物品且包容量為j時所能等到的最大價值，而有遞歸式
s[i][j]=
s[i-1][j],
wij
max{s[i-1][j],s[i-1][j-wi]+vi},
wi=j
s[0][j]=0
1=j=W
s[i][0]=0
1=i=n
所以不論用什麼語言實現，就是計算上面的式子，最終求得s[n][W]，上面的式子很好用遞推實現的，這個是自底向上的，就是兩層for；你也可以用棧實現自頂向下的，這個是記錄式的方法。
以上的W是只考慮整數的。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/157514.html
微信掃一掃 
支付寶掃一掃 