GetAnswer.cs

CSharp · Console

/Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
/*					
 * Диверсификация портфеля
 * У вас есть портфель ценных бумаг: A1, A2, A3,..., An. Необходимо диферсифицировать его на два отдельных портфеля, 
 * но так, чтобы разница в стоимости этих портфелей была минимальной.
 * Входные данные: Shares[] - массив ценых бумаг, где Shares[i] - цена i-й акции. Размер массива от 1 до 20, цена любой акции от 1 до 10^3
 * Вывод: FirstShares[], SecondShares[] - массивы с ценами бумаг для 1го и 2го портфеля соот-но, а также стоимость каждого из портфелей.
 * Пример: Shares = [1, 2, 3, 3]
 * Answer: 
 * FirstShares = [1, 3], FirstTotalValue = 4; 
 * SecondShares = [2, 3], SecondTotalValue = 5
 */
public class Program
{
	private class Portfolio
	{
		public int Cost;
		public List<int> Shares;
	}
	static Portfolio GetPortfolioValue(int k, int[] originalShares)
	{
		int cost = 0;
		List<int> shares = new List<int>();
		
		// Для k-го распределения бумаг в портфеле берем только те бумаги, для ктр соот-й бит не равен 0.
		// Например, для k = 3 -> 0011 (3 в двоичном представлении): 1й и 2й бит не равны нулю,
		// значит для этого распределения берем 1ю и 2ю бумагу.
		for (int i = 0; i < originalShares.Length; i++)
		{
			int bit = (k >> i) & 1; // получаем текущий i-й бит числа k
			if (bit != 0)
			{
				cost += originalShares[i];
				shares.Add(originalShares[i]);
			}
		}
		return new Portfolio { Cost = cost, Shares = shares };
	}

	static void Diversification(int[] shares)
	{
		// считаем полную стоимость исходного портфеля
		int totalCost = 0;
		int numberOfShares = shares.Length;
		for (int i = 0; i < numberOfShares; i++)
		{
			totalCost += shares[i];
		}

		List<int> firstShares = new List<int>();
		List<int> secondShares = new List<int>();
		int portfolioCostDiff = int.MaxValue;
		int firstPortfolioCost = 0, tempPortfolioCost = 0;

		// от 1 до (2^N - 1)
		// 2^N можно представить через битовое выражение: (1 << N)
		for (int i = 1; i < (1 << numberOfShares) - 1; i++)
		{
			// берем i-е распределение первого портфеля
			Portfolio portfolio = GetPortfolioValue(i, shares);
			tempPortfolioCost = portfolio.Cost;

			// ищем наименьшую разницу в стоимости портфелей
			int diff = Math.Abs(totalCost - 2 * tempPortfolioCost);
			if (diff < portfolioCostDiff)
			{
				portfolioCostDiff = diff;
				firstPortfolioCost = tempPortfolioCost;
				firstShares = portfolio.Shares;
			}
		}

		// Получаем второй портфель простым вычитанием
		secondShares = shares.ToList();
		foreach (var share in firstShares)
		{
			secondShares.Remove(share);
		}
		Console.WriteLine(string.Format("Cost diff of portfolio = {0}", portfolioCostDiff != int.MaxValue ? portfolioCostDiff : shares.FirstOrDefault()));
		Console.WriteLine(string.Format("First Portfolio (Cost: {0}) = [{1}]", firstPortfolioCost,  string.Join(", ", firstShares)));
		Console.WriteLine(string.Format("Second Portfolio (Cost: {0}) = [{1}]\n", totalCost - firstPortfolioCost,  string.Join(", ", secondShares)));
	}

	public static void Main()
	{
		Console.WriteLine("UniLecs");
		
		int[] shares = new int[] { 1 }; // 1
		Diversification(shares);
		
		shares = new int[] { 1, 2, 3, 3 }; // 1
		Diversification(shares);		
		
		shares = new int[] {  27, 14, 5, 8, 13 }; // 3
		Diversification(shares);
		
		shares = new int[] { 6, 7, 9, 13, 18, 24, 31, 50 }; // 0
		Diversification(shares);
		
		shares = new int[] { 5, 5, 4, 3, 3 }; // 0
		Diversification(shares);
		
		shares = new int[] { 1, 4, 5, 6, 7, 9 }; // 0
		Diversification(shares);
		
		shares = new int[] { 1, 2, 3, 4, 100, 100 }; // 0
		Diversification(shares);	
		
		shares = new int[] { 5, 8, 13, 14, 15 }; // 1
		Diversification(shares);
		
		shares = new int[] { 7, 5, 8, 10, 9 }; // 1
		Diversification(shares);
		
		shares = new int[] { 1, 2, 3, 4, 5, 6, 6 }; // 1
		Diversification(shares);
		
		shares = new int[] { 1, 4, 5, 6, 7, 9 }; // 0
		Diversification(shares);
		
		shares = new int[] { 1, 8, 13, 27, 14 }; // 7
		Diversification(shares);
		
		shares = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }; // 0
		Diversification(shares);
	}
}
;