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;
}