0-1背包问题（贪心法）

0-1背包问题（贪心法）

0-1背包问题：求从n种物品中选取若干物品装载容量为m的背包的最佳方案（x1，x2……xn）。其中第i个物品的重量为wi，价值为pi(i=1……n)。在åxiwi£m的前提下，最大。

贪心法

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1).不能保证求得的最后解是最佳的；
2).不能用来求最大或最小解问题；
3).只能求满足某些约束条件的可行解的范围。
分析：

目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)

故该题重点为每次选取单位容量价值最大的物品。

程序：

#include

#define max 100 //最多物品数

void sort (int n,float a[max],float b[max])//按价值密度排序

{

int j,h,k;

float t1,t2,t3,c[max];

for(k=1;k<=n;k++)

c[k]=a[k]/b[k];

for(h=1;h

for(j=1;j<=n-h;j++)

if(c[j]

{t1=a[j];a[j]=a[j+1];a[j+1]=t1;

t2=b[j];b[j]=b[j+1];b[j+1]=t2;

t3=c[j];c[j]=c[j+1];c[j+1]=t3;

}

}

void knapsack(int n,float limitw,floatv[max],float w[max],int x[max])

{float c1; //c1为背包剩余可装载重量

int i;

sort(n,v,w); //物品按价值密度排序

c1=limitw;

for(i=1;i<=n;i++)

{

if(w[i]>c1)break;

x[i]=1; //x[i]为1时，物品i在解中

c1=c1-w[i];

}

}

void main()

{

system("title megamirurutia—0-1背包问题（贪心法） ");

int n,i,x[max];

float v[max],w[max],totalv=0,totalw=0,limitw;

cout<<"请输入n和limitw:";

cin>>n >>limitw;

for(i=1;i<=n;i++)

x[i]=0; //物品选择情况表初始化为0

cout<<"请依次输入物品的价值："<

for(i=1;i<=n;i++)

cin>>v[i];

cout<

cout<<"请依次输入物品的重量："<

for(i=1;i<=n;i++)

cin>>w[i];

cout<

knapsack (n,limitw,v,w,x);

cout<<"the selection is:";

for(i=1;i<=n;i++)

{

cout<

if(x[i]==1)

{totalw=totalw+w[i];

totalv=totalv+v[i];}

}

cout<

cout<<"背包的总重量为："<背包所装载总重量

cout<<"背包的总价值为："<背包的总价值

}