|
int knapsack2(const std::vector<int>& wts, const std::vector<int>& cost, int W)
{
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];
}
</syntaxhighlight>
[[Java]]
<syntaxhighlight lang="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];
}
</syntaxhighlight>
[[Javascript]]
<syntaxhighlight lang="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];
}
</syntaxhighlight>
[[C_Sharp|C#]]
<syntaxhighlight lang="csharp">
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];
}
</syntaxhighlight>
[[w:Free Pascal|Free Pascal]]
<syntaxhighlight lang="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;
</syntaxhighlight>
[[PHP]]
<syntaxhighlight lang="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];
}
?>
</syntaxhighlight>
{{BookCat | filing = deep}}
| 