powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Мешки и кирпичи. Проблемы в реализации
25 сообщений из 30, страница 1 из 2
Мешки и кирпичи. Проблемы в реализации
    #38666459
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Доброго времени суток C:
Модератор: Лишнее удалено
У нас есть k мешков, каждый мешок вмещает определённое количество килограммов. У нас есть n кирпичей, каждый имеет вес. Как заполнить все мешки до упора, если это возможно. Каждый кирпич может быть только в одном мешке.

Я придумал два алгоритма решения данной задачи. Второй более длинный, но мне он пока более интересный. Прикладываю часть кода написанного на листке (ибо почему-то стали болеть глаза, и я сначала пишу код на листке). Сейчас стал его набирать, и возникли проблемы при выделении памяти на массив структур. Видимо такой тип структур нужно сразу инициализировать ?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
const char k=5;//количество мешков
const char n=10;//количество кирпичей

struct bag
{
	int weight;
	int pow_res;
	int res[];//массив в котором хранятся удовлетворяющие комбинации кирпичей
};

bag bags[10];



Можно ли исправить мой алгоритм малой кровью ? Пожалуйста не решайте её за меня (а если вам самим будет интересно, то поместите код в раскрывающийся знак плюса, пожалуйста)

Модератор: Вложение удалено.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666465
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Всё-же наберу код. Мне кажется не очень хорошо будет видно
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666481
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
const char k=5;//количество мешков
const char n=10;//количество кирпичей

struct bag
{
	int weight;
	int pow_res;
	int res[];//массив в котором хранятся удовлетворяющие комбинации кирпичей
};

bag bags[k];//мешки ТУТ ОШИБКА
int brick[n];//кирпичи с весом

int main(int argc, char** argv)
{
	//Нахожу все подходящие комбинации кирпичей для каждого мешка
	for(int i=0;i<k;i++)//цикл по мешкам
	{
		int* cur_res=&bags[i].res;//указатель на началь массива в котором будут храниться подходящие результаты
		for(int j=1;j<=(1<<n);j++)//цикл по комбинации множеств кипичей
		{
			int temp_res=0;
			for(int s=0;s<n;s++)//суммирую массу текущей комбинации кирпичей
			{
				temp_res+=brick[n]*(1&(j>>s));
			}
			(bags[i].weight==temp_res)? *(cur_res++)=j:false;
		}
	}

	//Нужно определить непересекающиеся для всех комбинации кирпичей
	//...
	return 0;
}



PS Я понимаю что этот алгоритм на оптимальный, в голове у меня есть более быстрый вариант
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666488
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryВот задача в моём понимании:
У нас есть k мешков, каждый мешок вмещает определённое количество килограммов. У нас есть
n кирпичей, каждый имеет вес. Как заполнить все мешки до упора, если это возможно. Каждый
кирпич может быть только в одном мешке.

Во-первых, кирпичи не сыпучие, заполнить ими мешок до полной вместимости чисто технически
невозможно.
Во-вторых, если суммарная вместимость мешков Х, а общий вес кирпичей Y, причём X >> Y, то
заполнить все мешки не получится точно так же технически.
Из чего следует вывод, что у тебя какое-то неправильное понимание задачи.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666506
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот пример: три мешка 10, 15, 120 кг.
Кирпичи: 3,12,105,15,16,4,3,3

1 мешок 4+3+3
2 3+12
3 сделать нелья

На выходе - пустое множество или что-нибудь.

Если суммарная масса мешков больше кирпичей тоже самое на выходе пусто, я же указал в постановке-"если это возможно". Если невозможно меня не интересует, очевидно это можно проверить.


Мешки и кирпичи абстракция, постановка задачи совершенно другая, так просто проще объяснить было
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666508
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ой, третий можно, да ещё двумя способами.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666514
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Даже если не заморачиваться на тему "сколько килограмм в литре", условие задачи непонятно. Какая целевая функция? Как сравнить какое из двух решений лучше?
Например: 4 мешка заполнено на 80% или три на 90% + один на 50%? что лучше?

Сформулируй и напиши функцию сравнения двух решений.

