CSharp · Console
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);
}
}