Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 25.11.2010, 18:26
Новичок

Отправить личное сообщение для vorkulsky Посмотреть профиль Найти все сообщения от vorkulsky
 
Регистрация: 25.11.2010
Сообщений: 2

Интересная задача на смеси.
Для приготовления некоторого состава требуется N ингредиентов в заданных пропорциях. Однако, эти ингредиенты отсутствуют в чистом виде. Они доступны в виде составляющих K смесей (для каждой смеси указано, в каких пропорциях в нее входит каждый из требуемых N ингредиентов). Определить, можно ли из этих смесей приготовить новую смесь, в которой все ингредиенты будут находиться в требуемых пропорциях.

Примечание:
  • В файле в первой строке N и K.
  • Во второй строке смесь, которую нужно получить.
  • В остальных K строках K смесей.
  • Количество каждого ингридиента в смеси задается в процентах, но знак % не ставится.
  • Можно брать разное количество каждой смеси.
Пример входного файла:

Код:
2 2
30 70
10 90
80 20

Вот часть кода на с++, что я уже написал:

Код:
#include <iostream>
#include <fstream>
using namespace std;

void read(ifstream&, double**&, int&, int&);

int main()
{
	int n; // Количество ингридиентов
	int k; // Количество исходных смесей
	double** a;
	ifstream fin("in.txt");
	read(fin, a, n, k);
	fin.close();
	return 0;
}

void read(ifstream& fin, double**& a, int& n , int& k)
{
	fin>>n;
	fin>>k;
	k++; // k + смесь, которую нужно получить (она записывается в 0 строку матрицы)
	a=new double*[k];
	for (int i=0; i<k; i++)
	{
		a[i]=new double[n];
		for (int j=0; j<k; j++) fin>>a[i][j];
	}
	k--;
}

При решении задачи желательно использовать только стандартные типы данных и стандартные функции (кроме собственных).
Подробное словесное описание алгоритма или код на Pascal'e тоже приветствуются.
  #2  
Старый 25.11.2010, 23:42
гость

 
Сообщений: n/a

Короче. У тебя k n-мерных векторов v1, ..., v_k (смеси). Причем неотрицательных. Спрашивается, можно ли взять неотрицательную их линейную комбинацию и получить w (желаемый коктейль). Если чо, множество линейный неотрицательных комбинаций v_i - это будет такой конус с вершиной в начале координат - держи эту картинку в уме.

Как решать. Спроектируем все вектора на какую-то плоскость пересекающую этот конус. Например на плоскость x1 + .. + x_n = 1, т.к. на неё особенно легко проектировать - просто надо отнормировать каждый вектор, поделив его на сумму его компонент.

Утверждение: ответ к задаче "ДА" если и только если proj(w) лежит в n-1 мерной выпуклой оболочке точек proj(v_1), ..., proj(v_n).

Proof is left as an exercise to the reader.

Алгоритм: нормируешь вектора как я выше написал (делил каждый вектор на сумму его компонент). Отбрасываешь, скажем, последнюю компоненту каждого вектора, и ты уже на нужной n-1 мерной плоскости. Считаешь выпуклую оболочку своих k точек, потом проверяешь, принадлежит ли w ей. Всё.

Теперь по поводу реализации. Для N=3 тебе нужно уметь искать двухмерную выпуклую оболочку. Это не совсем тривиально, но есть готовый код. Вот я когда-то давно написал - http://www.algorithmist.com/index.ph...onvex_Hull.cpp - можешь брать.

Для N=2 разговор вообще ни о чем. Взять макс/мин, gроверить принадлежность одномерному интервалу.

Для N>3 тебе нужно брать трехмерные и более выпуклые оболочки. Поэтому перекочевывай на матлаб (convhulln - рекомендую!) или ищи сишные библиотеки. Сам с нуля не напишеш.

Последний раз редактировалось MBo, 26.11.2010 в 06:25.
  #3  
Старый 25.11.2010, 23:47
гость

 
Сообщений: n/a

пояснение

Сообщение от гость Посмотреть сообщение
Утверждение: ответ к задаче "ДА" если и только если proj(w) лежит в n-1 мерной выпуклой оболочке точек proj(v_1), ..., proj(v_n).
proj - проектирование. n-1 одномерная т.к. proj всех их проектирует на одно и ту же плоскость. На ней и ищем оболочку.
  #4  
Старый 25.11.2010, 23:49
гость

 
Сообщений: n/a

ах да. чуть не забыл. еще можно свести к линейному программированию и решать симплекс методом. для N>3 это попроще и побыстрее чем выпуклые оболочки искать.
  #5  
Старый 26.11.2010, 15:13
Новичок

Отправить личное сообщение для vorkulsky Посмотреть профиль Найти все сообщения от vorkulsky
 
Регистрация: 25.11.2010
Сообщений: 2

Большое спасибо. Да, очевидно, метод выпуклых оболочек будет работать, но задача должна решаться более просто и стандартными методами.

Математический алгоритм для данных из примера входного файла:

Здесь a-количество взятой 1-ой смеси и b - 2-ой смеси.

Теперь бы где-то еще реализацию алгоритма Гаусса на с++ найти.
  #6  
Старый 26.11.2010, 15:41
гость

 
Сообщений: n/a

Сообщение от vorkulsky Посмотреть сообщение
Большое спасибо. Да, очевидно, метод выпуклых оболочек будет работать, но задача должна решаться более просто и стандартными методами.
я уже тебе назвал симплекс метод

Цитата:
Математический алгоритм для данных из примера входного файла:

Здесь a-количество взятой 1-ой смеси и b - 2-ой смеси.

Теперь бы где-то еще реализацию алгоритма Гаусса на с++ найти.
этот тебе на этот раз повезло. в следующий раз жосско обломишся - метод гаусса выдаст тебе "решение" с отрицательными коэффициентами.

так что... конвекс халл или кипячение...
  #7  
Старый 26.11.2010, 15:47
гость

 
Сообщений: n/a

Сообщение от vorkulsky Посмотреть сообщение
Большое спасибо. Да, очевидно, метод выпуклых оболочек будет работать, но задача должна решаться более просто и стандартными методами.
посчитать выпуклую оболочку и решить ЗЛП симплекс методом - стандартные методы в любом серьезном матпакете. матлабе, мэпле и пр.
  #8  
Старый 26.11.2010, 15:50
гость

 
Сообщений: n/a

>Последний раз редактировалось MBo, Сегодня в 06:25.
какого...

Последний раз редактировалось MBo, 26.11.2010 в 16:02. Причина: Копролалией не страдаете случайно?
  #9  
Старый 26.11.2010, 16:12
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
>Последний раз редактировалось MBo, Сегодня в 06:25.
какого...
уж извините, пользуюсь всего возможностями великого и могучего. не стесняю себя в выразительных средствах. мы в интернетах в конце концеов или где? отставьте свою говённую цензуру
  #10  
Старый 26.11.2010, 16:23
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>не стесняю себя в выразительных средствах
Уж будьте добры, немного постесняйте, чтобы не приходилось выкашивать целиком посты или ветки, которые по информационной содержательности могут кому-то пригодиться.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Интересная задача гость Решение задач с acm.sgu.ru 4 08.01.2010 19:09
Интересная задача ozerich Математические алгоритмы (другое) 3 25.12.2008 23:02
Интересная прикладная задача оптимизации AdeptusMechanicus Математические алгоритмы (другое) 5 22.04.2008 12:09
Интересная задачка! гость Задачи 2 16.01.2008 13:21
Интересная задача MSDN Графы 3 13.12.2007 06:34