當前位置:首頁 » 編程語言 » c語言背包問題
擴展閱讀
webinf下怎麼引入js 2023-08-31 21:54:13
堡壘機怎麼打開web 2023-08-31 21:54:11

c語言背包問題

發布時間: 2022-01-22 15:05:05

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語言背包問題遞歸演算法

你學過數據結構了嗎?如果學過,那就比較好理解,該演算法的思路和求二叉樹的高度的演算法的思路是十分類似的。把取這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語言動態規劃之背包問題求解

#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語言的窮舉法的背包問題

根據題目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語言實現背包問題,高手進來補填

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
long int m,n,w,p,i,j;
long int x[1001];
cin>>w>>p;
for(i=0;i<=1001;i++)
x[i]=0;
for(i=1;i<=n;i++)
{
cin>>a>>b;
if(m-a>0)
for(j=m-a;j>=0;j--)
if(x[j]+b>x[j+a]) x[j+a]=x[j]+b;
}
cout<<x[m]<<endl;
return 0;
}

❻ 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語言)

我一下別人的遞歸演算法,假如你有時間限時的話,那我就用動態規劃幫你重新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語言演算法求助:背包問題

//如果每種商品只有一件,是0-1背包問題
讀入的數據N代表物品個數
V代表背包容量。
//對於你的例子
,輸入為
//5
16
//2
3
//3
2
//4
3
//5
7
//6
9
//輸出為21
#include
<iostream>
using
namespace
std;
#define
MAXSIZE
1000
int
f[MAXSIZE
+
1],
c[MAXSIZE
+
1],
w[MAXSIZE
+
1];
int
main()
{
int
N,
V;
cin
>>
N
>>
V;
int
i
=
1;
for
(;
i
<=
N;
++i)
{
cin
>>
c[i]
>>
w[i];
}
for
(i
=
1;
i
<=
N;
++i)
{
for
(int
v
=
V;
v
>=
c[i];
--v)
//c[i]可優化為bound,
bound
=
max
{V
-
sum
c[i,...n],
c[i]}
{
f[v]
=
(f[v]
>
f[v
-
c[i]]
+
w[i]
?
f[v]
:
f[v
-
c[i]]
+
w[i]);
}
}
//當i=N時,可以跳出循環單獨計算F[V]
cout
<<
f[V]
<<
'\n';
system("pause");
return
0;
}
//如果每種可以有多個,是完全背包問題,