㈠ 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