Knapsack : Knapsack
Given weights w[] and values v[] of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. O(nW) 1) dp[y] - maximum total value for capacity y 2) dp[y] = max(dp[y - d[y - w[i]]] + v[i] for i in range(n)) 3) dp[W] - maximum total value for capacity W
Knapsack 1/0 [restricts the number of copies of each kind of item to zero or one]
// -----------------------------------------------------------------------------
// Knapsack C++
// -----------------------------------------------------------------------------
int knapsack(std::vector<int> &v, std::vector<int> &w, int W)
{
int n = v.size();
std::vector<int> dp(W + 1);
for (int i = 0; i < n; i++)
for (int j = W; j >= 0; j--)
dp[j] = j < w[i] ? dp[j] : std::max(dp[j], dp[j - w[i]] + v[i]);
return dp[W];
}
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// Knapsack C#
// -----------------------------------------------------------------------------
static int knapsack(int[] v, int[] w, int W)
{
int n = v.Length;
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++)
for (int j = W; j >= 0; j--)
dp[j] = j < w[i] ? dp[j] : Math.Max(dp[j], dp[j - w[i]] + v[i]);
return dp[W];
}
// -----------------------------------------------------------------------------
# ------------------------------------------------------------------------------
# Knapsack Python
# ------------------------------------------------------------------------------
def knapsack(v, w, W):
n = len(v)
dp = [0 for i in range(W + 1)]
for i in range(n):
for j in range(W, -1, -1):
if w[i] <= j:
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
return dp[W]
# ------------------------------------------------------------------------------
Unbounded [no upper bound on the number of copies of each kind of item]
// -----------------------------------------------------------------------------
// Knapsack C++
// -----------------------------------------------------------------------------
int knapsack(std::vector<int> &v, std::vector<int> &w, int W)
{
int n = v.size();
std::vector<int> dp(W + 1);
for (int i = 0; i < n; i++)
for (int j = w[i]; j <= W; j++)
dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
return dp[W];
}
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// Knapsack C#
// -----------------------------------------------------------------------------
static int knapsack(int[] v, int[] w, int W)
{
int n = v.Length;
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++)
for (int j = w[i]; j <= W; j++)
dp[j] = Math.Max(dp[j], dp[j - w[i]] + v[i]);
return dp[W];
}
// -----------------------------------------------------------------------------
# ------------------------------------------------------------------------------
# Knapsack Python
# ------------------------------------------------------------------------------
def knapsack(v, w, W):
n = len(v)
dp = [0 for i in range(W + 1)]
for i in range(n):
for j in range(w[i], W + 1):
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
return dp[W]
# ------------------------------------------------------------------------------