c語言背包問題(C語言背包問題)

c語言01背包問題誰能簡單說下

01背包問題就是有個容量為W的包，然后有一堆的物品(1...n)，其中wi、vi分別為第i個物品的重量和價值，現(xiàn)在需要求的就是使得包中所裝的物品盡可能的價值高。那么這個物品放不放在包中對應(yīng)取值0
or
1。其算法為動態(tài)規(guī)劃，需要證明最優(yōu)子結(jié)構(gòu)性質(zhì)。用s[i][j]表示只有前i個物品且包容量為j時所能等到的最大價值，而有遞歸式
s[i][j]=
s[i-1][j],
wi>j
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
所以不論用什么語言實現(xiàn)，就是計算上面的式子，最終求得s[n][W]，上面的式子很好用遞推實現(xiàn)的，這個是自底向上的，就是兩層for；你也可以用棧實現(xiàn)自頂向下的，這個是記錄式的方法。
以上的W是只考慮整數(shù)的。

c語言的窮舉法的背包問題

根據(jù)題目c1，c2是一組01組合的數(shù)組，也就是2個n位2進制數(shù)。
所以我的代碼邏輯就是，c1，c2初值分別是00000....以及111111....，之后循環(huán)執(zhí)行c1+1；c2-1（2進制加減運算），最大執(zhí)行次數(shù)2的n次方-1（n位2進制數(shù)最大數(shù)）

代碼實現(xiàn)功能，窮舉所有可能方案，返回:第一個/最后一個找到的可行方案。

函數(shù)intqj(BAGc1,BAGc2,intn,int*bws,intflag);
當(dāng)flag=1返回第一個可行方案，flag=0查找所有方案并返回最后一個可行方案
我測試時，flag傳值0，需要自己改！！

由于迭代順序，同樣實驗數(shù)據(jù)，返回的結(jié)構(gòu)和你案例結(jié)構(gòu)不一樣，我在下圖標(biāo)注了。

#include<stdio.h>
#include<math.h>
#include<malloc.h>
#include<string.h>
typedefstructbag
{
intbweight;
char*books;
}BAG;
intqj(BAGc1,BAGc2,intn,int*bws,intflag);//窮舉所有n位2進制組合，返回最后一個可行方案（可能有多個方案）。
//參數(shù)：c1背包1，c2背包2，n書本個數(shù)，bws所有書本重量，標(biāo)識：flag=1找到第一個可行方案截止，flag=0查找所有方案
intcheckOverLoad(BAGc1,BAGc2,int*bws,intn);
voidadd2(char*nums);//2進制字符串+1運算
voidsub2(char*nums);//2進制字符串-1運算
intmain()
{
BAGc1,c2;
inti,n,*bws,sum=0;
printf("請輸入兩個背包的最大載重：\n");
scanf("%d%d",&c1.bweight,&c2.bweight);
printf("請輸入書本的數(shù)量：\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;i<n;i++)
{
scanf("%d",&bws[i]);
sum+=bws[i];
}
if(sum<=c1.bweight+c2.bweight)
break;
el
printf("書本重量和超過背包負重和！請重新輸入\n\n");
}


qj(c1,c2,4,bws,0);
//------------------------------打印結(jié)果-----------------------------
printf("\n輸出：\n");
printf("book");
for(i=0;i<n;i++)
printf("%d",bws[i]);
printf("\n");
printf("c1%s\n",c1.books);
printf("c2%s\n",c2.books);
}
intqj(BAGc1,BAGc2,intn,int*bws,intflag)//窮舉所有n位二進制數(shù),
{
inti,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");
memt(c1.books,'0',n);
memt(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)
{
memt(nums1,0,n+1);
memt(nums2,0,n+1);
strcpy(nums1,c1.books);
strcpy(nums2,c2.books);
if(flag==1)
return0;
}
printf("\n");
for(i=0;i<max;i++)
{
add2(c1.books);
sub2(c2.books);
printf("%s\n",c1.books);
printf("%s\n",c2.books);
if(checkOverLoad(c1,c2,bws,n)==0)
{
memt(nums1,0,n+1);
memt(nums2,0,n+1);
strcpy(nums1,c1.books);
strcpy(nums2,c2.books);
if(flag==1)
return0;
}
printf("\n");
}
printf("-----------------窮舉結(jié)束------------------\n");
memt(c1.books,0,n+1);
memt(c2.books,0,n+1);
strcpy(c1.books,nums1);
strcpy(c2.books,nums2);
free(nums1);
free(nums2);
return0;
}
voidadd2(char*nums)//2進制字符串加1
{
inti,n=strlen(nums),jin=0;
for(i=n-1;i>=0;i--)
{
if(nums[i]=='0'&&i==n-1)
{
nums[i]='1';
break;
}
elif(nums[i]-'0'+jin==1&&i<n-1)
{
nums[i]='1';
break;
}
el
{
jin=1;
nums[i]='0';
}
}
}
voidsub2(char*nums)//2進制字符串減1
{
inti,n=strlen(nums),j=0;
for(i=n-1;i>=0;i--)
{
if(nums[i]=='1'&&i==n-1)
{
nums[i]='0';
break;
}
elif(nums[i]-'0'-j==0&&i!=n-1)
{
nums[i]='0';
break;
}
el
{
nums[i]='1';
j=1;
}
}
}
intcheckOverLoad(BAGc1,BAGc2,int*bws,intn)//檢查是否超載。超載返回1，否返回0
{
inti,sum1=0,sum2=0;
for(i=0;i<n;i++)
if(c1.books[i]=='1')
sum1=sum1+bws[i];
el
sum2=sum2+bws[i];
if(sum1>c1.bweight)
{
printf("背包1超載！\n");
return1;
}
if(sum2>c2.bweight)
{
printf("背包2超載！\n");
return1;
}
printf("方案可行！\n");
return0;
}

