c語言背包
① c語言：背包問題(數據結構)
詳細程序代碼如下:
用VC6.0編譯.保存代碼時,以.C為後綴名
下面是一組測試數據:
請輸入背包能容納的最大重量：20
請輸入物品個數：10
請輸入每一個物品的重量和價值：1,11,2,22, 3,33.....10,100
結果是正確的.
#include<stdio.h>
#include<conio.h>
#include<malloc.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;i<n;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((maxweight>0)&&(i<=n))/*當還可以裝下物品，且物品沒有用完時*/
{
if((maxweight-weight[i]==0)||(maxweight-weight[i]>0)&&(i<n))/*正好裝完物品或還能容納物品且物品沒有用完時*/
{
stack[++top]=i;/*把對應物品的處標保存到棧中*/
p=MallocNode();/*每一次得到一個結果後，就將該結果保存到鏈表中*/
for(tempTop=top,j=0;tempTop>0;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)&&(top>0))/*繼續測試*/
{
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;i<NUMBER;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;i<NUMBER;i++)
{
if(headLink->next->goods[i]==-1)
break;
result.goods[i]=headLink->next->goods[i];
}
p=headLink->next->next;
while(p)/*查找最佳結果*/
{
if(p->totalWeight>result.totalWeight)/*如果發現p點價值比當前結果還大，則將p又作為最佳結果*/
{
result.totalWeight=p->totalWeight;
for(i=0;i<NUMBER;i++)
result.goods[i]=-1;
for(i=0;i<NUMBER;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;i<NUMBER;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語言編程
原始題目： 有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是
w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容
量，且價值總和最大。（取自網路）
問題簡化： 1. 背包可容納總重量為M
2. 有n個物品，每個重量為m[0]. m[1]. m[2] ......m[i] 對應每個物品的
價值為s[0]. S[1]. S[2]....s[i] (i<=n)
3. 放入第i個物品,比較m[i]和M的大小,不超過M則記錄下當前價值s
4. 最終取得最大值s
實現方法：
定義三個浮點型一維數組float m[[n]和s[n]和y[n] 定義float M,float a,b定義int n,j, int i
請輸入背包容量大小M：
please input the number of the things：
please input the value of the things：
把輸入數據按順序分別定義到數組中（若可以的話，把m[n]的數據由小到大排序，判斷最小值m[0]和M的大小，若m[0]>M，輸出error）
創建一個棧（這里的東西不太懂—-—）
將第一個數據壓入棧底,定義i=0，把當前的m[i]賦值給a，s[i]賦值給b,把當前i存放進數組y[n]，以後在每次比較過程中，都把較大b值所對應的物品數存放進y[n]中
判斷a<M（這里，若在4已經做過，則可省略，第一個數據一定小於M）
判斷a+m[++i]<=M，為真，把第i（注意，此時i已經自增了，這個i是數組中的下標）個數據壓入棧，賦值a=a+m[++i]，比較b和b+s[++i]的大小，賦值b=b+s[++i]（理論上，物品價值總該是為正的吧，若是這樣的話，不用比較大小了，直接賦新值，直到跳出第一輪循環為止；另外有一種設想，若價值全為正，可以轉而把問題這樣簡化：即給定容量大小和全為正的價值物品，現在想辦法讓背包放入物品的數量最多 就行了）；若為假，轉10
如此進行一輪循環，直到出現10，此時b為一輪循環的最大值，return b,y[n]
當a+m[++i]>M，從棧中彈出m[i-2]，a=a-m[i-2],,當i原本就小於等於2的時候，則清除棧中數據，轉12，判斷a+m[i]<=M，為真，比較b和b-s[i-2]+s[i]，並把較大值賦給b，繼續向下比較，這時候就不用壓入棧中了,再定義一個j=1
判斷a+m[i+j]<=M,為真，比較b和b-s[i-2]+s[i+j]大小，較大值賦給b，為假，從棧中彈出m[i-3]，當i原本就小於等於3的時候，則清除棧中數據，轉12，判斷a+m[i]<=M，為真，比較b和b-s[i-3]+s[i]（注意，這個b一直在被賦予最新值），如此進行第一輪循環，用for語句實現，因為下面還有嵌入
此時棧中沒有數據，並且，已經把m[0]為棧底的循環計算完畢，現在開始計算m[1]為棧底的循環，在這一循環，忽略掉m[0]，所有可能情況已經在8-11計算過
依此往下，直到棧底被壓入的是m[n]為止，計算完畢，輸出b，並且輸出數組y[n]
碰巧幫同學，也是這個問題，希望能幫助你。
③ C語言背包問題
《背包九講》挺好的：http://wenku..com/link?url=QeRosxybnrqnCFvV-_
你這個屬於多重背包問題。
可以把所有同類書都分開考慮成單獨的書，就成了01背包
如果想要更快速看《背包九講吧》
④ c語言背包問題
演算法分析：
使用貪心策略求解此類問題時，首先要選出最優的度量標准。
可供選擇的度量標准有三種：價值，容量，單位價值（v/w，價值/重量）。
顯然，價值高的物品容量可能太大，容量大的物品價值也可能很低。最優的度量標準是單位價值。
背包問題演算法思路：
1、將各個物品按照單位價值由高到低排序；
2、取價值最高者放入背包；
3、計算背包的剩餘空間；
4、重復2-3步，直到背包剩餘容量=0或者物品全部裝入背包為止（對於0-1背包，終止條件為背包剩餘容量無法裝入任意一件物品或者物品全部裝入背包）。
#include<stdio.h>
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已經按照單位價值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這里已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩餘容量%f.\n",(i+1),c);
}
if(i<=n)//還可以放入一個物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩餘容量為0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這里已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩餘容量%f.\n",(i+1),c);
}
}
#include<stdio.h>
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已經按照單位價值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這里已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩餘容量%f.\n",(i+1),c);
}
if(i<=n)//還可以放入一個物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩餘容量為0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包問題
* n:物品個數
* c：背包容量
* v[]:每個物品的價值
* w[]:每個物品的重量（這里已經按照單位價值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始狀態，所有物品都沒有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩餘容量%f.\n",(i+1),c);
}
}
⑤ 完全背包問題，c語言編程
#include<stdio.h>
float V[1000],V1[1000];
int max(float a[],int n)
{
int s = 1;
float fmax = a[1];
for (int j=2;j<n;j++)
{
(a[j]>fmax)
{
fmax = a[j];
a[j] = 0;
s = j;
}
}
return s;
}
int KnapSack(int n,int w[],int v[],int C)
{
int Maxvalue = 0;
int X[1000],w0[1000],w1[1000];
memset(X,0,sizeof(X));
memset(w0,0,sizeof(w0));
memset(w1,0,sizeof(w0));
for (int j=1;j<n;j++)
{
V[i] = 1.0*v[i]/w[i];
V1[i] =V[i];
}
X[1] = max(V1,n);
int w0[1] = n/w[X];
int w1[1] = n%w[X];
int k = 1;
while (w1[k++]!=0)
{
X[K] = max(V1,n);
w0[k] = w1[k]/w[Y];
w1[k] = w1[k]%w[Y];
}
for (int m=1;m<k;m++)
{
Maxvalue+=w0[m]*w[X[K]]*v[X[k];
}
return Maxvalue;
}
int main(void)
{
int s;
int w[1000];
int v[1000];
int n,i;
int C;
scanf("%d %d", &C, &n);
for(i=0;i<n;i++)
scanf("%d %d",&w[i], &v[i]);
s=KnapSack(n,w,v,C);
printf("%d",s);
return 0;
}
⑥ 求大神給一份C語言01背包的代碼，要每一行都有注釋，謝謝！
這是一個背包問題，該演算法已經是最簡單的了，還有遞歸演算法，我覺得更麻煩。對你的代碼進行解釋如下：
//背包問題：有m件物品和一個承重為t的背包。第i件物品的重量是w[i]，價值是v[i]。
//求解將哪些物品裝入背包可使這些物品的重量總和不超過背包承重量t，且價值總和最大。
#include<stdio.h>
#include<conio.h>
#include<string.h>
intf[1010],w[1010],v[1010];//f記錄不同承重量背包的總價值，w記錄不同物品的重量，v記錄不同物品的價值
intmax(intx,inty){//返回x,y的最大值
if(x>y)returnx;
returny;
}
intmain(){
intt,m,i,j;
memset(f,0,sizeof(f));//總價值初始化為0
scanf("%d%d",&t,&m);//輸入背包承重量t、物品的數目m
for(i=1;i<=m;i++)
scanf("%d%d",&w[i],&v[i]);//輸入m組物品的重量w[i]和價值v[i]
for(i=1;i<=m;i++){//嘗試放置每一個物品
for(j=t;j>=w[i];j--){
f[j]=max(f[j-w[i]]+v[i],f[j]);
//在放入第i個物品前後，檢驗不同j承重量背包的總價值，如果放入第i個物品後比放入前的價值提高了，則修改j承重量背包的價值，否則不變
}
}
printf("%d",f[t]);//輸出承重量為t的背包的總價值
printf(" ");
getch();
return0;
}
⑦ C語言 背包問題
這個答案是我在網上找到的，你自己看看吧
0/1背包經典問題：
需對容量為M的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對於可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即n ?i=1pi xi 取得最大值。約束條件為n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。
我的程序：思想——動態規劃法，先考慮沒有物品要放的時候S0，再考慮只有一個要放物品a的各種情況S1，再綜合考慮只有第一個a和第二個b物品要放時的情況S2，再綜合考慮有三個待放物品abc的情況……
#include<stdio.h>
#include<iostream.h>
#define MAX 200
void main(void)
{
cout<<"******************************************************"<<endl
<<"******************* 0/1背包問題 ***************"<<endl
<<"******************* CopyRight: ***************"<<endl
<<"******************* Grace Air ***************"<<endl
<<"******************************************************"<<endl;
int n,M;
int num,t,q;
int temp;
int s[100];
int x[100];//決策集
int ww,pp,i,j,k,r,next;
int u;//記錄附加結點
int P[100000],W[100000];//存放所有的可行序偶
P[0]=W[0]=0;//S0中的點(0，0)
int F[100];//記錄si點的起點在P[]W[]數組中的位置
F[0]=0;F[1]=next=1;
int begin,end;begin=end=0;
int wi[100],pi[100],w[100],p[100];
cout<<"請輸入下列背包初始信息:"<<endl;
cout<<endl<<"背包最大容量為：";
cin>>M;
cout<<endl<<"請輸入下列物品初始信息:"<<endl;
cout<<endl<<"物品種類有幾種？：";
cin>>n;
for(num=0;num<n;num++)
{
cout<<endl<<"第"<<num+1<<"種物品重量：";
cin>>wi[num];
cout<<" 價值：";
cin>>pi[num];
}
for(num=0;num<n;num++)
{
temp=wi[0];
q=0;
for(t=0;t<n;t++)
{
if(temp>wi[t])
{
temp=wi[t];
q=t;
}
}
s[q]=num+1;
w[num]=wi[q];
p[num]=pi[q];
wi[q]=MAX;
}
for(i=0;i<n;i++)
{
F[i+1]=end+1;
u=begin;//從頭開始考慮序偶點
for(r=begin;r<end+1;r++)//生成sii圖，s1中只考察結點0,
{
if(W[r]+w[i]<=M)
u=(W[r]+w[i])>(W[u]+w[i])?r:u;//s1的u=0,u是sii中能讓i結點加上它把空間塞得最滿的那個結點，即
//造成s12中x軸最向右靠近確定的M值的點的附加點
}//u號以前的點都是可以考慮加入的點
k=begin;//k是記錄si-1圖中已加入到si圖中的點
for(j=begin;j<u+1;j++)//生成si圖
{
ww=W[j]+w[i];
pp=P[j]+p[i];
while(k<=end&&W[k]<ww)//將si-1的點都加到si中
{
P[next]=P[k];
W[next]=W[k];
next++;k++;
}
if(k<=end&&W[k]==ww)
{
pp=pp>P[k]?pp:P[k];
k++;
}
if(pp>P[next-1])//sii中的點如果效益比以前的大，加進si
{
P[next]=pp;
W[next]=ww;
next++;
}
while(k<=end&&P[k]<=P[next-1])
k++;
}
begin=end+1;
end=next-1;
}
//回溯
int PX,WX,PY,WY;
PX=P[end];WX=W[end];
for(i=n;i>0;i--)
{
PY=P[F[i]-1];WY=W[F[i]-1];
if(PX>PY)
{
x[i]=1;
PX=PX-p[i-1];WX=PY-w[i-1];
}
else x[i]=0;
}
cout<<endl<<"最優決策為：";
for(i=0;i<n;i++)
cout<<x[s[i]]<<" ";
cout<<endl<<"最優效益為:"<<P[end]<<endl<<"重量："<<W[end]<<endl;
}
⑧ 背包問題(C語言)
我一下別人的遞歸演算法，假如你有時間限時的話，那我就用動態規劃幫你重新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(i<n-1)find(i+1,tw+a[i].weight,tv);
else{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv;
}
}
cop[i]=0;
//物品i不包含在當前方案的可能性
if(tv-a[i].value>maxv){
if(i<n-1)find(i+1,tw,tv-a[i].value);
else{
for(k=0;k<n;++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;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);
}
⑨ 用C語言實現背包問題求解。
#include<stdio.h>
#define OK 1
#define ERROR 0
#define SElemtype int
#define STACKSIZE 100
typedef struct{
SElemtype data[STACKSIZE];
int top;
} SqStack;SElemtype Initstack(SqStack &s)//初始化棧。
{
s.top=0;
return OK;
}SElemtype Push(SqStack &s,SElemtype e)//入棧。
{
s.data[s.top++]=e;
return OK;
} void main()
{
int i,n,totalvol,w[STACKSIZE],sum=0,j=0;
SqStack s;
Initstack(s);
printf("請輸入背包能裝入的總體積：");
scanf("%d",&totalvol);
printf("請輸入物品件數：");
scanf("%d",&n);
printf("請輸入每件物品的體積：");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
while(s.top!=-1)
{ if(sum+w[j]<=totalvol)
{
Push(s,j);
sum+=w[j];
} if(sum==totalvol) //找到一組，退棧頂，找下一組。
{
for(i=0;i<s.top;i++)
printf("%d ",w[s.data[i]]);
printf("\n"); s.top--;
sum-=w[s.data[s.top]];
j=s.data[s.top]+1;
} else
j++;
while(j==n) //遍歷後仍未找到，則退棧。
{
s.top--;
sum-=w[s.data[s.top]];
j=s.data[s.top]+1;
}
}}
⑩ 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");
}
我的回答你滿意嗎？如果滿意，就請點贊哦，或者你也可以繼續追問。