面接問題14:ロープを切る(ダイナミックプランニング+貪欲アルゴリズム)C++

一、動的計画:動的計画を応用する前に、この問題が大問題を小問題に分解できるかどうかを分析する.

#include

class max_ProductCutting_solution
{
	int* products;
	int product;
	int m_max;
public:
	int c_max_ProductCutting_solution(int length);
	~max_ProductCutting_solution() { delete[] products; }
};
int max_ProductCutting_solution::c_max_ProductCutting_solution(int length)
{
	if (length < 2)return 0;
	if (length == 2)return 1;
	if (length == 3)return 2;
	products = new int[length + 1];
	products[0] = 0;
	products[1] = 1;
	products[2] = 2;
	products[3] = 3;
	for (int i = 4;i <= length;++i)
	{
		m_max = 0;
		for (int j = 1;j <= i / 2;++j)
		{
			product = products[j] * products[i - j];
			if (m_max < product)
			{
				m_max = product;
				products[i] = m_max;
			}
		}
	}
	return products[length];
}
int main(int argc, char* argv[])
{
	max_ProductCutting_solution B;
	std::cout << B.c_max_ProductCutting_solution(8) << std::endl;
	std::cin.get();
	return 0;
}

2、欲張りアルゴリズム欲張りアルゴリズムを用いるには一定の数学的モデリング能力を備える必要があるロープを切る欲張りアルゴリズムでは、3(n-3)>n,2(n-2)>nによれば、ロープを3または2に切るときが最良であることに注意しなければならないのは、ロープの長さ/3の残数が0,1,2であるとき、2の切り方によって残りを切り、0のときに切ったばかりであるが、余剰が1の場合は、カットが1回多くなったことを示すので、timeOf–は、マルチカットの1段と1を2の倍数に構成すればよい

#include
class max_ProductCutting_solution
{
public:
	int c_max_ProductCutting_solution(int length);
};

int max_ProductCutting_solution::c_max_ProductCutting_solution(int length)
{
	if (length < 2)return 0;
	if (length == 2)return 1;
	if (length == 3)return 2;
	int timesOf3 = length / 3;
	if (length - timesOf3 * 3 == 1)
		timesOf3 -= 1;
	int timeOf2 = (length - timesOf3 * 3) / 2;
	return (int)pow(3, timesOf3) * (int)(pow(2, timeOf2));
}

int main(int argc, char* argv[])
{
	max_ProductCutting_solution B;
	std::cout << B.c_max_ProductCutting_solution(10) << std::endl;
	std::cin.get();
	return 0;
}