Заполнение вектора числами и условиями в C ++ - PullRequest
Новая
       11

Заполнение вектора числами и условиями в C ++

0 голосов
/ 15 февраля 2020

Работая над заданием бизнес-класса, в котором мы используем Excel для решения проблемы со следующими настройками и условиями, но я хотел найти решения, написав некоторый код на C ++, который мне наиболее знаком по некоторым школьным курсам .

У нас есть 4 магазина, в которые нужно вложить 10 миллионов долларов. Основные условия:

  1. Необходимо инвестировать не менее 1 млн. В магазин.
  2. Инвестиции в 4 магазина должны составить 10 миллионов.
  3. В соответствии с правилами, приведенными выше, наибольшую сумму можно инвестировать в один магазин: 7 миллионов

Каждый магазин имеет свой собственный уникальный процент возврата инвестиций, основанный на сумме денег, вложенных в магазин. Другими словами, существует большое количество комбинаций, которые можно получить, инвестируя в каждый магазин. Повторение чисел не имеет значения, если общее число равно 10 на комбинацию, но порядок чисел имеет значение.

Если моя математика верна, общее число комбинаций равно 7 ^ 4 = 2401, но количество рабочих решений меньше из-за того, что каждая комбинация должна равняться сумме 10.

То, что я пытаюсь сделать в C ++, это использовать циклы, чтобы заполнить каждую строку 4 числами, чтобы их сумма равно 10 (миллионам), например:

7 1 1 1

1 7 1 1

1 1 7 1

1 1 1 7

6 2 1 1

6 1 2 1

6 1 1 2

5 3 1 1

5 1 3 1

5 1 1 3

5 1 2 2

5 2 1 2

5 2 2 1

Буду признателен за советы, как справиться с этим. До сих пор не совсем уверен, что использование циклов - хорошая идея, хотя использование массива (возможно, 2D Array / Vector?) Я смутно предположил, что, возможно, рекурсивные функции облегчат решение.

Спасибо, что нашли время для читай, я ценю любые советы по поиску решений.

Редактировать: Вот код, над которым я работал, чтобы получить случайным образом 50 строк чисел. По-прежнему приходится реализовывать условия, в которых допустимые комбинации строк должны быть суммой 10 между 4; 

int main(){
    const int rows = 50;
    int values[rows][4];

    for (int i = 0; i < 50; i++) {
        for (int j = 0; j <= 3; j++){
            values[i][j]= (rand() % 7 + 1);
            cout << values[i][j] << " ";
        }
        cout << endl;
    }
}

1 Ответ

0 голосов
/ 15 февраля 2020

Вы можете вычислить это рекурсивно. Для каждого уровня у вас есть:

  1. Целевая сумма
  2. Количество элементов на этом уровне
  3. Минимальное значение, которое может иметь каждый отдельный элемент

Сначала мы определим наш тип возвращаемого значения. Каков ваш окончательный результат? Выглядит как вектор векторов для меня. Таким образом, наша рекурсивная функция будет возвращать то же самое.

Во-вторых, мы определяем результат нашего вырожденного случая (в «нижней части» рекурсии), когда число элементов на этом уровне равно 1. 

std::vector<std::vector<std::size_t>> recursive_combinations(std::size_t sum, std::size_t min_val, std::size_t num_elements)
{
    std::vector<std::vector<std::size_t>> result {};
    if (num_elements == 1)
    {
        result.push_back(std::vector<std::size_t>{sum});
        return result;
    }

    ...non-degenerate case goes here...

    return result;
}

Далее мы определяем, что происходит, когда этот уровень содержит более 1 элемента. Разделите сумму на все возможные пары «первого» элемента и «оставшейся» группы. например, если у нас есть цель sum 5, 3 num_elements и min_val 1, мы сгенерируем пары {1,4}, {2,3} и {3,2}, где первое число в каждая пара - для первого элемента, а второе число в каждой паре - оставшаяся сумма, оставшаяся для оставшейся группы.

Рекурсивно вызывайте функцию recursive_combinations, используя это второе число в качестве нового sum, и num_elements - 1 как новый num_elements, чтобы найти вектор векторов для оставшейся группы, и для каждого вектора в возвращаемом векторе добавьте первый элемент из вышеуказанного набора.

...