㈠ 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语言01背包问题动态规划出错。麻烦各位帮忙纠错一下，谢谢
你这是完全背包。01背包每个物品只能装一次，因此必须和上一个物品比较，否则会出现重复装的情况。
f[i][j]表示把前i个物品装入容量为j的箱子能得到的最大价值
则有：
f[i][j]=max(f[i-1][j]/*不装*/,f[i-1][j-c]+v/*装，但必须满足j>=c*/)
改好的代码如下所示：
#include<algorithm>
#include<iostream>
#include<string.h>
usingnamespacestd;
intmain(intargc,char*argv[])
{
intc[]={0,5,3,4,3,5};//消耗
intv[]={0,500,200,300,350,400};//value
intf[6][11];
memset(f,0,sizeof(f));//归位0
for(inti=1;i<=(sizeof(c)/sizeof(int)-1);i++) //i第几个物品
{
for(intp=1;p<=10;p++)//表示10个空间
{
if(p<c[i])
{
f[i][p]=f[i][p-1];
}
else
{
//f[i][p]=max(f[i-1][p],f[i][p-c[i]]+v[i]);
f[i][p]=max(f[i-1][p],f[i-1][p-c[i]]+v[i]);
}
}
}
printf("%d",f[5][10]);
return0;
}
㈢ C语言动态规划——0-1背包问题
以前写的 自己看吧
#include<stdio.h>
int w[5]={0,3,5,2,1},p[5]={0,9,10,7,4};
int c=7,n=4;
int cw=0,cp=0,bestp=0;
int x[10]={0};
void try(int k)
{
int i;
if(k>n)
{
for(i=1;i<=n;i++)
printf("%2d",x[i]);
printf(" %d %d\n",cw,cp);
if(bestp<cp)
bestp=cp;
}
else
{
x[k]=1;
cw=cw+w[k];
cp=cp+p[k];
if(cw<=c)
try(k+1);
x[k]=0;
cw=cw-w[k];
cp=cp-p[k];
if(cw<=c)
try(k+1);
}
}
main()
{
clrscr();
try(1);
printf("best_P=%d",bestp);
}
㈣ 求动态规划01背包问题c语言的代码，要稍微简单且无错的。谢谢
我写个C++的。
#include<iostream>
#define MAX 1111
using namespace std;
int f[MAX],n,m,v,w;
int main(){
cin>>n>>m;//n表示个数，m表示背包容量
for(int i=1;i<=n;++i){
cin>>v>>w;//v=价值，w=重量
for(int j=m;j>=w;--j)
if(f[j]<f[j-w]+v)
f[j]=f[j-w]+v;
}
cout<<f[m]<<'\n';
return 0;
}
C++和C应该都差不多吧。。这个最简洁了 。顺便一句，如果要能无限放的话
for(int j=m;j>=w;--j)这一句变成for(int j=w;j<=m;++j)就行了。
㈤ 编程序解决0 1 背包问题（c语言）
for (int i=1;i<=n;i++)
for (int j=0;j<=v;j++)
if (j<w[i]) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);//w为重量，c为价值，n为物品个数，v为背包容量
printf ("%d",f[n][v]);
㈥ 贪婪启发式算法求解01背包问题（C语言编码实现）
这种要么装要么不装，应该采用动态规划算法解决吧
㈦ c语言，01背包问题
没错就是声明
intA();
intmain()
{
A();
return0;
}
intA()
{
intB();
B();
return1;
}
intB()
{
return0;
}//这样试试就知道了
㈧ 用分支限界法，写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;
}
㈨ 【在线等】分支限界法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;
}
}
㈩ 0-1背包的c语言程序运行结果总是出错，求指教
学妹。。。
算法实习又遇到难题了？？？给你个链接，好多背包问题的讲解哦
http://wenku..com/view/e97568d6b9f3f90f76c61b7d.html