модификация Задачи о ранце (рюкзаке)

Тема в разделе "C/C++/C#", создана пользователем razval, 25 янв 2011.

  1. razval

    razval New Member

    Регистрация:
    25 янв 2011
    Сообщения:
    3
    Симпатии:
    0
    доброго времени суток.
    постановка задачи:
    с клавиатуры вводиться массив элементов, каждый элемент имеет свой вес, требуется разбить этот масcив на двое, так что бы суммы элементов новых массивов были наиближайщие.
    пример:
    ввод:
    4, 2, 11, 9
    вывод:
    общий вес: 26
    первый массив: 11, 2
    вес: 13
    второй массив: 9, 4
    вес: 13
    не могу разобраться с индексацией в массивах(
    листинг на cpp
    Код (C++):
    #include <iostream>
    using namespace std;
    const int u=5, y=5;
    main()
    {
    int n; //количество вещей
    int j;//вес вещей
    int k[j]; //массив для хранения вещей
    int mas1[u]={0,0,0,0,0};//рюкзак 1
    int mas2[y]={0,0,0,0,0};//рюкзак 2
    int i=0; //счетчик
    int sum=0,sum1=0,sum2=0; //общий вес
    cout<<"введите количество вещей: ";
    cin>>n;
    while(i<n)
    {
    ++i;
    cout<<"введите вес вещи № "<<i<<": ";
    cin>>k[i];
    sum+=k[i];
    };
    cout<<"общий вес: "<<sum<<endl;
    //сортировка
    for(i=n; i>=1; --i)
    for(j=1; j<i; ++j)
    {
    if(k[j]<k[j+1])
    {
    int m=k[j];
    k[j]=k[j+1];
    k[j+1]=m;        
    }
    }
    //вывод сортировки
    /*   for(i=1; i<=n; ++i)
    {
    cout<<k[i]<<" ";
    } */

    /*тут нужно что-то сделать с индексацией,
    чтобы он перебирал элементы массива k
    и по весу раскидывал в два массива ???*/

    for(int i=1; i<=n; ++i)//просмотр всех вещей
    {
    if (sum1>=sum2)
    {
    for(int l=1; l<5; ++l)
    {
    mas1[0]=k[1];  
    }
    for(int i=0; i<5; ++i)         
    {
    sum1+=mas1[i];                 
    }
    }
    else
    {
    mas2[0]=k[2];

    for(int i=0; i<5; ++i)
    {
    sum2+=mas2[i];
    }
    }
    }
    //вывод массивом и их сумм
    cout<<"первый рюкзак: ";
    for(int i=0; i<5; ++i)
    {
    cout<<mas1[i]<<" ";
    }
    cout<<endl;
    cout<<"вес первого рюкзака: "<<sum1<<endl;
    cout<<"второй рюкзак: ";
    for(int i=0; i<5; ++i)
    {
    cout<<mas2[i]<<" ";
    }
    cout<<endl;
    cout<<"вес второго рюкзака: "<<sum2;
    getchar();
    getchar();
    }
     
  2. StudyMen

    StudyMen Гость

    Профессиональная и оперативная помощь студентам в решении задач по программированию.
    Реализатор: ведущий разработчик. Более 5000 выполненных работ по программированию для студентов всех ВУЗов России более чем на 25 различных языках программирования.
    Стоимость: от 30 рублей за задачу.
    Оплата: оплата производится после выполнения задачи (то есть без предоплаты).
    Способ оплаты: электронный платежные системы webMoney и Яндекс-деньги.
    Контакты для связи:
    Email: administrator@studymen.ru
    Skype: studymen
    ICQ: 639151387
     
  3. IrineK

    IrineK Гость

    Индексация массива не имеет отношения к сумме весов.
    Кроме того, сортировка по возрастанию тоже не поможет, если составляющие элементы будут неоднородными. Например: {1;1;11;1}. Тогда едиственным решением с минимальным разрывом будет {1;1;1} в один рюкзак и {11} - во второй. Общая сумма: S = 14, сумма первого рюкзака S1 = 3, второго S2=11. Разрыв: 14 - 2*3 = 8

    Поскольку размерность N исходного набора невелика (ограничимся N<=8), можно организовать полный перебор всех возможных сочетаний без повторений: С(1;N), C(2;N)...C(N-1;N). Для каждого сочетания (k) нужно посчитать сумму составляющих элементов Sk.
    Условием оптимальности будет требование к разрыву: S-2Sk ->min

    Нужно организовать вывод сответствующего набора (можно сформировать строку из номеров элеметов), его сумму Sk(вес) и минимальный разрыв (S-2Sk)
     
  4. razval

    razval New Member

    Регистрация:
    25 янв 2011
    Сообщения:
    3
    Симпатии:
    0
    а можно хотя бы немного кода или псевдокода, этого куска
     
  5. IrineK

    IrineK Гость

    ОК. Вот решение для частного случая: общего набора из 4 элементов

    #include <iostream>
    using namespace std;

    const int n=4;//только для набора из 4 элементов
    const int m=14;//количество всех возможных сочетаний при раскладке в 2 рюкзака

    void main()
    {
    int i,j,k,opt1,opt2;

    int S=0;//общая сумма
    int set[n]; //общий набор
    int bag1[n-1]={0,0,0};//рюкзак 1
    int bag2[n-1]={0,0,0};//рюкзак 2

    int Si[m]; //суммы каждого из сочетаний
    int descr[n-1][m];//описания каждого из сочетаний
    int cur=0; //текущий индес для массивов сочетаний

    cout<<"Specify the set of 4 numbers"<<endl;
    for (i=0;i<n;i++)
    {
    cout<<"Number "<<(i+1)<<" ";
    cin>>set;
    S+=set;//определение общей суммы
    }

    //----------сочетания С(1;4),1 элемент из 4

    for (i=0;i<n;i++)
    {
    Si[cur]=set;
    descr[0][cur]=set;
    descr[1][cur]=0;
    descr[2][cur]=0;
    cur++;
    }
    //----------сочетания С(2;4),2 элемента из 4

    for (i=0;i<n-1;i++)
    for (j=i+1;j<n;j++)
    {
    Si[cur]=set+set[j];
    descr[0][cur]=set;
    descr[1][cur]=set[j];
    descr[2][cur]=0;
    cur++;
    }
    //----------сочетания С(3;4),3 элемента из 4

    for (i=0;i<n-2;i++)
    for (j=i+1;j<n-1;j++)
    for (k=j+1;k<n;k++)
    {
    Si[cur]=set+set[j]+set[k];
    descr[0][cur]=set;
    descr[1][cur]=set[j];
    descr[2][cur]=set[k];
    cur++;
    }
    //---------вывод всех наборов и сумм
    cout<<"-----------------------------------------------------------"<<endl;
    for (i=0;i<m;i++)
    cout<<"Bag "<<descr[0]<<","<<descr[1]<<","<<descr[2]<<"; Si = "<<Si<<endl;

    //--------поиск оптимального набора
    int min=S;//самое большое число в рамках задачи

    for (i=0;i<m;i++)
    if (abs(S-2*Si)<min)
    {
    min=abs(S-2*Si);
    opt1=i;
    }
    opt2=m-opt1-1;// используем симметрию задачи

    cout<<"-----------------------------------------------------------"<<endl;
    cout<<"Optimum Bag1: "<<descr[0][opt1]<<","<<descr[1][opt1]<<","<<descr[2][opt1]<<"; Si = "<<Si[opt1]<<endl;
    cout<<"Optimum Bag2: "<<descr[0][opt2]<<","<<descr[1][opt2]<<","<<descr[2][opt2]<<"; Si = "<<Si[opt2]<<endl;

    }

    Попробуйте ваш исходный {4,2,11,9}, мой исходный {1,1,11,1}, а также любой другой.
     
  6. razval

    razval New Member

    Регистрация:
    25 янв 2011
    Сообщения:
    3
    Симпатии:
    0
    to IrineK

    Спасибо, интересный вариант.
     
  7. dreamer

    dreamer Гость

    Зато сортировка по убыванию поможет.
     
  8. IrineK

    IrineK Гость

    С этого места поподробней, пожалуйста.
     
  9. dreamer

    dreamer Гость

    Из исходного массива выбираются элементы от большего к меньшему. На каждой итерации сравнивается сумма имеющихся в двух массивах элементов и текущий элемент добавляется в тот массив, в котором сумма меньшая. Таким способом достигается минимальная разница между суммами.
     
  10. IrineK

    IrineK Гость

    Реализация отличной идеи dreamer для любого N:

    Код (C++):
    #include <iostream>
    using namespace std;

    int lot[100],bag1[99],bag2[99];
    int i;

    void create_lot(int dim)
    {
    for(i=0;i<dim;i++)
    {cout<<(i+1)<<": ";
    cin>>lot[i];}
    }

    void arrange_lot(int dim)
    {
    int j,cur;
    for(i=0;i<dim-1;i++)
    for(j=i+1;j<dim;j++)
    if(lot[i]<lot[j])
    {   cur=lot[i];
    lot[i]=lot[j];
    lot[j]=cur; }
    }

    void arrange_bags(int dim)
    {
    int sum1=0, sum2=0, k1=0, k2=0;
    for(i=0;i<dim;i++)
    {
    if(sum1<=sum2)
    {   bag1[k1]=lot[i];
    sum1+=lot[i];
    k1++;}
    else
    {   bag2[k2]=lot[i];
    sum2+=lot[i];
    k2++;}
    }
    cout<<"\nBag1: ";
    for(i=0;i<k1;i++)
    cout<<bag1[i]<<" ";
    cout<<"\nSum1: "<<sum1<<endl;
    cout<<"\nBag2: ";
    for(i=0;i<k2;i++)
    cout<<bag2[i]<<" ";
    cout<<"\nSum2: "<<sum2<<endl;
    }

    void main()
    {
    int n;
    cout<<"Total number of items is: ";
    cin>>n;
    create_lot(n);
    arrange_lot(n);
    arrange_bags(n);
    }
    Более того, данная идея позволяет формировать любое к-во рюкзаков M<=N. Возьму на вооружение. Спасибо.
     
Загрузка...

Поделиться этой страницей