сумма элементов =? определенному числу

@stalkersev · Регистрация: 01.06.2010

Author24 — интернет-сервис помощи студентам

Здравствуйте!

Уже второй день бьюсь:
Имеется массив, и нужно определить можно ли из суммы элементов (не обязательно всех) составить определенное число, ну например 10.
Например такой массив:

1 437 3 5 134 1 34 67 132

,здесь вот можно составить:

1+3+5+1 =10

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

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

Спасибо

valeriikozlov · 16.05.2011, 16:26

Сообщение от stalkersev

ведь должен же быть какой-то способ...

должен. Вот такой например (по приведенным Вами данным):
создаем массив размером 10 элементов (потому что нужно найти сумму 10), обнуляем все элементы.
1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива
0 0 0 0 0 0 0 0 0 0 <- значения элементов массива

Затем перебираем числа из массива: 1 437 3 5 134 1 34 67 132
С каждым текущим числом делаем следующее:
- проходим массив от последнего элемента (в данном случае с индексом 10) до первого. Если встречаем в массиве 1 и (индекс элемента равного 1+ текущее число <= 10), то элемент с индексом (индекс элемента равного 1+ текущее число) делаем равным 1.
- после этого элемент с индексом равным текущему числу делаем равным 1.

Если после этого элемент массива с индексом 10 равен 1, то можно. Если равен 0, то нельзя.
И даже можно потом вычислить из каких элементов можно составить необходимую сумму.

А теперь наглядно как будет меняться массив:
Изначально имеем:
1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива
0 0 0 0 0 0 0 0 0 0 <- значения элементов массива
- берем число 1. Имеем:
1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива
1 0 0 0 0 0 0 0 0 0 <- значения элементов массива
- берем число 437. Имеем:
1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива
1 0 0 0 0 0 0 0 0 0 <- значения элементов массива
- берем число 3. Имеем:
1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива
1 0 1 1 0 0 0 0 0 0 <- значения элементов массива
- берем число 5. Имеем:
1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива
1 0 1 1 1 1 0 1 1 0 <- значения элементов массива
- берем число 134. Имеем:
1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива
1 0 1 1 1 1 0 1 1 0 <- значения элементов массива
- берем число 1. Имеем:
1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива
1 1 1 1 1 1 1 1 1 1 <- значения элементов массива
и т.д.
Уже на этом этапе видно, что из взятых чисел можно составить любую сумму в диапазоне от 1 до 10 включительно.

silent_1991 · 16.05.2011, 17:35

Если не ошибаюсь, это один из частных случаев задачи об укладке ранца, так что гуглим в этом направлении.

@stalkersev · 17.05.2011, 01:41 **[ТС]**

Сообщение от silent_1991

Если не ошибаюсь, это один из частных случаев задачи об укладке ранца, так что гуглим в этом направлении.

Всем огромное СПАСИБО

Если кому надо, вот
здесь подробнее о задаче про ранец, похожей на мой случай, там код тоже есть, я тут еще добавил вывод тех слагаемых величин:

C#

            int[] weights = new int[9] { 1, 437, 3, 5, 134, 1, 34, 67, 132 };
            int[] costs = new int[9] { 1, 437, 3, 5, 134, 1, 34, 67, 132 };
            int needed = 10;
 
            int n = weights.Length;
            bool[] counts = new bool[n];
            
            int[,] dp = new int[needed + 1, n + 1];
            for (int j = 1; j <= n; j++)
            {
                for (int w = 1; w <= needed; w++)
                {
                    if (weights[j - 1] <= w)
                    {
                        dp[w, j] = Math.Max(dp[w, j - 1], dp[w - weights[j - 1], j - 1] + costs[j - 1]);
                        counts[j-1] = true;
                    }
                    else
                    {
                        dp[w, j] = dp[w, j - 1];
                    }
                }
            }
 
            for (int i = 0; i < n; i++)
            {
                if (counts[i] == true)
                    Console.Write(weights[i] + " + "); 
            }
 
            Console.WriteLine("=" + dp[needed, n]);
 
            Console.Read();

Не по теме:

Не посоветуете сайт или литературу по алгоритмизации подобных задач?

@stalkersev \|____WTF!?____\| 94 / 93 / 11 Регистрация: 01.06.2010 Сообщений: 227
		1
	сумма элементов =? определенному числу 16.05.2011, 15:28. Показов 997. Ответов 3 Метки нет (Все метки) Здравствуйте! Уже второй день бьюсь: Имеется массив, и нужно определить можно ли из суммы элементов (не обязательно всех) составить определенное число, ну например 10. Например такой массив: 1 437 3 5 134 1 34 67 132 ,здесь вот можно составить: 1+3+5+1 =10 Была идея после каждой неудачной попытки сортировать массив, чтобы каждый элемент находился на разных местах, но такой алгоритм тоже не подходит и задача решается неправильно Если кто знает, подскажите пожалуйста, можно на любом языке или просто описать алгоритм, ведь должен же быть какой-то способ... Спасибо 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	16.05.2011, 16:26	2
	Сообщение от stalkersev ведь должен же быть какой-то способ... должен. Вот такой например (по приведенным Вами данным): создаем массив размером 10 элементов (потому что нужно найти сумму 10), обнуляем все элементы. 1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива 0 0 0 0 0 0 0 0 0 0 <- значения элементов массива Затем перебираем числа из массива: 1 437 3 5 134 1 34 67 132 С каждым текущим числом делаем следующее: - проходим массив от последнего элемента (в данном случае с индексом 10) до первого. Если встречаем в массиве 1 и (индекс элемента равного 1+ текущее число <= 10), то элемент с индексом (индекс элемента равного 1+ текущее число) делаем равным 1. - после этого элемент с индексом равным текущему числу делаем равным 1. Если после этого элемент массива с индексом 10 равен 1, то можно. Если равен 0, то нельзя. И даже можно потом вычислить из каких элементов можно составить необходимую сумму. А теперь наглядно как будет меняться массив: Изначально имеем: 1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива 0 0 0 0 0 0 0 0 0 0 <- значения элементов массива - берем число 1. Имеем: 1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива 1 0 0 0 0 0 0 0 0 0 <- значения элементов массива - берем число 437. Имеем: 1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива 1 0 0 0 0 0 0 0 0 0 <- значения элементов массива - берем число 3. Имеем: 1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива 1 0 1 1 0 0 0 0 0 0 <- значения элементов массива - берем число 5. Имеем: 1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива 1 0 1 1 1 1 0 1 1 0 <- значения элементов массива - берем число 134. Имеем: 1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива 1 0 1 1 1 1 0 1 1 0 <- значения элементов массива - берем число 1. Имеем: 1 2 3 4 5 6 7 8 9 10 <- индексы элементов массива 1 1 1 1 1 1 1 1 1 1 <- значения элементов массива и т.д. Уже на этом этапе видно, что из взятых чисел можно составить любую сумму в диапазоне от 1 до 10 включительно. 1

silent_1991 5056 / 3116 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	16.05.2011, 17:35	3
	Если не ошибаюсь, это один из частных случаев задачи об укладке ранца, так что гуглим в этом направлении. 1

	17.05.2011, 01:41