c語言背包問題回溯

㈠ 分別用回溯法和動態規劃求0/1背包問題（c語言代碼）

#include <stdio.h>
#include <malloc.h>
#include <windows.h>typedef struct goods
{
double *value; //價值
double *weight; //重量
char *select; //是否選中到方案
int num;//物品數量
double limitw; //限制重量
}GOODS;
double maxvalue,totalvalue;//方案最大價值,物品總價值
char *select1; //臨時數組
void backpack(GOODS *g, int i, double tw, double tv)//參數為物品i,當前選擇已經達到的重量和tw,本方案可能達到的總價值
{
int k;
if (tw + g->weight[i] <= g->limitw)//將物品i包含在當前方案,且重量小於等於限制重量
{
select1[i] = 1; //選中第i個物品
if (i < g->num - 1) //若物品i不是最後一個物品
backpack(g, i + 1, tw + g->weight[i], tv); //遞歸調用,繼續添加下一物品
else //若已到最後一個物品
{
for (k = 0; k < g->num; ++k) //將狀態標志復制到option數組中
g->select[k] = select1[k];
maxvalue = tv; //保存當前方案的最大價值
}
}
select1[i] = 0; //取消物品i的選擇狀態
if (tv - g->value[i] > maxvalue)//若物品總價值減去物品i的價值還大於maxv方案中已有的價值,說明還可以繼續向方案中添加物品
{
if (i < g->num - 1) //若物品i不是最後一個物品
backpack(g, i + 1, tw, tv - g->value[i]); //遞歸調用,繼續加入下一物品
else //若已到最後一個物品
{
for (k = 0; k < g->num; ++k) //將狀態標志復制到option數組中
g->select[k] = select1[k];
maxvalue = tv - g->value[i]; //保存當前方案的最大價值(從物品總價值中減去物品i的價值)
}
}
}
int main()
{
double sumweight;
GOODS g;
int i;
printf("背包最大重量:");
scanf("%lf",&g.limitw);
printf("可選物品數量:");
scanf("%d",&g.num);
if(!(g.value = (double *)malloc(sizeof(double)*g.num)))//分配內存保存物品價值
{
printf("內存分配失敗\n");
exit(0);
}
if(!(g.weight = (double *)malloc(sizeof(double)*g.num)))//分配內存保存物品的重量
{
printf("內存分配失敗\n");
exit(0);
}
if(!(g.select = (char *)malloc(sizeof(char)*g.num)))//分配內存保存物品的重量
{
printf("內存分配失敗\n");
exit(0);
}
if(!(select1 = (char *)malloc(sizeof(char)*g.num)))//分配內存保存物品的重量
{
printf("內存分配失敗\n");
exit(0);
}
totalvalue=0;
for (i = 0; i < g.num; i++)
{
printf("輸入第%d號物品的重量和價值:",i + 1);
scanf("%lf%lf",&g.weight[i],&g.value[i]);
totalvalue+=g.value[i];//統計所有物品的價值總和
}
printf("\n背包最大能裝的重量為:%.2f\n\n",g.limitw);
for (i = 0; i < g.num; i++)
printf("第%d號物品重:%.2f,價值:%.2f\n", i + 1, g.weight[i], g.value[i]);
for (i = 0; i < g.num; i++)//初始設各物品都沒加入選擇集
select1[i]=0;
maxvalue=0;//加入方案物品的總價值
backpack(&g,0,0.0,totalvalue); //第0號物品加入方案,總重量為0,所有物品價值為totalvalue
sumweight=0;
printf("\n可將以下物品裝入背包,使背包裝的物品價值最大:\n");
for (i = 0; i < g.num; ++i)
if (g.select[i])
{
printf("第%d號物品,重量:%.2f,價值:%.2f\n", i + 1, g.weight[i], g.value[i]);
sumweight+=g.weight[i];
}
printf("\n總重量為: %.2f,總價值為:%.2f\n", sumweight, maxvalue );
// getch();
return 0;
}

㈡ 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語言程序或者思路啊！！！！！

