『壹』 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語言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語言背包問題，求高手解答
對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語言簡短代碼，大神們最好帶解釋和注釋，謝謝！！！
不知道你說的哪種類型的背包，我就說下最簡單的吧。
一、01背包
問題描述：有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
（1）基本思路：這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
意思簡要來說就是：如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」，價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
（2）優化空間復雜度：以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果只用一個數組f[0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態f[i-1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當於我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為現在的f[v-c[i]]就相當於原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符。
（3）初始化的細節問題：我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求「恰好裝滿背包」時的最優解，有的題目則並沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。
如果並沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。
為什麼呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那麼此時只有容量為0的背包可能被價值為0的nothing「恰好裝滿」，其它容量的背包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果背包並非必須被裝滿，那麼任何容量的背包都有一個合法解「什麼都不裝」，這個解的價值為0，所以初始時狀態的值也就全部為0了。
【寫的偽代碼，能看懂哈。。。不懂再問好了】