c語言背包問題

❶ 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語言，01背包問題

沒錯就是聲明

intA();
intmain()
{
	A();
	return0;
}
intA()
{
	
intB();
	B();
	return1;
}
intB()
{

	return0;
}//這樣試試就知道了

❹ C語言動態規劃之背包問題求解

#include<stdio.h>
int max(int a,int b)
{
if (a>b) return a;
else return b;
}
int main()
{
//int max(int , int );
int n,m,i,j;
int data[101][2];
int f[101][101];
scanf("%d%d",&n,&m); //n表示個數，m表示能背的最大重量
for(i=1;i<=n;i++)
{
scanf("%d%d",&data[i][0],&data[i][1]);
} //我是數組從第一個開始記得，看著容易理解，沒必要去省那麼幾B的內存
for(i=0;i<=m;i++) f[0][i]=0;
for(i=0;i<=n;i++) f[i][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
f[i][j]=0;
if (j>=data[i][0])
{
f[i][j]=max(f[i-1][j],f[i-1][j-data[i][0]]+data[i][1]);
//對於這件物品要麼不選要麼選，不選是f[i-1][j];
//選的話為f[i-1][j-data[i][0]]此處j-data[i][0]是因為要選上一次就得少背j-data[i][0]的重量
//才能裝下這次的物品
}
else f[i][j]=f[i-1][j];
}
printf("%d\n",f[n][m]);
return 0;
}
然後常見的背包問題還有多重背包問題，對於每一個物品可能有多個這種可以預處理成一般的背包問題，就是把幾個攤開，很簡單就不解釋了，當然也可以加一維.
還有就是完全背包問題他的狀態轉移方程是f[i,j]=max(f[i-1][j],f[i][j-data[i].v]);
他和01的區別只是要選的時候不是f[i-1][j-data[i].v]而是f[i][j-data[i].v]，這樣就能選到自己了，如果是初學可能不好理解，慢慢理會吧，其實這個很妙，我當初用了很多種方法，都是錯的，看了一時也沒明白，後來豁然開朗，然後對動規的理解都上了一個層次.
還有就是多為背包，這個只需要加一維，理解了前面的自然就能做出來了，根本不需要再看狀態轉移方程了（事實上理解後01就能夠做出來了）.
一句話：要多思考，反復思考
我很久沒碰演算法了，我沒現成的代碼這是我手打出來的，求分

❺ 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語言編程

原始題目： 有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語言的窮舉法的背包問題

根據題目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語言：背包問題(數據結構)

詳細程序代碼如下:
用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語言程序設計 背包問題

#include<stdio.h>
#define N 100
int n,limitW,totV,maxV;
int option[N],cop[N] = {0};
struct {
int weight;
int value;
}a[N];

void find(int i,int tw,int tv) {
int k;
if(tw + a[i].weight <= limitW) {
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;
}
}
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;
}
}
}

int main() {
int i,k,w,v;
printf("輸入物品總數 : ");
scanf("%d",&n);
for(i = 0; i < n;i++) {
printf("第%d/%d件物品的重量和價值 : ",i + 1,n);
scanf("%d %d",&a[i].weight,&a[i].value);
}
printf("輸入限制重量 ：");
scanf("%d",&limitW);
maxV = 0;
totV = 0;
find(0,0,totV);
for(k = 0;k < n;k++) if(option[k]) printf("%4d",k + 1);
printf("\n最大總值為%d\n",maxV);
return 0;
}

❿ C語言 貪心演算法求背包問題

是你的冒泡排序出了問題~

你吧 原來的1-2-3號按照東西的價值重新排列現在的1-2-3對應原來的2-1-3了
所以 你輸出的時候是按 1-2-3輸出的話 就等於第一個是原來的X2 第二個是X1第三個是X3
而且你的冒泡排序用錯了 只比較了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去學校幫你重新改改 我家的機器沒有C++
周一晚上我會上傳答案~我最近正好也要做演算法的作業~
#include <stdio.h>
#include <math.h>
#define N 50

float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放單位價值量大的物體，再考慮小的物體*/
{
int i;
float maxprice;
for (i = 0; i < n; i++)
x[i] = 0;
i = 0;
maxprice=0;
while (i < n && w[i] < M)
{
M=M-w[i];
x[i] =w[i]; /* 表示放入數量 */
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if (i < n &&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}

int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(