プログラミングの美2.18配列分割

テーマ:無秩序で、要素の個数が2 nの正の整数の配列があって、どのようにこの配列を要素の個数がnの2つの配列に分割することができて、そして2つのサブ配列の和を最も接近させます.
 
動的計画法を用いてこの問題を解き,配列とsumの半分に最も近いn個のデータの数列を探す.
sum/2未満の配列を探します.
配列isOk[sum/2]、  isOk[i]は、シーケンスが存在するか否かの和がiであることを示す
配列vv_の割り当てdata[sum/2], vv_Data[i]はシーケンスとiのシーケンスの長さを表し、長さは値ではない可能性があるためvv_data[i]は配列です
 
各数ごとにisOk,vv_を更新dataの値は、最後にsum/2未満のシーケンス長nの最大値を検索する.
 

#include <iostream>
#include <vector>
#include <set>

using namespace std;

class DynamicHalfApproach
{
public:
	DynamicHalfApproach(vector<int> &data)
	{
		m_vData = data;
	}
	
	int getHalfApproach()
	{
		int sum = 0;
		for (vector<int>::iterator iter = m_vData.begin(); iter != m_vData.end(); ++iter)
		{
			sum += *iter;
		}

		int half = sum / 2;
		
		cout << "half = " << half << endl;

		vector<bool> isOk;
		isOk.push_back(true);
		for(int i = 1; i <= half; ++i)
		{
			isOk.push_back(false);
		}
		
		vector< set<int> > vv_data;
		set<int> iset;
		iset.insert(0);
		vv_data.push_back(iset);
		for (int i = 1; i <= half; ++i)
		{
			set<int> iset;
			vv_data.push_back(iset);
		}

		for (int j = 0; j < m_vData.size(); j++)
		{
			for(int i = half; i>= 0; --i)
			{
				if(isOk[i] && (m_vData[j] + i <= half))
				{
					isOk[m_vData[j] + i] = true;
					set<int> &iset = vv_data[i];
					for(set<int>::iterator iter = iset.begin(); iter != iset.end(); ++iter)
					{
						vv_data[m_vData[j] + i].insert(*iter + 1);
					}
				}
			}
		}

		for (int i = 1; i <= half; ++i)
		{
			cout << "*******************************" << endl;
			cout << "i = " << i << endl;
			set<int> &iset = vv_data[i];
			for(set<int>::iterator iter = iset.begin(); iter != iset.end(); ++iter)
			{
				cout << *iter << " ";
			}
			cout << endl;
			cout << "*******************************" << endl;
		}

		for (int i = half; i >= 0; --i)
		{
			if (isOk[i])
			{
				set<int> &iset = vv_data[i];
				for(set<int>::iterator iter = iset.begin(); iter != iset.end(); ++iter)
				{
					if (*iter == m_vData.size() / 2)
						return i;
				}
			}
		}

		return -1;
	}
private:
	vector<int> m_vData;
};

int main(void)
{
	vector<int> ivect;

	ivect.push_back(1);
	ivect.push_back(5);
	ivect.push_back(7);
	ivect.push_back(8);
	ivect.push_back(9);
	ivect.push_back(6);
	ivect.push_back(3);
	ivect.push_back(11);
	ivect.push_back(20);
	ivect.push_back(17);

	DynamicHalfApproach helper(ivect);

	cout << helper.getHalfApproach() << endl;

	system("pause");

	return 0;
}