Алгоритмы

[Cris]

ну вообшем придлагаю использовать эту тему для обсуждения алгоритмов, и для их поска))

ну начну:
вообшем есть задача в которой я дошол до того что есть набор чисел n1,n2,n3,n4,n5, и есть еше одно число - m, нужно проверить можно ли найти такую сумму чисел n чтобы получилось m, т.е можноли разложить m на сумму n1,n2,n3,n4,n5..(не обезательно все).

сначала попробовал обычным перебором - долго))
потом вспомнил такое как жадный алгоримт, но мне нужен оптимальный его вариант так как чисел может быть окола 10 000, а их кол-во 50 000,
кто что подскажит?

 

[Пух]

это называеться так: "Кто поможет решить мне олимпиаду?"

 

[Cris]

это называеться так: "Кто поможет решить мне олимпиаду?"

несовсем, просто я ишю небольшой помоши)) я задачу решил но нужно зделать ее болие быстрей, эдак раз в 100)

 

[Пух]

несовсем, просто я ишю небольшой помоши)) я задачу решил но нужно зделать ее болие быстрей, эдак раз в 100)

ну да, а потом у тебя задачи по таймауту проходят, а у других, кто решал их сам, нет...

 

[quant]

решить эту задачу можно с помощью "Задачи рюкзака" (Knapsack Problem)
"Задача рюкзака" задаётся примерно так

Дан набор предметов с весом Wi и ценой Ci и есть рюкзак вместимостью W единиц веса, какова максимальная цена предметов, которые возможно взять в рюкзак ?

почитай решение в интернете, не поймёш пиши попытаюсь обьяснить
вообще очень приятно, что кто-то интересуется алгоритмами

 

[Cris]

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

 

[Cris]

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

 

[Cris]

кстати а нехто незнает какогонить алгоритма на шахматы:
нужен алгоритм который вычисляет за какое минимальное количество ходов КОНЕМ можно перебраться с одной точки в другую на шахматной доске любого размера)
смотрел алгоритмы прохода конем шахматной доски любого размера но там покачто ненашол нече интересного(

 

[quant]

Відповідь: Алгоритмы

тут сходу 2 мысли - если разность координат относятся как 2 : 1 то решение тривиальное, а вообще можно высчитывать все координаты за первый ход, за второй и так пока не заполнится нужная клетка
хотя уверен здесь есть более элегантное решение, после предлагаю решить

You must be registered for see links

а рекурсивный рюкзак будет примерно так выглядеть на c++

#include <cstdio>
#include <vector>
using namespace std;

bool knap(vector<int>& maj, int weig, int pos) {
	if(pos == maj.size()) { return false; }
	if( (weig == 0) || (weig - maj[pos] >= 0) && knap(maj, weig - maj[pos], pos + 1) ) { return true; }
	return knap(maj, weig, pos + 1); }

int main () {
	int m, a;
	vector<int> maj;
	scanf("%d", &m);
	while(scanf("%d", &a) != EOF) { maj.push_back(a); }
	puts(knap(maj, m, 0) ? "YES" : "NO");
	return 0; }

на вход - первое число m, дальше набор чисел

 

[Cris]

ну посотрел я ссылку, не то(( темблие там одно задание а не решение)