本文目录一览：
c语言背包问题
算法分析：
使用贪心策略求解此类问题时，首先要选出最优的度量标准。
可供选择的度量标准有三种：价值，容量，单位价值（v/w，价值/重量）。
显然，价值高的物品容量可能太大，容量大的物品价值也可能很低。最优的度量标准是单位价值。
背包问题算法思路：
1、将各个物品按照单位价值由高到低排序；
2、取价值最高者放入背包；
3、计算背包的剩余空间；
4、重复2-3步，直到背包剩余容量=0或者物品全部装入背包为止（对于0-1背包，终止条件为背包剩余容量无法装入任意一件物品或者物品全部装入背包）。
#includestdio.h
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已经按照单位价值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包问题
* n:物品个数
* c：背包容量
* v[]:每个物品的价值
* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;in;i++)
{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}
for(i=0;in;i++)
{
if(w[i] c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
if(i=n)//还可以放入一个物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包问题
* n:物品个数
* c：背包容量
* v[]:每个物品的价值
* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;in;i++)
{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}
for(i=0;in;i++)
{
if(w[i] c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
}
#includestdio.h
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已经按照单位价值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包问题
* n:物品个数
* c：背包容量
* v[]:每个物品的价值
* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;in;i++)
{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}
for(i=0;in;i++)
{
if(w[i] c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
if(i=n)//还可以放入一个物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包问题
* n:物品个数
* c：背包容量
* v[]:每个物品的价值
* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;in;i++)
{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}
for(i=0;in;i++)
{
if(w[i] c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
}
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语言简短代码，大神们最好带解释和注释，谢谢！！！
不知道你说的哪种类型的背包，我就说下最简单的吧。
一、01背包
问题描述：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
（1）基本思路：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。-c语言背包问题
意思简要来说就是：如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。-c语言背包问题
（2）优化空间复杂度：以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：-c语言背包问题
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符。-c语言背包问题
（3）初始化的细节问题：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。-c语言背包问题
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。-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],
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是只考虑整数的。
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;
}
