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;
}