C語言 背包問題 遞歸算法

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

關(guān)于輸出選擇的物品，我加了一個數(shù)組，用來標(biāo)記選擇的物品。因為做完所有遞歸后只有最外層的標(biāo)記是有效的，所以最后用了一個for循環(huán)來完成各層的標(biāo)記。下面是改動后的程序：

　　

inta[5]={0};
　　intMaxW(intn,intC,int*Volunme,int*Weight)
　　{
　　intW=0,W1=0,W2=0;
　　if(n==0)
　　{
　　if(C>=Volunme[0])
　　{
　　a[0]=1;
　　returnW=1;
　　}
　　el
　　return0;
　　}
　　elif(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=(W1>W2?W1:W2);
　　a[n]=(W1>W2?1:0);
　　}
　　el//背包空間放不下n,返回判斷放n-1的情況
　　{
　　returnMaxW(n-1,C,Volunme,Weight);
　　}
　　returnW;
　　}
　　intmain(void)
　　{
　　intn=5;intC=7;
　　intVolunme[]={1,2,3,4,5};
　　intWeight[]={1,2,5,7,8};
　　printf("最大重量為%d\n",MaxW(n-1,C,Volunme,Weight));
　　
　　for(inti=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(inti=0;i<5;i++)
　　{
　　if(a[i]==1)
　　printf("#%d",i+1);
　　}
　　printf("\n");
　　return0;
　　}

C語言背包問題遞歸算法

你學(xué)過數(shù)據(jù)結(jié)構(gòu)了嗎？如果學(xué)過，那就比較好理解，該算法的思路和求二叉樹的高度的算法的思路是十分類似的。把取這i個物體看成i個階段，則該二叉樹有i+1層。其中空背包時為根結(jié)點，左孩子則為放棄了第1個物品后的背包，右孩子為選取了第1個物品后的背包。今后在對第i個物品進行選擇時，向左表示放棄，向右表示選取。則遞歸算法可如下：
int fun(int s, int i, int n) //s傳入的是背包容量, i是進行第i個物品的選取，n為剩余物品的件數(shù)
{
if(s == 0) return 有解；
el if(剩余的每件物品都裝不進|| n == 0) return 無解；
L = fun(s, i + 1, n - 1); //放棄第i個物品，則下一步的背包容量仍為s，然后看其是否有解，(遞歸調(diào)用進入左子樹)
R = fun(s - wi, i + 1, n - 1); //選取第i個物品，則下一步的背包容量為s-wi，然后看其是否有解，(遞歸調(diào)用進入右子樹)
return (l, r); //綜合考慮左右兩邊，看哪邊是正解或都無解。其實應(yīng)該返回 return (L||R);
}

c語言背包問題，求高手解答

對01背包求解，方法有回溯法、分支限界法、動態(tài)規(guī)劃法等。給你一個較容易理解的解法：窮舉搜索。問題求解的結(jié)果實際上是一個01序列，0表示該物品未裝入背包，1表示裝入背包。以本題為例，設(shè)求解結(jié)果為0111011，表示第0個和第4個未裝入，其他均裝入。關(guān)鍵就是如何找到這個01序列。設(shè)物品數(shù)量為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用于存放最優(yōu)解向量*/
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表示包中現(xiàn)有物品總價值，value2表示剩余物品總價值，n為物品總數(shù)量*/
{
int i;
if((step >= n) || (weight[step] > bag) || (value1 + value2 <= max)) /*如果所有物品都選擇完畢或剩余的物品都放不進或者包中物品總價值與剩余物品總價值之和小于等于目前的已知解，則找到一個解(但不一定是最終解或更優(yōu)解)*/
{
for(i = step; i < n; i++) v[i] = 0; /*剩余的物品都不放入*/
if(value1 > max) /*如果本次求得的解比以往的解更優(yōu)，則將本次解作為更優(yōu)解*/
{
max = value1;
for(i = 0; i < n; i++) Max[i] = v[i]; /*將更優(yōu)解保存到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( )
{
/*輸入數(shù)據(jù)：背包容量、物品數(shù)量、重量、價值 代碼略*/
int bag = 150, i, j, min, totalcost;
/*按物品重量從小到大的順序?qū)ξ锲放判颍判驎rcost向量中的相對順序也要作相應(yīng)移動*/
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為物品數(shù)量*/
/*以下輸出解*/
printf("最大價值為: %d。\n裝入背包的物品依次為：\n", max);
for(i = 0; i < N; i++)
if(Max[i]) printf("%c\t", name[i]);
printf("\n");
}

我的回答你滿意嗎？如果滿意，就請采納哦，或者你也可以繼續(xù)追問。

背包問題(C語言)

我copy一下別人的遞歸算法，假如你有時間限時的話，那我就用動態(tài)規(guī)劃幫你重新code一個

#include <stdio.h>
#define N 100 //物品總種數(shù)不是常量，沒法根據(jù)它來決定數(shù)組的長度，只有先定義個長度了
int n;//物品總種數(shù)
double limitW;//限制的總重量
double totV;//全部物品的總價值
double maxv;//解的總價值
int option[N];//解的選擇
int cop[N];//當(dāng)前解的選擇
struct {//物品結(jié)構(gòu)
double weight;
double value;
}a[N];
//參數(shù)為物品i,當(dāng)前選擇已經(jīng)達到的重量和tw,本方案可能達到的總價值
void find(int i,double tw,double tv)
{
int k;
//物品i包含在當(dāng)前方案的可能性
if(tw+a[i].weight <= limitW){
cop[i]=1;
if(i<n-1)find(i+1,tw+a[i].weight,tv);
el{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv;
}
}
cop[i]=0;
//物品i不包含在當(dāng)前方案的可能性
if(tv-a[i].value>maxv){
if(i<n-1)find(i+1,tw,tv-a[i].value);
el{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}
}
void main()
{
int k;
double w,v;
printf("輸入物品種數(shù):");
scanf("%d",&n);
printf("輸入各物品的重量和價值:");
for(totV=0.0,k=0;k<n;++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;k<n;++k)cop[k]=0;
find(0,0.0,totV);
for(k=0;k<n;++k)
if(option[k])printf("%4d",k+1);
printf("總價值為: %2f",maxv);
}