PS По сути это задача о рюкзаке, только рюкзаков больше одного.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666521
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryВот пример: три мешка 10, 15, 120 кг.
Кирпичи: 3,12,105,15,16,4,3,3
Вот это - практически классическая задача рюкзака. Но всё же придётся определить цель:
разложить вещи в минимальное число мешков или разложить вещи по всем имеющимся мешкам как
можно равномернее. Или просто ответить на вопрос "влезет или нет". В зависимости от цели
способы решения будут разные.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666553
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Каждый рюкзак должен быть заполнен на 100 процентов. 99 процентов не интересны. Нужно узнать как именно будут распределны кирпичи по мешкам. Не все кирпичи обязательно использовать.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666555
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryКаждый рюкзак должен быть заполнен на 100 процентов. 99 процентов не
интересны. Нужно узнать как именно будут распределны кирпичи по мешкам. Не все кирпичи
обязательно использовать.
Тогда не парься и делай полный перебор. Для малого количества кирпичей сойдёт.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666613
SS-phone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Вопросы по данному конкретному алгоритму, что я привел...там и есть полный перебор, вариация..точней вопросы по-реализации алгоритма, я ведь привел свой код.

Меня гонят ..
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666678
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
On 10.06.2014 16:12, SashaMercury wrote:

> У нас есть k мешков, каждый мешок вмещает определённое количество
> килограммов. У нас есть n кирпичей, каждый имеет вес. Как заполнить все
> мешки до упора, если это возможно. Каждый кирпич может быть только в
> одном мешке.

Это какая-то вариация на дискретную задачу о рюкзаке, которая является
каноническим примером NPполной задачи.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38666688
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SS-phoneВопросы по данному конкретному алгоритму, что я привел...там и есть полный
перебор, вариация..точней вопросы по-реализации алгоритма, я ведь привел свой код.
Выкинь этот алгоритм вместе с вопросами по нему, он дохлый.

Лично я бы попробовал рекурсию. В конце концов заполнение мешка размера n это заполнение
остатками кирпичей мешка размера n-x в котором уже лежит один кирпич размера х. Точно так
же как и заполнение остатками кирпичей k-1 мешков после заполнения первого.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38667023
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov Выкинь этот алгоритм вместе с вопросами по нему, он дохлый.

Почему дохлый ?

Он работает теоретически. Осталось решить проблему со структурой, и доделать вторую часть программы с пересечением.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38667037
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Алгоритм находит для каждого мешка все удовлетворяющие комбинации кирпичей, и записывает их в массив. 2 часть-найти непересекающиеся комбинации.
Проблема только в массиве, и она обозначена в первом сообщении.

PS Я знаю что можно короче. Сначала хочу сделать так.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38667235
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryDimitry Sibiryakov Выкинь этот алгоритм вместе с вопросами по нему, он дохлый.

Почему дохлый ?

Он работает теоретически. Осталось решить проблему со структурой, и доделать вторую часть программы с пересечением.

как бы хочу напомнить, что работать в данном случае может только алгоритм с полным перебором всех комбинаций.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38667290
SS-phone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Так я и перебираю все комбинации
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38667850
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryПочему дохлый ?
Назовём это "интуицией разработчика".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38667938
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне кажется, с большой долей вероятности, интуиция иногда ошибается :-). Я допишу этот алгоритм и покажу вам.
Но было бы-лучше побольше конкретики, что вам не нравится.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38668200
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryМне кажется, с большой долей вероятности, интуиция иногда ошибается :-). Я допишу этот алгоритм и покажу вам.
Но было бы-лучше побольше конкретики, что вам не нравится.
Спешу заметить, друг что в самом творческом процессе коим и является
"писание программ" или "синтез" своих алгоритмов, практически нет никакой
конкретики.

Творчество - не детерминировано, изначально интуитивно и не
раскладывается ни в какие формы или каноны.

И сейчас ты занимаешся самым что ни на есть творчеством.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38669016
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо, это конечно здорово звучит. Творчество. Жаль что только у меня мало кисточек.
Вообщем, несмотря на пять часов сна из-за Бразилии в 7 утра, я сделал что-то полезное. В последние дни у меня в голове крутится проблема с пересечением множеств разных мощностей, и пока я не решил её. Но я нахожу для каждого мешка все возможные комбинации. Мне части моего когда кажутся порнографией если честно, выделяю слишком много лишней памяти.
Вот что пока получилось. И это работает. Осталось только пересечение найти..

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
#include <stdio.h>
#include <stdlib.h>

const char k=3;//количество мешков
const char n=10;//количество кирпичей

struct bag
{
	unsigned int w;//вес
	unsigned int pow_comb;//настоящая мощность массива подходящих комбинаций
	int comb[1<<n];//в данном массиве будут храниться все возможные комбинации
} bags[k];

struct brick
{
	unsigned int w;//вес
} bricks[n];

