#include
#include
#define N 50
typedef struct {
int list;
float p; // 物体的价值
float w; // 物体的重量
float v; // 物体的价值重量比
}Object;
void MERGE(Object A[],int low,int mid,int high)
{
int h,i,j,k;
Object* B=(Object*)malloc((high-low+1)*sizeof(Object));
h=low;i=0; j=mid+1;
while (h
{
if (A[h].v>=A[j].v )
{ B[i]=A[h];h=h+1 ;}
else
{B[i] =A[j]; j=j+1 ;}
i++;
}
if( h>mid)
{
for (k=j;k
{
B[i]=A[k];i=i+1; }
}
else
for (k=h;k
{ B[i] =A[k];i=i+1; }
i=0;
for (k=low;k
{
A[k] =B[i] ;
i++;}
free(B);
}
void MERGESORT(Object array[],int low,int high)
{
int mid;
if( low
{
mid=(low+high)/2;
MERGESORT(array,low,mid) ;
MERGESORT(array,mid+1,high) ;
MERGE(array,low,mid,high) ;
}
}
float knapsack_greedy(float m, Object instance[], float x[], int n){
int i;
float p = 0; // 总价值初始为0
/* 初始化 */
for(i=0; i
instance[i].v = instance[i].p / instance[i].w; // 计算物体价值重量比
x[i] = 0; // 默认放入份量为0
}
/* 对物体进行排序：按v的递减顺序 */
MERGESORT(instance,0,n-1);
/* 填物过程 */
for(i=0; i
if(instance[i].w
x[i] = 1; // 将物体全部装入 置x[i]为1
m -= instance[i].w; // 从剩余载重量中去掉物体的重量
p += instance[i].p; // 总价值加上物体的完整价值
}else{ // 若物体重量大于剩余载重量
x[i] = m / instance[i].w; // 置x[i]为剩余载重量/物体重量：即最大能置入的百分比
p+= x[i]*instance[i].p; // 总价值加上物体装入部分的价值
break; // 此时背包已满，可以退出循环
}
}
return p;
}
void main(){
Object instance[N]; // n个物体的属性
float x[N]; // n个物体装入背包的份量(0
float m; // 背包的最大载重量
int n; // 物体个数
int i;
cout
cin>>m;
cout
cin>>n;
cout
cout
for(i=0; i
cout
instance[i].list=i+1;
cin>>instance[i].p>>instance[i].w;
cout
}
float maxv = knapsack_greedy(m, instance, x, n);
cout
cout
cout
cout
for( i=0; i
cout
cout
cout
}
}
#include
#include
#define N 50
typedef struct {
int list;
float p; // 物体的价值
float w; // 物体的重量
float v; // 物体的价值重量比
}Object;
void MERGE(Object A[],int low,int mid,int high)
{
int h,i,j,k;
Object* B=(Object*)malloc((high-low+1)*sizeof(Object));
h=low;i=0; j=mid+1;
while (h
{
if (A[h].v>=A[j].v )
{ B[i]=A[h];h=h+1 ;}
else
{B[i] =A[j]; j=j+1 ;}
i++;
}
if( h>mid)
{
for (k=j;k
{
B[i]=A[k];i=i+1; }
}
else
for (k=h;k
{ B[i] =A[k];i=i+1; }
i=0;
for (k=low;k
{
A[k] =B[i] ;
i++;}
free(B);
}
void MERGESORT(Object array[],int low,int high)
{
int mid;
if( low
{
mid=(low+high)/2;
MERGESORT(array,low,mid) ;
MERGESORT(array,mid+1,high) ;
MERGE(array,low,mid,high) ;
}
}
float knapsack_greedy(float m, Object instance[], float x[], int n){
int i;
float p = 0; // 总价值初始为0
/* 初始化 */
for(i=0; i
instance[i].v = instance[i].p / instance[i].w; // 计算物体价值重量比
x[i] = 0; // 默认放入份量为0
}
/* 对物体进行排序：按v的递减顺序 */
MERGESORT(instance,0,n-1);
/* 填物过程 */
for(i=0; i
if(instance[i].w
x[i] = 1; // 将物体全部装入 置x[i]为1
m -= instance[i].w; // 从剩余载重量中去掉物体的重量
p += instance[i].p; // 总价值加上物体的完整价值
}else{ // 若物体重量大于剩余载重量
x[i] = m / instance[i].w; // 置x[i]为剩余载重量/物体重量：即最大能置入的百分比
p+= x[i]*instance[i].p; // 总价值加上物体装入部分的价值
break; // 此时背包已满，可以退出循环
}
}
return p;
}
void main(){
Object instance[N]; // n个物体的属性
float x[N]; // n个物体装入背包的份量(0
float m; // 背包的最大载重量
int n; // 物体个数
int i;
cout
cin>>m;
cout
cin>>n;
cout
cout
for(i=0; i
cout
instance[i].list=i+1;
cin>>instance[i].p>>instance[i].w;
cout
}
float maxv = knapsack_greedy(m, instance, x, n);
cout
cout
cout
cout
for( i=0; i
cout
cout
cout
}
}