背包問題c語言
『壹』 背包問題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了。
【寫的偽代碼，能看懂哈。。。不懂再問好了】陸亮
『貳』 C語言 背包問題 遞歸演算法
if(n==0)應該改成
if(n<0)才對，表示沒有物品可選了。我的一個改進，但輸出選擇項還是有問題！
#include<stdio.h>
#include<conio.h>
#defineN3
intMaxW(intn,intC,int*Volume,int*Weight,int*Select){
intW=0,W1=0;
if(n<0){//沒有物品了
return0;
}
W=MaxW(n-1,C,Volume,Weight,Select);//沒放入n之前的重量
if(C>=Volume[n]){//背包剩餘空間可以放下物品n
W1=MaxW(n-1,C-Volume[n],Volume,Weight,Select)+Weight[n];//放入n所能得到的重量
Select[n]=0;
if(W1>W){//放入n能獲得更大的重量
Select[n]=1;
W=W1;
}
}
returnW;
}
intmain(){
intC=8,W,i;
//intVolume[N]={1,2,3,4,5};//物品體積
//intWeight[N]={1,2,5,7,8};//物品重量
intVolume[N]={2,3,5};//物品體積
intWeight[N]={5,8,7};//物品重量
intSelect[N]={0};//選擇標記
W=MaxW(N-1,C,Volume,Weight,Select);
printf("MaxWeight=%d,SelectList[index(volume,weight)]: ",W);
for(i=0;i<N;++i){
if(Select[i]){
printf("%d(%d,%d)",i,Volume[i],Weight[i]);
}
}
printf(" Finished! ");
getch();
return0;
}
其中的Select數組還是會多選了，你看看。
『叄』 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語言疑問
#include <stdio.h>
#define N 100 //物品總種數不是常晌畢量，沒法根據它來決定數組的長度，只有先定義個長度了
int n;//物品總種橋謹禪數
double limitW;//限制的總重量
double totV;//全部物品的總價值
double maxv;//解的總價值
double maxw=0.0;//解的總重量-------------->新加
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])
{//-------------->新加
maxw+=a[k].weight//-------------->新加
printf("%4d",k+1);
}//-------------->新加
printf("總價值為: %2f",maxv);
printf("總重量為: %2f",maxw); //-------------->新加
}
『伍』 c語言01背包問題誰能簡單說下
01背包問題就是有個容量為W的包，然後有一堆的物品(1...n)，其中wi、vi分別為第i個物品的重量和價值，現在需要求的就是使得包中所裝的物品盡可能的價值高。那麼這個物品放不放在包中對應取值0
or
1。其演算法為動態規劃，需要證明最優子結構性質。用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
所以不論用什麼語言實現，就是計算上面的式子，最終求得s[n][W]，上面的式子很好用遞推實現的，這個是自底向上的，就是兩層for；你也可以用棧實現自頂向下的，這個是記錄式的方法。
以上的W是只考慮整數的。
『陸』 c語言的窮舉法的背包問題
根據題目c1，c2是一組01組合的數組，也就是2個n位2進制數。
所以我的代碼邏輯就是，c1，c2初值分別是00000....以及111111....，之後循環執行c1+1；c2-1（2進制加減運算），最大執行次數2的n次方-1（n位2進制數最大數）
代碼實現功能，窮舉所有可能方案，返回:第一個/最後一個找到的可行方案。
函數intqj(BAGc1,BAGc2,intn,int*bws,intflag);
當flag=1返回第一個可行方案，flag=0查找所有方案並返回最後一個可行方案
我測試時，flag傳值0，需要自己改！！
由於迭代順序，同樣實驗數據，返回的結構和你案例結構不一樣，我在下圖標注了。
#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進制組合，返回最後一個可行方案（可能有多個方案）。
//參數：c1背包1，c2背包2，n書本個數，bws所有書本重量，標識：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("請輸入兩個背包的最大載重：
");
scanf("%d%d",&c1.bweight,&c2.bweight);
printf("請輸入書本的數量：
");
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("請輸入每本書的重量：
");
for(i=0;i<n;i++)
{
scanf("%d",&bws[i]);
sum+=bws[i];
}
if(sum<=c1.bweight+c2.bweight)
break;
else
printf("書本重量和超過背包負重和！請重新輸入
");
}
qj(c1,c2,4,bws,0);
//------------------------------列印結果-----------------------------
printf("
輸出：
");
printf("book");
for(i=0;i<n;i++)
printf("%d",bws[i]);
printf("
");
printf("c1%s
",c1.books);
printf("c2%s
",c2.books);
}
intqj(BAGc1,BAGc2,intn,int*bws,intflag)//窮舉所有n位二進制數,
{
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("---------開始窮舉所有可能的組合----------
");
memset(c1.books,'0',n);
memset(c2.books,'1',n);
c1.books[n]=c2.books[n]=0;
printf("%s
",c1.books);
printf("%s
",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)
return0;
}
printf("
");
for(i=0;i<max;i++)
{
add2(c1.books);
sub2(c2.books);
printf("%s
",c1.books);
printf("%s
",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)
return0;
}
printf("
");
}
printf("-----------------窮舉結束------------------
");
memset(c1.books,0,n+1);
memset(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;
}
elseif(nums[i]-'0'+jin==1&&i<n-1)
{
nums[i]='1';
break;
}
else
{
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;
}
elseif(nums[i]-'0'-j==0&&i!=n-1)
{
nums[i]='0';
break;
}
else
{
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];
else
sum2=sum2+bws[i];
if(sum1>c1.bweight)
{
printf("背包1超載！
");
return1;
}
if(sum2>c2.bweight)
{
printf("背包2超載！
");
return1;
}
printf("方案可行！
");
return0;
}
『柒』 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語言)
我一下別人的遞歸演算法，假如你有時間限時的話，那我就用動態規劃幫你重新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語言背包問題
演算法分析：
使用貪心策略求解此類問題時，首先要選出最優的度量標准。
可供選擇的度量標准有三種：價值，容量，單位價值（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);
}
}