getOptimalPurchasePlan.php

<?php

function getOptimalPurchasePlan(array $priceList, int $need): array {
	if ($need <= 0) {
		return [];
	}

	usort($priceList, fn($a, $b) => ($a['price'] / $a['pack']) <=> ($b['price'] / $b['pack']));

	$dp = array_fill(0, $need + 1, PHP_INT_MAX);
	$dp[0] = 0;

	$trace = [];

	foreach ($priceList as $offer) {
		$id = $offer['id'];
		$price = $offer['price'];
		$pack = $offer['pack'];
		$count = $offer['count'];

		for ($i = $need; $i >= 0; $i--) {
			$maxQty = min($count, (int)(($need - $i) / $pack)) * $pack;

			for ($qty = $pack; $qty <= $maxQty; $qty += $pack) {
				$newCost = $dp[$i] + $price * $qty;

				if ($newCost < $dp[$i + $qty]) {
					$dp[$i + $qty] = $newCost;
					$trace[$i + $qty] = ['id' => $id, 'qty' => $qty];
				}
			}
		}
	}

	if ($dp[$need] === PHP_INT_MAX) {
		return [];
	}

	$plan = [];
	$remaining = $need;

	while ($remaining > 0 && isset($trace[$remaining])) {
		$item = $trace[$remaining];
		$plan[] = $item;
		$remaining -= $item['qty'];
	}

	return $plan;
}

function generateInputData(int $maxRows = 1000, int $maxN = 10000, int $maxPack = 500, int $maxPackVariants = 20): array {
	$packVariants = [];
	while (count($packVariants) < $maxPackVariants) {
		$packVariants[] = rand(1, $maxPack);
		$packVariants = array_unique($packVariants);
	}

	$priceList = [];
	for ($i = 1; $i <= $maxRows; $i++) {
		$pack = $packVariants[array_rand($packVariants)];
		$count = rand($pack, 5000) * $pack;
		$price = rand(1, 2000) / 100;

		$priceList[] = [
			'id' => $i,
			'count' => $count,
			'price' => $price,
			'pack' => $pack,
		];
	}


	$totalAvailable = array_sum(array_column($priceList, 'count'));
	$N = rand(1, min($totalAvailable, $maxN));

	return ['priceList' => $priceList, 'N' => $N];
}

$data = generateInputData();

$need = $data['N'];
$priceList = $data['priceList'];

$result = getOptimalPurchasePlan($priceList, $need);

echo '<pre>';
print_r($result);
echo '</pre>';
echo 'Потребность: ' . $need . '<br>';
echo 'Кол. строк в прайс-листе: ' . count($priceList);