void view_combination_break(int bag, int combination, int count_breaks)
{
	printf("\nindexes breaks for bag %i = ",bag);
	for (int i=0;i<count_breaks;i++)
	{
		if((combination>>i)&1!=0)
		{
			printf("%i ",i);
		}
	}
	printf("\n");
}

int main(int argc, char** argv)
{
	unsigned char checksum=0;//Все мешки наполнены
	int check_intersection=1;//Нет пересечений
	
	//Инициализация массива мешков и массива кирпичей
	printf("Initializing array bags\n");
	for(int i=0;i<k;i++)
	{
		printf("bag %i:",i);
		scanf("%u",&bags[i].w);
		bags[i].pow_comb=0;//можно ли это сделать при объявлении структуры ?
	}
	printf("\n Initializing array bricks\n");
	for(int i=0;i<n;i++)
	{
		printf("bricks %i:",i);
		scanf("%u",&bricks[i].w);
	}

	//Ищу все возможные комбинации для каждого мешка
	for(int i=0;i<k;i++)//Цикл по мешкам bags[i]
		{
			for(int j=0;j<=(1<<n);j++)//цикл по комбинации множеств кирпичей j
			{
				int temp_res=0;
				for(int s=0;s<n;s++)//суммирую массу текущей комбинации кирпичей
				{
					temp_res+=(1&(j>>s))*(bricks[s].w);
				}
				if(bags[i].w==temp_res)//Если сумма текущей комбинации кирпичей j равна массе текущего мешка i
				{
					bags[i].comb[bags[i].pow_comb]=j;
					bags[i].pow_comb++;
				}
			}

		}
	//Вывод на экран всех возможных комбинаций для каждого мешка
	for(int i=0;i<k;i++)
	{
		for(int j=0;j<bags[i].pow_comb;j++)
		{
			view_combination_break(i,bags[i].comb[j],n);
		}
	}
	//Поиск уникального пересечения
	return 0;
}
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38669045
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я только что придумал как сделать пересечение.
Берём массив F. Помещаем в него все подходящие комбинации первого массива.
Последовательно сравниваем элементы F со элементами 2 мешка. Если попарно всё ок, то перезаписываю F элементами a1|a2, далее F сравниваю с комбинациями 3 мешка, и т.д. Только надо хранить для каждого элемента F историю. Да это не просто, но мы видим что решение есть.
Всё, замыпаю.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38669056
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury, на всякий случай напомню что комбинаторика РАЗЛИЧАЕТ следующие понятия

сочетания

перестановки

размещения

и когда ты в тексте используешь термин из К. то нужно говорить точными понятиями.
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38669353
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Просто я не считаю что использую термины из комбинаторики. Ну да ладно. Сегодня вечером подумал, и сделал такую структуру для хранения 1. Побитового или всех комбинаций текущего набора. 2. Реальной мощности данного набора 3. Массива из k элементов, каждый элемент есть набор для каждого мешка. Пока вот такой код:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
//Поиск уникального пересечения
	//Размерность массива в котором будут храниться все пересечения
	int dim=1;
	for(int i=0;i<k;i++)
	{
		dim*=bags[i].pow_comb;
	}
	//Выделяю память на результирующий массив. Его нужно читать блоками размерности (k+2). Слева-направо: 1 int - побитовое или всей цепочки операций
	//2 int - реальная мощность текущей цепочки 3 : k+2 int - комбинация для каждого мешка
	int* res=(int*)malloc(sizeof(int)*dim*(k+2));
	int* s_res=res;
	int* cur=res;
//тестирую
	for(int i=0;i<bags[1].pow_comb;i++)
	{
		*(res+7*i)=bags[1].comb[i];
		*(res+1+7*i)=1;
	}






PS Видел сегодня Скиену- Алгоритмы. Стоит покупать ? или лучше начать с Кнута ? Я просто помню что кто-то мне эту книгу советовал. Или где я встречал эту фамилию совсем недавно..
...
Рейтинг: 0 / 0
Мешки и кирпичи. Проблемы в реализации
    #38669577
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryPS Видел сегодня Скиену- Алгоритмы. Стоит покупать ? или лучше начать с Кнута ? Я просто помню что кто-то мне эту книгу советовал. Или где я встречал эту фамилию совсем недавно..
Скачай, посмотри, а там решишь что тебе больше понравится.
...
Рейтинг: 0 / 0
25 сообщений из 30, страница 1 из 2
Форумы / C++ [игнор отключен] [закрыт для гостей] / Мешки и кирпичи. Проблемы в реализации
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]