我们有n种物品,物品j的重量为wj,价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。
如果限定每种物品只能选择0个或1个,则问题称为0-1背包问题。可以用公式表示为:
- 最大化
- 受限于
如果限定物品j最多只能选择bj个,则问题称为有界背包问题。可以用公式表示为:
- 最大化
- 受限于
如果不限定每种物品的数量,则问题称为*背包问题。
各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。
现在我们可以分为2类:即物体可以分割的背包问题及物体不可分割的背包问题,把后者成为0/1背包问题。
注:贪心法只能求解可分割的背包问题,如果不分割,求的不一定是最优解。
代码如下:
/*********贪婪法求解可分割的背包问题**************/ #include<iostream> using namespace std; typedef struct{ float p; float w; float v; }OBJECT; OBJECT object[7]; float x[7]; /*输入:背包载重量M,存放n个物体的价值p,重量w信息的数组object[] 输出: n个物体被装入背包的分量x[],背包物体的总价值 */ float knapsack_greedy(float M,OBJECT object[],float x[],int n) { int i; float m,p=0; for(i=0;i<n;i++) { object[i].v=object[i].p/object[i].w; x[i]=0; //解向量赋初值 } mergeSort(object,n); //按关键值v的递减顺序排序 m=M; //背包的剩余载重量 for(i=0;i<n;i++) { if(object[i].w<=m) { x[i]=1; m-=object[i].w; p+=object[i].p; } else { x[i]=m/object[i].w; p+=object[i].p*x[i]; break; } } return p; } int main() { cout<<"请依次输入第i个物体的price 和weight"<<endl; float a,b; for(int i=0;i<7;i++) { cin>>a>>b; object[i].p=a; object[i].w=b; } cout<<endl<<"请输入最大载重量M"; float M; float resultPrice=knapsack_greedy(M,object,x,7); cout<<"最大的价值为 "<<resultPrice<<endl; }
mergeSort函数如下:
#include<iostream> using namespace std; #define INFINITE 10000 #define ARRAYSIZE 80 void merge(int a[],int p,int q,int r); void mergeSort(int a[],int p,int r) { int q; if(p<r) { q=(p+r)/2; mergeSort(a,p,q); mergeSort(a,q+1,r); merge(a,p,q,r); } } void merge(int a[],int p,int q,int r) { int i,j; int n1=q-p+1; int n2=r-q; //creat array L[1,..n1+1], R[1,..n2+1]; int *L=(int *)malloc(sizeof(int)*ARRAYSIZE); int *R=(int *)malloc(sizeof(int)*ARRAYSIZE); for(i=1;i<=n1;i++) L[i]=a[p+i-1]; for(j=1;j<=n2;j++) R[j]=a[q+j]; //哨兵牌 L[n1+1]=INFINITE; R[n2+1]=INFINITE; i=1; j=1; for(int k=p;k<=r;k++) { if(L[i]<=R[j]) { a[k]=L[i]; i=i+1; } else { a[k]=R[j]; j=j+1; } } } void main() { int n,i; cout<<"请输入数组的大小n"; cin>>n; int *a=(int *)malloc(sizeof(int)*n); cout<<"请依次输入元素的值"<<endl; int x; for(i=0;i<n;i++) { cin>>x; a[i]=x; } mergeSort(a,0,n-1); cout<<"合并排序后为"<<endl; for(i=0;i<n;i++) cout<<a[i]<<ends; cout<<endl; }