#include<stdio.h>
#include<stdlib.h>
#define N 3
typedef struct PackNode
{
int w;
int v;
}PN,*pPn;
void swop(pPn a,pPn b)
{
PN temp=*a;
*a=*b;
*b=temp;
}
int partition(pPn p,int x,int y)
{
pPn pn=&p[y];
int i=x-1;
for(int j=x;j<y;j++)
{
if(p[j].w<=pn->w)
{
i++;
swop(&p[i],&p[j]);
}
}
swop(&p[i+1],pn);
return i+1;
}
int getSumW(pPn p,int i,int j)
{
if(i>j)
return 0;
int sum=0;
for(int k=i;k<=j;k++)
{
sum+=p[k].w;
}
return sum;
}
void printP(pPn p,int x,int y)
{
for(int i=x;i<=y;i++)
{
printf("(%d,%d) ",p[i].w,p[i].v);
}
printf("\n");
}
void getResult(pPn p,int W,int i,int j)
{
int r=partition(p,i,j);
int sumL=getSumW(p,i,r-1);
int sumM=p[r].w;
int sumR=getSumW(p,r+1,j);
if(sumL>W)
{
getResult(p,W,i,r-1);
}
else if(sumL+sumM >= W)
{
printP(p,i,r-1);
float f=(float)(W-sumL)/sumM;
printf("%.2f*(%d,%d) ",f,p[r].w,p[r].v);
}
else
{
printP(p,i,r);
getResult(p,W-sumL-sumM,r+1,j);
}
}
void main()
{
pPn p=(pPn)malloc(N*sizeof(PN));
p[0].w=30;
p[0].v=120;
p[1].w=10;
p[1].v=60;
p[2].w=20;
p[2].v=100;
//partition(p,0,2);
//printP(p,0,2);
getResult(p,50,0,2);
getchar();
}
