#include<stdio.h>
#include <conio.h>
float **nhapDuLieu(float**A,int*n,int*c)
{
int j;
printf("
**************** THONG TIN BAI TOAN ******************
");
printf("
Nhap so luong do vat:n=");
scanf("%d",n);
printf("
Nhap khoi luong toi da:c=");
scanf("%d",c);
A=new float*[2];
for(int i=0;i<2;i++)
A[i]=new float[*n];
printf("Moi ban nhap gia tri va trong luong cua cac vat:");
for(int j=0;j<*n;j++)
{
printf("
Do vat %d:
",j);
printf("A[0][%d] = ",j);
scanf("%d",&A[0][j]);
printf("A[1][%d] = ",j);
scanf("%d",&A[1][j]);
}
return A;
}

void printOut(float **A,int n,int c)
{
printf("
So luong do vat n= %d",n);
printf("
Khoi luong toi da c=%d",c);
printf(" Gia tri va trong luong cua cac vat la:");
for(int i=0;i<2;i++)
{ printf("

");
for(int j=0;j<n;j++)
printf("\t%d",A[i][j]);
}
}
void result(int *A,int n,float MAX){
printf("
Nghiem cua bai toan xep balo:
");
for(int i=0;i<n;i++)
printf("%d\t",A[i]);
printf("
MAX=%d",MAX);
}
int kiemTra(int *A,int n){
int dem=0;
for(int i=0;i<n;i++)
if(A[i]==1)dem++;
return dem;
}
int*cong1VaoSoNhiPhan(int*A,int n){
int i=n-1;
while(i>=0){
if(A[i]==0){A[i]=1;
return A;
}
else{A[i]=0;
i--;
}
}
return A;
}
float *sapXep(float*A,int n){
float gan;
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++){
if(A[i]<A[j]){
gan=A[i];
A[i]=A[j];
A[j]=gan;
}
}
return A;
}

//Phuong phap de quy.
int *ppDeQuy(float**A,int n,int c,int*B,int*C,float*MAX){
float max=0,p=0;
int kt=kiemTra(B,n);
if(kt==n){
return C;
}
else{
p=0;
max=0;
B=cong1VaoSoNhiPhan(B,n);
//cout<<kt;
for(int j=0;j<n;j++)
if(B[j]==1){
p=p+A[1][j];
if(p<=c)max=max+A[0][j];
else{
max=0;
break;
}
}
if(max>*MAX){
*MAX=max;
for(int j=0;j<n;j++)
C[j]=B[j];
}
return ppDeQuy(A,n,c,B,C,MAX);
}
}

void main()
{

int i,n,c;
float MAX,**A;

printf("* 1:Nhap du lieu tu ban phim. *
");
printf("
**************************************** ******************
");
A=nhapDuLieu(A,&n,&c);
printf("
**************** THONG TIN BAI TOAN ******************
");
printOut(A,n,c);
int*B=new int[n];// khoi tao mang n phan tu luu nghiem bai toan;
int*C=new int[n];//Luu nghiem bai toan.
MAX=0;
for(i=0;i<n;i++)
{
B[i]=0; // khoi tao nghiem bai toan 0,0,...,0
C[i]=0;
}


C=ppDeQuy(A,n,c,B,C,&MAX);result(C,n,MAX);
printf("
**************************************** ******************
");
printf("* Chu y: Neu ten cua do vat tuong ung la:1,2,...n *
");
printf("* Nghiem tuong ung la: x1,x2,...,xn. Neu xi=0 thi *
");
printf("* xi khong duoc chon, xi=1 thi duoc chon cho vao balo. *
");
printf("
**************************************** ******************
");
getch();
}