C++作業:欲張り法で問題を解く

3906 ワード

/*

1.     :       A(  2838594)           N(   3)  
  A   N  ,           ( 2354)


2.      200   。 8   ,           。             ,
                     。
A	B	C	D	E	F 	G	H
40	55	20	55	30	40	45	55
35	20	20	40	35	15	40	20

*/

#include <stdio.h>
#include <string.h>

// ------------------  1  -----------------

//   n             ,              
// "28318594" ->   "1",  "8594" 
static char take_minimum(char* buf, int n)
{
	int len = strlen(buf);
	if(n > len) n = len;

	char min = '9' + 1;
	int  pos = -1;

	for(int i=0; i<n; i++)
	{
		char ch = buf[i];
		if(ch < min)
		{
			min = ch;
			pos = i;
		}
	}

	//        
	memmove(buf, buf + pos + 1, len - pos);
	return min;
}

static int ex_1(int a, int n)
{
	//  a     ,     
	char buf[32] = {0};
	sprintf(buf, "%d", a);
	int  size = strlen(buf);

	//     ,  a  m  , m = size - n
	int m = size - n;

	//  a   n   ,        
	while(m > 0)
	{
		//                 ,      
		//      "    "

		char min = take_minimum(buf, strlen(buf) - (m-1));
		printf("%c", min); //         
		m --;
	}

	return 0;
}

// ------------------  2  -----------------
struct Object
{
	char label; //   
	int  volumn;   //   
	int  value;    //   
	float ratio;   //      
	int	 count;		//      
};

static int ex2()
{
	/*
	A	B	C	D	E	F 	G	H
		40	55	20	55	30	40	45	55
		35	20	20	40	35	15	40	20
	*/
	int MAX_VOLUMN = 200;
	int i;

	//     struct,       
	Object objs[8] =
	{
		{ 'A', 40, 35, 0.0f, 0 },
		{ 'B', 55, 20, 0.0f, 0 },
		{ 'C', 20, 20, 0.0f, 0 },
		{ 'D', 55, 40, 0.0f, 0 },
		{ 'E', 30, 35, 0.0f, 0 },
		{ 'F', 40, 15, 0.0f, 0 },
		{ 'G', 45, 40, 0.0f, 0 },
		{ 'H', 55, 20, 0.0f, 0 }
	};

	//      
	for(i=0; i<8; i++)
	{
		objs[i].ratio = (float)  objs[i].value / objs[i].volumn;
	}

	//   :    , value/volumn    ,  ratio      
	//     
	for(i=0; i<7; i++)
	{
		int maxobj = i;
		for(int j=i+1; j<8; j++)
		{
			if(objs[j].ratio > objs[maxobj].ratio)
				maxobj = j;
		}

		//   
		if(maxobj != i)
		{
			Object temp = objs[maxobj];
			objs[maxobj] = objs[i];
			objs[i] = temp;
		}
	}
	
	//    ,             
	int total_volumn = 0; //      
	for(i=0; i<8; i++)
	{
		if(total_volumn >= MAX_VOLUMN) break;

		Object* obj = &objs[i]; //        obj
		int volumn = MAX_VOLUMN - total_volumn; //     

		int num = volumn / obj->volumn; //      ?
		obj->count = num; 
		total_volumn += num * obj->volumn;

		printf("  :%c,  :%d x %d,    :%d
" ,obj->label, num, obj->volumn, total_volumn); } return 0; } int main() { // char s[] = "28318594"; // char ch = take_minimum(s, 5); if(0) { // 1 // int a = 0; printf("a="); scanf("%d", &a); // int n = 0; printf("n="); scanf("%d", &n); ex_1(a, n); } if(1) { // 2 ex2(); } return 0; }