本文目录一览：
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语言的穷举法的背包问题
根据题目c1，c2是一组01组合的数组，也就是2个n位2进制数。
所以我的代码逻辑就是，c1，c2初值分别是 00000....以及111111....，之后循环执行c1+1；c2-1（2进制加减运算），最大执行次数 2的n次方-1（n位2进制数最大数）
代码实现功能，穷举所有可能方案，返回:第一个 /最后一个找到的可行方案。
函数int qj(BAG c1,BAG c2,int n,int *bws,int flag);
当flag=1 返回第一个可行方案，flag=0 查找所有方案并返回最后一个可行方案
我测试时，flag传值0，需要自己改！！
由于迭代顺序，同样实验数据，返回的结构和你案例结构不一样，我在下图标注了。
#includestdio.h
#includemath.h
#includemalloc.h
#includestring.h
typedef struct bag
{
int bweight;
char *books;
}BAG;
int qj(BAG c1,BAG c2,int n,int *bws,int flag);//穷举所有n位2进制组合，返回最后一个可行方案（可能有多个方案）。
//参数：c1背包1，c2背包2，n书本个数，bws所有书本重量，标识：flag=1 找到第一个可行方案截止，flag=0查找所有方案
int checkOverLoad(BAG c1,BAG c2,int *bws,int n);
void add2(char *nums);//2进制字符串+1运算
void sub2(char *nums);//2进制字符串-1运算
int main()
{
BAG c1,c2;
int i,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;in;i++)
{
scanf("%d",bws[i]);
sum+=bws[i];
}
if(sum=c1.bweight+c2.bweight)
break;
else
printf("书本重量和超过背包负重和！请重新输入\n\n");
}
qj(c1,c2,4,bws,0);
//------------------------------打印结果-----------------------------
printf("\n输出：\n");
printf("book ");
for(i=0;in;i++)
printf("%d ",bws[i]);
printf("\n");
printf("c1 %s\n",c1.books);
printf("c2 %s\n",c2.books);
}
int qj(BAG c1,BAG c2,int n,int *bws,int flag)// 穷举 所有n位二进制数,
{
int i,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");
memset(c1.books,'0',n);
memset(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)
{
memset(nums1,0,n+1);
memset(nums2,0,n+1);
strcpy(nums1,c1.books);
strcpy(nums2,c2.books);
if(flag==1)
return 0;
}
printf("\n");
for(i=0;imax;i++)
{
add2(c1.books);
sub2(c2.books);
printf("%s\n",c1.books);
printf("%s\n",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)
return 0;
}
printf("\n");
}
printf("-----------------穷举结束------------------\n");
memset(c1.books,0,n+1);
memset(c2.books,0,n+1);
strcpy(c1.books,nums1);
strcpy(c2.books,nums2);
free(nums1);
free(nums2);
return 0;
}
void add2(char *nums)//2进制字符串加1
{
int i,n=strlen(nums),jin=0;
for(i=n-1;i=0;i--)
{
if(nums[i]=='0' i==n-1)
{
nums[i]='1';
break;
}
else if(nums[i]-'0'+jin==1 in-1)
{
nums[i]='1';
break;
}
else
{
jin=1;
nums[i]='0';
}
}
}
void sub2(char *nums)//2进制字符串减1
{
int i,n=strlen(nums),j=0;
for(i=n-1;i=0;i--)
{
if(nums[i]=='1' i==n-1)
{
nums[i]='0';
break;
}
else if(nums[i]-'0'-j==0 i!=n-1)
{
nums[i]='0';
break;
}
else
{
nums[i]='1';
j=1;
}
}
}
int checkOverLoad(BAG c1,BAG c2,int *bws,int n)//检查是否超载。超载返回1，否返回0
{
int i,sum1=0,sum2=0;
for(i=0;in;i++)
if(c1.books[i]=='1')
sum1=sum1+bws[i];
else
sum2=sum2+bws[i];
if(sum1c1.bweight)
{
printf("背包1超载！\n");
return 1;
}
if(sum2c2.bweight)
{
printf("背包2超载！\n");
return 1;
}
printf("方案可行！\n");
return 0;
}
C语言 背包问题 递归算法
提问者的这程序中用了递归算法，不过逻辑上有个小bug，就是在判断到n==0时，如果还有容量，那么返回的应该是第一个物品的重量而不是0。你可以改变容量C或物品参数来检验算法的逻辑正确性。
关于输出选择的物品，我加了一个数组，用来标记选择的物品。因为做完所有递归后只有最外层的标记是有效的，所以最后用了一个for循环来完成各层的标记。下面是改动后的程序：
int a[5]={0};
int MaxW(int n, int C, int *Volunme, int *Weight)
{
int W=0,W1=0,W2=0;
if (n == 0)
{
if(C = Volunme[0])
{
a[0]=1;
return W=1;
}
else
return 0;
}
else if(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=(W1W2?W1:W2);
a[n]=(W1W2?1:0);
}
else//背包空间放不下n,返回判断放n-1的情况
{
return MaxW(n-1,C,Volunme,Weight);
}
return W;
}
int main(void)
{
int n=5;int C=7;
int Volunme[] = {1,2,3,4,5};
int Weight[] = {1,2,5,7,8};
printf("最大重量为%d\n",MaxW(n-1,C,Volunme,Weight));
for(int i=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(int i=0;i5;i++)
{
if(a[i]==1)
printf("#%d ",i+1);
}
printf("\n");
return 0;
}
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语言01背包问题谁能简单说下
01背包问题就是有个容量为W的包，然后有一堆的物品(1...n)，其中wi、vi分别为第i个物品的重量和价值，现在需要求的就是使得包中所装的物品尽可能的价值高。那么这个物品放不放在包中对应取值0
or
1。其算法为动态规划，需要证明最优子结构性质。用s[i][j]表示只有前i个物品且包容量为j时所能等到的最大价值，而有递归式
s[i][j]=
s[i-1][j],
wij
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是只考虑整数的。
