Рекурсивное суммирование максимальных чисел

У меня проблема с рекурсивным решением задачи суммирования. Проблема заключается в следующем: для заданных m и n составьте программу, которая будет суммировать n чисел до m так, чтобы использовались минимальные числа, а они есть. Если существует несколько решений, правильным будет то, которое использует большие числа. Пользователь вводит n, m и n чисел. Например: m=19 n=4 8,5,4,1 . Решение 8+5+5+1. если я вызову функцию со следующим числом в массиве и добавлю его, пока оно меньше суммы, решение будет найдено, только если следующие числа в массиве могут суммироваться до m. Если проблема такова: m=28 n=3 8,7,5 Решение 8+8+7+5, но моя программа пойдет 8+8+8 и попытается добавить 7 или 5 и вылетит, потому что нет из них может поместиться до 28. Итак, моя проблема заключается в том, чтобы вернуться более чем на 2 шага назад. Я могу перейти от 8+8+8+7 к 8+8+8, но не могу вернуться к 8+8. Это похоже на задачу о рюкзаке, только проще. Извините, что пока не включил мой код:

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

void outputt(vector<int>);

int x(int m,vector<int> s,int n,int u)
{
    static int sum=0;
    static int level=0;
    static vector<int> p;
    sum+=s[u];       
    p.push_back(s[u]);

    if(level==((n-u)+1))
    {
        p.pop_back();
        level=0;
        x(m,s,n,u-1);
    }

    if(sum>m)
    {
        level++;
        sum-=s[u];
        p.pop_back();
        x(m,s,n,u+1);
    }

    if(sum==m)
    {
        outputt(p);
        return sum;
    }
    else
        x(m,s,n,u);

    level++;
    if(level>n-1)
        outputt(p);

    if(sum==m)
        return sum;
    else
    {
        cout<<"....";
        x(m,s,n,level);
    }
}

void outputt(vector<int> x)
{
    for(vector<int>::iterator i=x.begin();i!=x.end();++i)
        cout<<*i<<" ";
}

int main()
{
    int m,n;
    cin>>m>>n;
    int z;
    vector<int> p;
    for(int i=0;i<n;++i)
    {
        cin>>z;
        p.push_back(z);
    }
    cout<<x(m,p,n,0);

    system("PAUSE");
}

Есть проблема с выводом, но сейчас это не важно.


c++ knapsack-problem
person Transcendental    schedule 09.03.2012    source источник
comment
Можем ли мы увидеть ваш код, пожалуйста?   -  person Chetter Hummin    schedule 09.03.2012
comment
Я думаю, что ваша постановка задачи не то, что вы имели в виду: напишите программу, которая будет суммировать n чисел до m так, чтобы использовались минимальные числа. количество слагаемых минимально   -  person Bernhard Kausler    schedule 09.03.2012
comment
Чувак, эта домашняя работа действительно предназначалась для IOCCC? Люди с большей вероятностью помогут вам, если смогут прочитать ваш код (и задать вопрос).   -  person Christian Rau    schedule 09.03.2012

Ответы (2)


arrow_upward
0
arrow_downward

Это недалеко от того, где вам нужно быть, это найдет решение как можно быстрее (наименьшее количество итераций), а не самое поверхностное решение.

#include <deque>
#include <iostream>
#include <iterator>
#include <algorithm>

template <typename IT, typename IT2>
bool perm_find(int num, IT start, IT last, IT2 output)
{
    for(IT first=start; first!=last; ++first)
    {
        int t=num-*first;
        if(t==0
        ||(t>0 && perm_find(t, start, last, output)))
        {   
            *output++=*first;
            return true;
        }   
    }
    return false;
} 

int main()
{
    int num;
    std::deque<int> pallet, results;

    std::cout << "Enter M: "      << std::endl;
    std::cin  >> num;
    std::cout << "Enter N vals: " << std::endl;

    std::copy(std::istream_iterator<int>(std::cin),
              std::istream_iterator<int>(),
              std::back_inserter(pallet));

    std::sort(pallet.rbegin(), pallet.rend());

    perm_find(num, pallet.begin(), pallet.end(), 
              std::back_inserter(results));

    std::copy(results.begin(), results.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    return 0;
}

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

EDTT: была ошибка, которую я исправил сейчас

person 111111    schedule 09.03.2012
comment
@IrrationalБез проблем брат - person 111111; 09.03.2012

arrow_upward
0
arrow_downward

Некоторые предложения:

  • избегайте статики в рекурсивном коде (можно использовать для отладки), пусть каждый экземпляр функции будет максимально независимым.
  • переберите все ваши числа (числа) в функции (x), чтобы вернуться к оптимальному решению.
  • передайте числа (ы) как константную ссылку, потому что они все равно не меняются.
  • также передать (как значение) контейнер с уже выбранными номерами (попытка), поэтому при возврате вы продолжите предыдущую попытку (откат). Это должно быть вашим фактическим состоянием.
  • сумма равна std::accumulate(attempt.begin(), try.end(), 0);
  • уровень — попытка.размер();
  • сначала отсортируйте свои числа по убыванию, чтобы получить минимальные числа.
  • верните вектор попытки, если он вам понадобится позже (теперь вы не всегда возвращаете сумму).
person stefaanv    schedule 09.03.2012