#include<stdio.h>
#define N 100
int str[N];
int w[N];
int k=0;
void
backtrack(int i,int n,int m)
{

if(m==0){
k++;
for(int i=1;i<=n;i++)
if(str[i]!=i)
printf("%d ",i);
printf("\n");
}
if(i<=n&&m>0){
for(int j=0;j*w[i]<=m;j++){
if(j!=0)str[i]=0;
backtrack(i+1,n,m-j*w[i]);
str[i]=i;
}
}
}
int
main()
{
int m,n;
printf("請輸入背包的容積:\n");
scanf("%d",&m);
printf("請輸入物品的種類數:\n");
scanf("%d",&n);
for(int i=1;i<=n;i++)
str[i]=i;
for(i=1;i<=n;i++){
printf("請輸入第%d種物品的體積:\n",i);
scanf("%d",&w[i]);
}
printf("背包中存放的物品的幾種情況分別為為:\n");//注意輸出結果有的相同，但他們的數目不同
backtrack(1,n,m);
printf("總方案數為:%d\n",k);
return 0;
}

㈣ 背包問題(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語言或C++版)或演算法

背包問題小結- []2006-07-28

做到背包問題覺得很有意思，寫寫看看。
完全背包問題可以用貪心演算法。
代碼如下：

program bag1;
const maxn=10;
var
goods:array[1..maxn,1..3] of integer;
s:array[1..maxn] of real;
i,j:integer;
m,n:integer;
y:integer;
x:real;
function max:integer;
var m:real;
i,j:integer;
begin
m:=0;
for i:=1 to n do
if (goods[i,3]=0) and (m max:=j;
end;

procere choose;
var i,j:integer;

begin
while y begin
if y begin
i:=max;
if m>=y+goods[i,1] then begin goods[i,3]:=1;x:=x+goods[i,2];y:=y+goods[i,1];end else
begin
x:=x+(m-y)*s[i];
y:=m;
end;
end;
end;
end;

begin
fillchar(goods,sizeof(goods),0);
assign(input,'b.txt');
reset(input);
readln(m,n);
for j:=1 to n do
read(goods[j,1]);
readln;
for j:=1 to n do
read(goods[j,2]);
for j:=1 to n do
s[j]:=goods[j,2]/goods[j,1];

close(input);
choose;
writeln(x:5:2);
end.
編得不是很好 ^-^ 獻丑了。

我來說說0/1背包問題。
狀態：當前物品n
算符：j=0（當前物品不放入背包） 或 j=1（當前物品放入背包）
這就很好說了，還是把yes函數一改，問題OK了。
代碼如下：

program bag2;
const maxn=10;
var i:integer;
goods:array[1..maxn,1..3] of integer;{原始數據}
s:array[1..maxn] of integer;{當前的狀態}
r:array[1..maxn] of integer;{當前的總質量}
m:integer;{背包容量}
max:integer;{物品個數}
procere try(n:integer);
var j:integer;

{function yes:boolean;
var k:integer;
t:integer;
mn:integer;
begin
mn:=0;
t:=goods[n,3];
goods[n,3]:=j;
for k:=1 to n do
if goods[k,3]=1 then inc(mn,goods[k,1]);
goods[n,3]:=t;
if mn>m then yes:=false else yes:=true;
end;}

begin
if n=max+1 then begin if x for i:=1 to max do s[i]:=goods[i,3]; {保存最優解}end
end else
begin
if r[n-1]>m then exit;{已超過背包總容量}
for j:=1 downto 0 do
begin
if j=1 then r[n]:=r[n-1]+goods[n,1];
if j=0 then r[n]:=r[n]-goods[n,1];
if {yes}r[n]<=m then begin goods[n,3]:=j;try(n+1);goods[n,3]:=0;end
end;
end;
end;

begin
assign(input,'b.txt');
reset(input);
readln(m,max);
for i:=1 to max do
read(goods[i,1]);
readln;
for i:=1 to max do
read(goods[i,2]);
close(input);
try(1);
for i:=1 to 7 do
write(s[i]:3);
writeln;
writeln(x);
end.

用yes 函數要從頭到當前求已裝入背包物品的總質量，時間效率不高。所以我們引入r[n]數組來記錄當前背包總質量（很好用！）注意用r[n-1]>m來做剪枝，以再次提高時間效率。

DC跟我說可以用二進制解此類問題。我覺得很有創意，也說說。比如8個物品，每個物品有0/1兩種狀態所以我們從(00000000)(二進制 )到（11111111）（二進制）循環即可。然後在分離十進制數對應起來即可。但在實際的操作中發現效率比回溯還低，我想有兩方面的原因：1、顯而易見，不可能做剪枝。2、每一次結果都要從1到8求和十效率降低。不過這確實是一種很新穎的演算法。

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

根據題目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;
}