Реализации алгоритмов/Комбинаторика/Задача о ранце

Реализация

C++

#include <vector>
#include <limits>

//wts - массив весов, cost - массив стоимостей предметов, W - вместимость рюкзака
//функция возвращает максимальную стоимость, которую можно набрать(решение задачи о рюкзаке
//с повторениями)
//массив dp собственно реализует динамическое программирование, описанное в статье, как K_w
int knapsack1(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
	size_t n = wts.size();
	std::vector<int> dp(W + 1);
	dp[0] = 0;
	for (int w = 1; w <= W; w++)
	{
		dp[w] = dp[w-1];
		for (size_t i = 0; i < n; i++)
		{
			if (wts[i] <= w)
			{
				dp[w] = std::max(dp[w], dp[w - wts[i]] + cost[i]);
			}
		}
	}
	return dp[W];
}

Задача о ранце с возможностью единичного выбора предмета

Решение

Обозначим через $K_{w,i}$ максимальную стоимость, которую мы можем набрать при весе не более $w$ среди $i$ первых предметов. Получаем следующее рекуррентное соотношение:

• $K_{0,i}=0,\quad 0\leq i\leq n$
• $K_{w,0}=0,\quad 0\leq w\leq W$
• $K_{w,i}={\begin{cases}\max {\left(K_{w,i-1},K_{w-w_{i},i-1}+v_{i}\right)},\quad w_{i}\leq w\\K_{w,i-1},\quad w_{i}>w\end{cases}},0\leq w\leq W$

Реализация

C++

#include <vector>
#include <limits>

int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
    size_t n = wts.size();
    std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n+1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (wts[j-1] <= w)
            {
                dp[w][j] = std::max(dp[w][j - 1], dp[w - wts[j-1]][j - 1] + cost[j-1]);
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[W][n];
}

Java

int knapsack(int weights[], int costs[], int needed) {
    int n = weights.length;
    int dp[][] = new int[needed + 1][n + 1];
    for (int j = 1; j <= n; j++) {
        for (int w = 1; w <= needed; w++) {
            if (weights[j-1] <= w) {
                dp[w][j] = Math.max(dp[w][j - 1], dp[w - weights[j-1]][j - 1] + costs[j-1]);
            } else {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[needed][n];
}

Javascript

/**
 * @param {Array.<Number>} scores Стоимости предметов
 * @param {Array.<Number>} weights Веса предметов
 * @param {Number} capacity Грузоподъемность
 * @return {Number} Максимальная стоимость предметов, вмещающихся в рюкзак
 */
function packBagpack(scores, weights, capacity) {
  let n = weights.length;
  let dp = new Array(capacity + 1);

  for (let i = 0; i <= capacity; i += 1) {
    dp[i] = new Array(n + 1).fill(0);
  }

  for (let i = 1; i <= n; i += 1) {
    for (let j = 1; j <= capacity; j += 1) {
      if (weights[i - 1] <= j) {
        dp[j][i] = Math.max(dp[j][i - 1], dp[j - weights[i - 1]][i - 1] + scores[i-1]);  
      } else {
        dp[j][i] = dp[j][i - 1];
      }

    }
  }

  return dp[capacity][n];
}

C#

int knapsack(int[] weights, int[] costs, int needed)
{
    int n = weights.Length;
    int[,] dp = new int[needed + 1, n + 1];
    for (int j = 1; j <= n; j++)
    {
        for (int w = 1; w <= needed; w++)
        {
            if (weights[j - 1] <= w)
            {
                dp[w, j] = Math.Max(dp[w, j - 1], dp[w - weights[j - 1], j - 1] + costs[j - 1]);
            }
            else
            {
                dp[w, j] = dp[w, j - 1];
            }
        }
     }
     return dp[needed, n];
}

Free Pascal

procedure rec(k,w,st:longint);
var i:longint;
begin
  for i:=1 to n do
    if b[i] and(w>=weight[i]) then
      begin
        b[i]:=false;
        now[k]:=i;
        rec(k+1,w-weight[i],st+price[i]);
        b[i]:=true;
      end
    else
      begin
        if (st>maxprice) then
          begin
            best:=now;
            maxprice:=st;
          end;
      end;
end;

PHP

<?php
/**
 * @param array $weights
 * @param array $costs
 * @param int $needed 
 */
function knapsack($weights, $costs, $needed) {
      $n = count($weights);
      $dp = array();

      for ($j = 1; $j <= $n; $j++)
            for ($w = 1; $w <= $needed; $w++)
                  $dp[$w][$j] =
                        $weights[$j - 1] <= $w ?
                              max(array($dp[$w][$j - 1], $dp[$w - $weights[$j - 1]][$j - 1] + $costs[$j - 1])) :
                              $dp[$w][$j - 1];

      return $dp[$needed][$n];
}
?>