| Вопрос: Задачка | Добавлено: 17.04.05 15:57 |
Автор вопроса:  Sharp | Web-сайт: sharpc.livejournal.com | ICQ: 216865379 |
| Ответы | Всего ответов: 17 |
|
Номер ответа: 16 Автор ответа:  Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #16 | Добавлено: 18.04.05 23:49 |
|
Sharp тут не в том дело, 500 или 6, это способ исключить часть непроизводительных проверок. И чем больше книг, тем больший эффект будет от такого способа.
Отмечу, чтр число 20,19,18,17,16-книжных комбинаций равно числу 1,2,3,4,5-книжных комбинаций :P Основную массу комбинаций придется все-таки тупо перебирать, что займет много времени. Мое решение работает быстрее.
Например для 20 книг 50,47,41,38,35,33,32,29,21,15,14,13,11,10,8,6,5,4,3,1 Правильное решение лежит в диапазоне 4-15 книг. Исключаются 1,2,3-книжные комбинации, и что самое приятное, самые тяжелые случаи- 20,19,18,17,16-книжные комбинации. |
||
|
Номер ответа: 17 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #17 | Добавлено: 01.05.05 19:07 |
|
Кто-то просил мое решение, нате:
/*
Имеется массив толщины W[N] для N книг и полка, на которую нужно поставить книги, чтобы осталось как можно меньше свободного места. При одинаковом свободном месте предпочтительнее вариант с меньшим числом книг. */ #include <windows.h> #include <stdio.h> //#define n 10 #define n 20 #define l 200 void main(){ //int w[n] = {100, 50, 29, 25, 24, 19, 0, 0, 0, 0}; int w[n] = {50,47,41,38,35,33,32,29,21,15,14,13,11,10,8,6,5,4,3,1}; /* Алгоритм решения - создать обнуленный массив a[l+1][n], заполнить a[w[i]][i] единицами (i:0 -> n-1) Итерация: Для каждого i:1->l, если в a[i][j] (j:0->n-1) содержится хотя бы одна единица, прибавлять к i все w[k] (k:0->n-1; a[i][k]!=1), и полученную сумму s, если она меньше l и строка w[s] не содержит единиц, скопировать туда строку w[l] и w[s][k]=1 и отметить логическую переменную "Были ли сделаны изменения в массиве" как TRUE. Повторить итерацию, если были сделаны изменения в массиве, установить ее значение в FALSE После окончания итераций проверить, какое максимальное m, для которого w[m] содержит единицы. Вывести m и все p, для которых w[m][p]==1 */ int i, j, k, p, q; int a[l+1][n]; for(i=0; i<=l; i++){ for(j=0; j<n; j++) a[i][j]=0; } for(i=0; i<n; i++){ for(j=0; j<n; j++) if(a[w[i]][j]  break;
if(j==n) a[w[i]][i]=1; } int h; int c, s; do{ c = 0; for(i=1; i<=l; i++){ for(j=0; j<n; j++) if(a[i][j] break;
if(j<n){ for(k=0; k<n; k++){ s = i+w[k]; if(!a[i][k] && s<=l){ for(p=0; p<n; p++) if(a[s][p] break;
if(p==n){ for(q=0; q<n; q++) a[s][q] = a[i][q]; a[s][k] = 1; c = 1; } } } } } } while(c); int m=0; for(i=l; i>0; i--){ for(j=0; j<n; j++){ if(a[i][j] {
m=i; break; } } if(m) break; } printf("Max width = %d\n", m); printf("Books: " ;
for(i=0; i<n; i++) if(a[m][i] printf("#%d (%d); ", i, w[i];
printf("\n" ;
MessageBox(0, "Результат", "Результат", MB_ICONASTERISK); } |
||