c语言背包问题(C语言背包问题)

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("请输入两个背包的最大载重：\n");
scanf("%d%d",&c1.bweight,&c2.bweight);
printf("请输入书本的数量：\n");
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("请输入每本书的重量：\n");
for(i=0;i<n;i++)
{
scanf("%d",&bws[i]);
sum+=bws[i];
}
if(sum<=c1.bweight+c2.bweight)
break;
el
printf("书本重量和超过背包负重和！请重新输入\n\n");
}


qj(c1,c2,4,bws,0);
//------------------------------打印结果-----------------------------
printf("\n输出：\n");
printf("book");
for(i=0;i<n;i++)
printf("%d",bws[i]);
printf("\n");
printf("c1%s\n",c1.books);
printf("c2%s\n",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("---------开始穷举所有可能的组合----------\n");
memt(c1.books,'0',n);
memt(c2.books,'1',n);
c1.books[n]=c2.books[n]=0;
printf("%s\n",c1.books);
printf("%s\n",c2.books);
if(checkOverLoad(c1,c2,bws,n)==0)
{
memt(nums1,0,n+1);
memt(nums2,0,n+1);
strcpy(nums1,c1.books);
strcpy(nums2,c2.books);
if(flag==1)
return0;
}
printf("\n");
for(i=0;i<max;i++)
{
add2(c1.books);
sub2(c2.books);
printf("%s\n",c1.books);
printf("%s\n",c2.books);
if(checkOverLoad(c1,c2,bws,n)==0)
{
memt(nums1,0,n+1);
memt(nums2,0,n+1);
strcpy(nums1,c1.books);
strcpy(nums2,c2.books);
if(flag==1)
return0;
}
printf("\n");
}
printf("-----------------穷举结束------------------\n");
memt(c1.books,0,n+1);
memt(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;
}
elif(nums[i]-'0'+jin==1&&i<n-1)
{
nums[i]='1';
break;
}
el
{
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;
}
elif(nums[i]-'0'-j==0&&i!=n-1)
{
nums[i]='0';
break;
}
el
{
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];
el
sum2=sum2+bws[i];
if(sum1>c1.bweight)
{
printf("背包1超载！\n");
return1;
}
if(sum2>c2.bweight)
{
printf("背包2超载！\n");
return1;
}
printf("方案可行！\n");
return0;
}

C语言 背包问题 递归算法

　　提问者的这程序中用了递归算法，不过逻辑上有个小bug，就是在判断到n==0时，如果还有容量，那么返回的应该是第一个物品的重量而不是0。你可以改变容量C或物品参数来检验算法的逻辑正确性。

关于输出选择的物品，我加了一个数组，用来标记选择的物品。因为做完所有递归后只有最外层的标记是有效的，所以最后用了一个for循环来完成各层的标记。下面是改动后的程序：

　　

inta[5]={0};
　　intMaxW(intn,intC,int*Volunme,int*Weight)
　　{
　　intW=0,W1=0,W2=0;
　　if(n==0)
　　{
　　if(C>=Volunme[0])
　　{
　　a[0]=1;
　　returnW=1;
　　}
　　el
　　return0;
　　}
　　elif(C>=Volunme[n])//背包剩余空间可以放下物品n
　　{
　　W1=MaxW(n-1,C-Volunme[n],Volunme,Weight)+Weight[n];//放入n所能得到的重量
　　W2=MaxW(n-1,C,Volunme,Weight);//不放n所能得到的重量
　　W=(W1>W2?W1:W2);
　　a[n]=(W1>W2?1:0);
　　}
　　el//背包空间放不下n,返回判断放n-1的情况
　　{
　　returnMaxW(n-1,C,Volunme,Weight);
　　}
　　returnW;
　　}
　　intmain(void)
　　{
　　intn=5;intC=7;
　　intVolunme[]={1,2,3,4,5};
　　intWeight[]={1,2,5,7,8};
　　printf("最大重量为%d\n",MaxW(n-1,C,Volunme,Weight));
　　
　　for(inti=n-2;i>=0;i--)
　　{
　　a[i]=0;
　　if(a[i+1]==1)
　　{
　　C-=Volunme[i+1];
　　Weight[i+1]=0;
　　}
　　MaxW(i,C,Volunme,Weight);
　　}
　　printf("选择的物品号是：");
　　for(inti=0;i<5;i++)
　　{
　　if(a[i]==1)
　　printf("#%d",i+1);
　　}
　　printf("\n");
　　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 有解；
el 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语言背包问题，求高手解答

对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语言)

我copy一下别人的递归算法，假如你有时间限时的话，那我就用动态规划帮你重新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);
el{
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);
el{
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);
}