Разделение предметов по весу

[Viperous]

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

[Syuf]

Я бы сделал так:
1. Если бы не знал задачу о рюкзаке, то ознакомился бы с ней.
2. Начиная с N, до N/2, вызывал бы задачу, указанную выше, сохраняя нужные данные (номера предметов, например), каждый раз для (предыдущего ответа-1), и выбрал бы лучший (самый близкий к N/2).

[niki123]

Всем доброго вечера спасибо что откликнулись.

Вы всё правильно поняли. Почему не будет?

Если взять три предмета массами: 1000, 6 и допустим 2 то вполне логично предположить что «чтобы общие веса групп были максимально близки» в 1 ой группе будет 1000 во второй 8.

niki123, задачу эту для чего решаете? (цель какую пытаетесь достигнуть, какой результат получить? )

Вопрос скорее философский )))) обычная лаб. работа.

N какой максимальной величины может быть?

В условии задачи для N не указан диапазон так что скорее всего N->бесконечности.
По поводу условия задачи я так понимаю, что нужно найти такое распределение весов чтобы их разность была минимальной то есть при любом другом распределении разность будет либо равна найденной или больше найденной (если ошибаюсь поправьте).

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

Мне кажется это вполне может получиться прибавлять к меньшей группе элементы ДО ТЕХ ПОР пока она меньше другой группы и затем обратно (в отсортированном массиве).
Попробую реализовать.

[niki123]

Задача в принципе оказалось довольно простой (если конечно я ее правильно решил)
Может быть кому нибудь понадобиться.

#include "stdafx.h"
#include "iostream"; 
using namespace std; 
int _tmain(int argc, _TCHAR* argv[])
{
	int n, r, k=0, l=0;
	float v1, v2;
	cout<<"VVedite razmer massiva\n";
	cin>>n;
	float *mass=new float [n];
	float *mass1=new float [n];
	float *mass2=new float [n];
	cout<<"VVedite element massiva\n";
	for (int i=0; i<n; i++)
	{
		cin>>mass[i];
		cout<<"\n";
	}

	for (int i=0; i<n-1; i++)
	{
		for (int j=0; j<n-1; j++)
		{
			if (mass[j]<mass[j+1])
			{
				int s=mass[j];
				mass[j]=mass[j+1];
				mass[j+1]=s;
			}
		}
	}
	
	v1=mass[0];
	v2=mass[1];
	
	for (int i=2; i<n; i++)
	{
		if(v1<v2)
		{
			v1+=mass[i];
			mass1[k]=mass[i];
			k++;
		}
		else
		{
			v2+=mass[i];
			mass2[l]=mass[i];
			l++;
		}
	}
	cout<<"Vvodnii massiv";
	for (int i=0; i<n; i++)
	{
		cout<<mass[i]<<"\t";
	}
	cout<<"\n"<<"1 massiv";
	cout<<"\n"<<v1<<"\n";
	cout<<mass[0]<<"\t";
	for (int i=0; i<k; i++)
	{
		cout<<mass1[i]<<"\t";
	}
	cout<<"\n"<<"2 massiv";
	cout<<"\n"<<v2<<"\n";
	cout<<mass[1]<<"\t";
	for (int i=0; i<l; i++)
	{
		cout<<mass2[i]<<"\t";
	}
	cin>>r;
	return 0;
}