❶ 用分支限界法求解0/1背包问题
1.问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。
2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。
#include
struct good
{
int weight;
int benefit;
int flag;//是否可以装入标记
};
int number=0;//物品数量
int upbound=0;
int curp=0, curw=0;//当前效益值与重量
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; i {
cout<<"请输入第件"<cin>>bag[i].weight;
cout<<"请输入第件"<cin>>bag[i].benefit;
bag[i].flag=0;//初始标志为不装入背包
cout< }
}
int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; num {
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//当前结点的c限界和u限界
for(int i=0; i {
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树
upbound=bound_u;//更改已有u限界,不更改标志
if( getbound(i, &bound_u)>bound_c )//遍历右子树
//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//从已有重量和效益加上新物品
bag[i].flag=1;//标记为装入
}
}
}
void Display()
{
cout<<"可以放入背包的物品的编号为：";
for(int i=0; iif(bag[i].flag>0)
cout<
｝
参考：
http://cache..com/c?word=%B7%D6%D6%A7%3B%CF%DE%BD%E7%3B%B7%A8%3B%C7%F3%BD%E2%3B0%2C1%3B%B1%B3%B0%FC%3B%CE%CA%CC%E2&url=http%3A//www%2Edaxiongonline%2Ecom/dvbbs/dispbbs%2Easp%3FboardID%3D31%26ID%3D1016&b=10&a=0&user=
❷ 分别用队列和优先级队列分支限界法解0—1背包问题
利用优先级分支限界法设计0/1背包问题的算法，掌握分支限界法的基本思想和算法设计的基本步骤，注意其中结点优先级的确定方法，要有利于找到最优解的启发信息。
要求：设计0/1背包问题的分支限界算法，利用c语言（c++语言）实现算法，给出程序的正确运行结果。
注意：
1. 把物品按照单位体积的价值降序排列；
2. 构造优先级分支限界法的状态空间树，共n层，第i层每个节点的两个分支分别代表第i个物品的取和不取；
3. 节点上需要保存的值有：S代表已装入背包的物品的总体积，V代表已装入背包的物品的总价值，u代表当前节点的上界，计算公式如下：
u=V+（C-S）（vi+1/si+1）
其中C是背包的总容积，vi+1代表第i+1个物品的价值，si+1代表第i+1个物品的体积。
4. 选择适当的数据结构（如最大堆，或者基本的线性数组）实现算法，输出最后结果。
❸ 分支限界法两道题目
利用优先级分支限界法设计0/1背包问题的算法，掌握分支限界法的基本思想和算法设计的基本步骤，注意其中结点优先级的确定方法，要有利于找到最优解的启发信息。要求：设计0/1背包问题的分支限界算法，利用c语言（c++语言）实现算法，给出程序的正确运行结果。注意：1.把物品按照单位体积的价值降序排列；2.构造优先级分支限界法的状态空间树，共n层，第i层每个节点的两个分支分别代表第i个物品的取和不取；3.节点上需要保存的值有：S代表已装入背包的物品的总体积，V代表已装入背包的物品的总价值，u代表当前节点的上界，计算公式如下：u=V+（C-S）（vi+1/si+1）其中C是背包的总容积，vi+1代表第i+1个物品的价值，si+1代表第i+1个物品的体积。4.选择适当的数据结构（如最大堆，或者基本的线性数组）实现算法，输出最后结果。
❹ 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语言算法求助：背包问题
//如果每种商品只有一件，是0-1背包问题
读入的数据N代表物品个数
V代表背包容量。
//对于你的例子
，输入为
//5
16
//2
3
//3
2
//4
3
//5
7
//6
9
//输出为21
#include
<iostream>
using
namespace
std;
#define
MAXSIZE
1000
int
f[MAXSIZE
+
1],
c[MAXSIZE
+
1],
w[MAXSIZE
+
1];
int
main()
{
int
N,
V;
cin
>>
N
>>
V;
int
i
=
1;
for
(;
i
<=
N;
++i)
{
cin
>>
c[i]
>>
w[i];
}
for
(i
=
1;
i
<=
N;
++i)
{
for
(int
v
=
V;
v
>=
c[i];
--v)
//c[i]可优化为bound,
bound
=
max
{V
-
sum
c[i,...n],
c[i]}
{
f[v]
=
(f[v]
>
f[v
-
c[i]]
+
w[i]
?
f[v]
:
f[v
-
c[i]]
+
w[i]);
}
}
//当i=N时，可以跳出循环单独计算F[V]
cout
<<
f[V]
<<
'\n';
system("pause");
return
0;
}
//如果每种可以有多个，是完全背包问题，
❻ 【在线等】分支限界法01背包问题C语言
哈哈,选我吧!#include
#include
usingnamespacestd;
#defineN100
class
HeapNode
{
public:
doubleupper,price,weight;
intlevel,x[N];
};
doubleMaxBound(inti);
doubleKnap();
voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);
stackHigh;
doublew[N],p[N];
doublecw,cp,c=7;
intn=4;
intmain()
{
inti;
for(i=1;i>w[i];
for(i=1;i>p[i];
coutbestp)bestp=cp+p[i];
AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);
}
up=MaxBound(i+1);
if(up>=bestp)
AddLiveNode(up,cp,cw,false,i+1);
if(High.empty())returnbestp;
HeapNodenode=High.top();
High.pop();cw=node.weight;cp=node.price;up=node.upper;
i=node.level;
}
}
❼ 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数组还是会多选了，你看看。
❽ 用分支限界法，写01背包问题！C语言版！急~~~~~~能不用结构体，尽量别用！
class Object{
friend int Knapsack(int *,int *,int,int,int *);
public :
int operator<=(Object a)const {return(d>=a.d);}
private:
int ID;
floa d;//单位重量价值
};
template <class Typew,class Typep> class Knap;
class bbnode{
friend Knap<int,int>;
friend int Knapsack （int *,int *,int,int,int *）;
private:
bbnode * parent;
bool LChild;
};
template<class Typew,class Typep>
class Heap Node{
friend Knap<Typep>;
public:
operator Typep ()const{return uprofit;}
private:
Typep uprofit,profit;//结点价值上界
Typew weight;//结点所相应的价值
int level;//结点所相应的重量
bbnode *ptr;//指向活结点在子集树中相应结点的指针
}；
template<class Typew,class Typep>
class Knap{
friend Typep Knapsack(Typep *,Typew *,Typew,int,int *);
public:
Typep MaxKnapsack();
private:
MaxHeap<HeapNode<Typep,Typew>>* H;
Typep Bound(int i);
void AddLiveNode(Typep up,Typep cp,Typew cw ,bool ch,int level);
bbnode * E;//指向扩展结点的指针
Typew c;//背包容量
int n;//物品总数
Typew * w;//物品重量数组
Typep * p;//物品价值数组
Typew cw;//当前装包重量
Typep cp;//当前装包价值
int * bestx;//最优解
}；
上界函数：
template<class Typew,class Typep>
Typep Knap<Typew,Typep>::Bound(int i)
{//计算结点所相应价值的上界
Typew clef=c-cw;//剩余容量
Typep b=cp;//价值上界
//以物品单位重量价值递减次序装剩余容量
while(i<n&&w[i]<=cleft){
cleft-=w[i];
b+=p[i];
i++;
}
//装填剩余容量装满背包
if（i<=n）b+=p[i]/w[i] * clef;
return b;
}
函数AddLiveNode将一个新的活结点插入到子集树和优先队列中
template<class Typep,class Typew>
void Knap<Typep,Typew>::AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev)
{//将一个新的活结点插入到子集树和最大堆H中
bbnode * b=new bbnode;
b->parent=E;
b->LChild=ch;
HeapNode<Typep,Typew>N;
N.uprofit=up;
N.profit=cp;
N.weight=cw;
N.level=lev;
N.ptr=b;
H->Insert(N);
}
template<class Typew,class Typep>
Typep Knap<Typew,Typep>::MaxKnapsack()
{//优先队列式分支限界法，返回最大价值，bestx返回最优解
//定义最大堆的容量为1000
H=new MaxHeap<HeapNode<Typep,Typew>>(1000);
//为bestx分配存储空间
bestx=new int[n+1];
//初始化
int i=1;
E=0;
cw=cp=0;
Typep bestp=0;//当前最优值
Typep up=Bound(1);//价值上界
//搜索子集空间树
while(i!=n+1){
//非叶结点，检查当前扩展结点的左儿子节点
Typew wt=cw+w[i];
if(wt<=c){//左儿子节点为可行结点
if(cp+p[i]>bestp)bestp=cp+p[i];
AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}
up=Bound(i+1);
//检查当前扩展结点的右儿子节点
if(up>=bestp)//右子树可能含最优解
AddLiveNode(up,cp,cw,false,i+1)
//曲下一个结点
HeapNode<Typep,Typew> N;
H->DeleteMax(N);
E=N.ptr;
cw=N.weight;
cp=N.profit;
up=N.uprofit;
i=N.level;
}
for ( int j=n;j>0;j-- )
{
bextx[j]=E->LChile;
E=E->parent;
}
return cp;
}
❾ 背包问题，C语言编程
原始题目： 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是
w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容
量，且价值总和最大。（取自网络）
问题简化： 1. 背包可容纳总重量为M
2. 有n个物品，每个重量为m[0]. m[1]. m[2] ......m[i] 对应每个物品的
价值为s[0]. S[1]. S[2]....s[i] (i<=n)
3. 放入第i个物品,比较m[i]和M的大小,不超过M则记录下当前价值s
4. 最终取得最大值s
实现方法：
定义三个浮点型一维数组float m[[n]和s[n]和y[n] 定义float M,float a,b定义int n,j, int i
请输入背包容量大小M：
please input the number of the things：
please input the value of the things：
把输入数据按顺序分别定义到数组中（若可以的话，把m[n]的数据由小到大排序，判断最小值m[0]和M的大小，若m[0]>M，输出error）
创建一个栈（这里的东西不太懂—-—）
将第一个数据压入栈底,定义i=0，把当前的m[i]赋值给a，s[i]赋值给b,把当前i存放进数组y[n]，以后在每次比较过程中，都把较大b值所对应的物品数存放进y[n]中
判断a<M（这里，若在4已经做过，则可省略，第一个数据一定小于M）
判断a+m[++i]<=M，为真，把第i（注意，此时i已经自增了，这个i是数组中的下标）个数据压入栈，赋值a=a+m[++i]，比较b和b+s[++i]的大小，赋值b=b+s[++i]（理论上，物品价值总该是为正的吧，若是这样的话，不用比较大小了，直接赋新值，直到跳出第一轮循环为止；另外有一种设想，若价值全为正，可以转而把问题这样简化：即给定容量大小和全为正的价值物品，现在想办法让背包放入物品的数量最多 就行了）；若为假，转10
如此进行一轮循环，直到出现10，此时b为一轮循环的最大值，return b,y[n]
当a+m[++i]>M，从栈中弹出m[i-2]，a=a-m[i-2],,当i原本就小于等于2的时候，则清除栈中数据，转12，判断a+m[i]<=M，为真，比较b和b-s[i-2]+s[i]，并把较大值赋给b，继续向下比较，这时候就不用压入栈中了,再定义一个j=1
判断a+m[i+j]<=M,为真，比较b和b-s[i-2]+s[i+j]大小，较大值赋给b，为假，从栈中弹出m[i-3]，当i原本就小于等于3的时候，则清除栈中数据，转12，判断a+m[i]<=M，为真，比较b和b-s[i-3]+s[i]（注意，这个b一直在被赋予最新值），如此进行第一轮循环，用for语句实现，因为下面还有嵌入
此时栈中没有数据，并且，已经把m[0]为栈底的循环计算完毕，现在开始计算m[1]为栈底的循环，在这一循环，忽略掉m[0]，所有可能情况已经在8-11计算过
依此往下，直到栈底被压入的是m[n]为止，计算完毕，输出b，并且输出数组y[n]
碰巧帮同学，也是这个问题，希望能帮助你。
❿ 背包问题(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);
}