0/1背包-递归算法
标签：第一个 div flag code 选择 value 编号 for ||
问题描述：
有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
总体思路：
针对每个物品只有选与不选。
1. 判断背包容量是否能承载第n个物品。
不能承载：判断下一个物品 能承载：选择 装 还是 不装。不装，判断下一个物品；装，背包容量-物品重量，现有价值+物品价值，判断下一个物品。
2. 当所有物品都判断完或者背包容量为0则当前递归结束。
代码：
#includeint maxNum[6]; //存放最优解的编号
int maxValue=0; //存放最大价值
int w[6] = {0,2,2,6,5,4};//每个物品的重量，第一个为0，方便角标对应
int v[6] = {0,6,3,5,4,6};//每个物品的价值，第一个为0，方便角标对应
int num = 5; //物品的个数
int cap = 10; //背包能承载的重量
void package01(int *flag,int n,int c,int nowValue) //nowvalue（现有价值）
{
int i;
if(n == 0 || c == 0) //当所有物品判断后 或者 背包容量为0时
{
if(nowValue > maxValue)
{
for(i=0;i6;i++)
maxNum[i] = flag[i];
maxValue = nowValue;
}
return;
}
if(c >= w[n])
{
flag[n] = 1;//第n物品被选
package01(flag, n-1, c-w[n], nowValue+v[n]);
}
flag[n] = 0;//第n物品没选
package01(flag, n-1, c, nowValue);
}
int main()
{
int flag[6] = {0,0,0,0,0,0};//标记选择的物品
int i;
package01(flag,num,cap,0);
for(i=1;i)
maxNum[i] == 1 ? printf("第%d号货物装了包中 \n",i) : 0;
printf("最大价值为:%d \n",maxValue);
}
0/1背包-递归算法
标签：第一个 div flag code 选择 value 编号 for ||
原文地址：https://www.cnblogs.com/xxaf/p/12785232.html
评论