题目
已知N个物品的重量和利润，我们将这些物品放入容量为C的背包。目标是背包中的物品中获得最大的利润。每个物品只能选择一次。
示例：
物品：物品1、物品2、物品3、物品4
单个物品重量：2、3、1、4
单个物品盈利：4、5、3、7
背包容量：5
解法
暴力解法
Java
class Knapsack {
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
return this.knapsackRecursive(profits, weights, capacity, 0);
}
//currentIndex是用于确定当前遍历到的元素的索引
private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
//基准检查
if (capacity <= 0 || currentIndex >= profits.length)
return 0;
//选择当前物品后递归调用
//如果当前物品的重量超过容量，则不继续递归调用
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
capacity - weights[currentIndex], currentIndex + 1);
//排除当前索引的物品后递归调用
int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);
return Math.max(profit1, profit2);
}
public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {1, 6, 10, 16};
int[] weights = {1, 2, 3, 5};
int maxProfit = ks.solveKnapsack(profits, weights, 7);
System.out.println("Total knapsack profit ---> " + maxProfit);
maxProfit = ks.solveKnapsack(profits, weights, 6);
System.out.println("Total knapsack profit ---> " + maxProfit);
}
}JavaScript
class Knapsack {
solveKnapsack(profits, weights, capacity) {
return this.knapsackRecursive(profits, weights, capacity, 0);
}
knapsackRecursive(profits, weights, capacity, currentIndex) {
if (capacity <= 0 || currentIndex >= profits.length) {
return 0;
}
let profit1 = 0;
if (weights[currentIndex] <= capacity) {
profit1 =
profits[currentIndex] +
this.knapsackRecursive(
profits,
weights,
capacity - weights[currentIndex],
currentIndex + 1
);
}
let profit2 = this.knapsackRecursive(
profits,
weights,
capacity,
currentIndex + 1
);
return Math.max(profit1, profit2);
}
}
const ks = new Knapsack();
const profits = [1, 6, 10, 16];
const weights = [1, 2, 3, 5];
let maxProfit = ks.solveKnapsack(profits, weights, 7);
console.log("Total knapsack profit ---> " + maxProfit);
maxProfit = ks.solveKnapsack(profits, weights, 6);
console.log("Total knapsack profit ---> " + maxProfit);Python
class Knapsack:
def solveKnapsack(self, profits, weights, capacity):
return self.knapsackRecursive(profits, weights, capacity, 0)
def knapsackRecursive(self, profits, weights, capacity, currentIndex):
if capacity <= 0 or currentIndex >= len(profits):
return 0
profit1 = 0
if weights[currentIndex] <= capacity:
profit1 = (
profits[currentIndex]
+ self.knapsackRecursive(
profits,
weights,
capacity - weights[currentIndex],
currentIndex + 1,
)
)
profit2 = self.knapsackRecursive(profits, weights, capacity, currentIndex + 1)
return max(profit1, profit2)
ks = Knapsack()
profits = [1, 6, 10, 16]
weights = [1, 2, 3, 5]
maxProfit = ks.solveKnapsack(profits, weights, 7)
print("Total knapsack profit --->", maxProfit)
maxProfit = ks.solveKnapsack(profits, weights, 6)
print("Total knapsack profit --->", maxProfit)Go
package main
import (
"fmt"
)
type Knapsack struct{}
func (ks Knapsack) solveKnapsack(profits []int, weights []int, capacity int) int {
return ks.knapsackRecursive(profits, weights, capacity, 0)
}
func (ks Knapsack) knapsackRecursive(profits []int, weights []int, capacity int, currentIndex int) int {
if capacity <= 0 || currentIndex >= len(profits) {
return 0
}
profit1 := 0
if weights[currentIndex] <= capacity {
profit1 = profits[currentIndex] + ks.knapsackRecursive(profits, weights, capacity-weights[currentIndex], currentIndex+1)
}
profit2 := ks.knapsackRecursive(profits, weights, capacity, currentIndex+1)
if profit1 > profit2 {
return profit1
}
return profit2
}
func main() {
ks := Knapsack{}
profits := []int{1, 6, 10, 16}
weights := []int{1, 2, 3, 5}
maxProfit := ks.solveKnapsack(profits, weights, 7)
fmt.Println("Total knapsack profit --->", maxProfit)
maxProfit = ks.solveKnapsack(profits, weights, 6)
fmt.Println("Total knapsack profit --->", maxProfit)
}自顶向下(备忘录)解法
Java
class Knapsack {
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
Integer[][] dp = new Integer[profits.length][capacity + 1];
return this.knapsackRecursive(dp, profits, weights, capacity, 0);
}
private int knapsackRecursive(Integer[][] dp, int[] profits, int[] weights, int capacity,
int currentIndex) {
//基础检查
if (capacity <= 0 || currentIndex >= profits.length)
return 0;
// 如果我们已经解决过相似的问题，那么直接从dp二维表中返回相似的结果
if(dp[currentIndex][capacity] != null)
return dp[currentIndex][capacity];
//选择当前物品后递归调用
//如果当前物品的重量超过容量，则不继续递归调用
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights,
capacity - weights[currentIndex], currentIndex + 1);
// 排除当前索引指向的物品后递归调用
int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);
//返回结果之前，先将结果存到dp二维表中
dp[currentIndex][capacity] = Math.max(profit1, profit2);
return dp[currentIndex][capacity];
}
public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {1, 6, 10, 16};
int[] weights = {1, 2, 3, 5};
int maxProfit = ks.solveKnapsack(profits, weights, 7);
System.out.println("Total knapsack profit ---> " + maxProfit);
maxProfit = ks.solveKnapsack(profits, weights, 6);
System.out.println("Total knapsack profit ---> " + maxProfit);
}
}JavaScript
class Knapsack {
solveKnapsack(profits, weights, capacity) {
const dp = new Array(profits.length);
for (let i = 0; i < profits.length; i++) {
dp[i] = new Array(capacity + 1).fill(null);
}
return this.knapsackRecursive(dp, profits, weights, capacity, 0);
}
knapsackRecursive(dp, profits, weights, capacity, currentIndex) {
if (capacity <= 0 || currentIndex >= profits.length) return 0;
if (dp[currentIndex][capacity] !== null) return dp[currentIndex][capacity];
let profit1 = 0;
if (weights[currentIndex] <= capacity) {
profit1 =
profits[currentIndex] +
this.knapsackRecursive(
dp,
profits,
weights,
capacity - weights[currentIndex],
currentIndex + 1
);
}
const profit2 = this.knapsackRecursive(
dp,
profits,
weights,
capacity,
currentIndex + 1
);
dp[currentIndex][capacity] = Math.max(profit1, profit2);
return dp[currentIndex][capacity];
}
static main() {
const ks = new Knapsack();
const profits = [1, 6, 10, 16];
const weights = [1, 2, 3, 5];
let maxProfit = ks.solveKnapsack(profits, weights, 7);
console.log("Total knapsack profit ---> " + maxProfit);
maxProfit = ks.solveKnapsack(profits, weights, 6);
console.log("Total knapsack profit ---> " + maxProfit);
}
}
Knapsack.main();Python
class Knapsack:
def solveKnapsack(self, profits, weights, capacity):
dp = [[None] * (capacity + 1) for _ in range(len(profits))]
return self.knapsackRecursive(dp, profits, weights, capacity, 0)
def knapsackRecursive(self, dp, profits, weights, capacity, currentIndex):
if capacity <= 0 or currentIndex >= len(profits):
return 0
if dp[currentIndex][capacity] is not None:
return dp[currentIndex][capacity]
profit1 = 0
if weights[currentIndex] <= capacity:
profit1 = profits[currentIndex] + self.knapsackRecursive(
dp,
profits,
weights,
capacity - weights[currentIndex],
currentIndex + 1
)
profit2 = self.knapsackRecursive(
dp,
profits,
weights,
capacity,
currentIndex + 1
)
dp[currentIndex][capacity] = max(profit1, profit2)
return dp[currentIndex][capacity]
ks = Knapsack()
profits = [1, 6, 10, 16]
weights = [1, 2, 3, 5]
maxProfit = ks.solveKnapsack(profits, weights, 7)
print("Total knapsack profit --->", maxProfit)
maxProfit = ks.solveKnapsack(profits, weights, 6)
print("Total knapsack profit --->", maxProfit)Go
package main
import (
"fmt"
)
type Knapsack struct{}
func (ks *Knapsack) SolveKnapsack(profits []int, weights []int, capacity int) int {
dp := make([][]int, len(profits))
for i := 0; i < len(profits); i++ {
dp[i] = make([]int, capacity+1)
}
return ks.knapsackRecursive(dp, profits, weights, capacity, 0)
}
func (ks *Knapsack) knapsackRecursive(dp [][]int, profits []int, weights []int, capacity int, currentIndex int) int {
if capacity <= 0 || currentIndex >= len(profits) {
return 0
}
if dp[currentIndex][capacity] != 0 {
return dp[currentIndex][capacity]
}
profit1 := 0
if weights[currentIndex] <= capacity {
profit1 = profits[currentIndex] + ks.knapsackRecursive(
dp,
profits,
weights,
capacity-weights[currentIndex],
currentIndex+1,
)
}
profit2 := ks.knapsackRecursive(
dp,
profits,
weights,
capacity,
currentIndex+1,
)
dp[currentIndex][capacity] = max(profit1, profit2)
return dp[currentIndex][capacity]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
ks := Knapsack{}
profits := []int{1, 6, 10, 16}
weights := []int{1, 2, 3, 5}
maxProfit := ks.SolveKnapsack(profits, weights, 7)
fmt.Println("Total knapsack profit --->", maxProfit)
maxProfit = ks.SolveKnapsack(profits, weights, 6)
fmt.Println("Total knapsack profit --->", maxProfit)
}自底向上
Java
class Knapsack {
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
// 基准检查
if (capacity <= 0 || profits.length == 0 || weights.length != profits.length)
return 0;
int n = profits.length;
int[][] dp = new int[n][capacity + 1];
// 填充capacity=0的那列，0容量0利润
for(int i=0; i < n; i++)
dp[i][0] = 0;
// 如果我们只有一个重量，如果它不超过承载量，我们就接受它
for(int c=0; c <= capacity; c++) {
if(weights[0] <= c)
dp[0][c] = profits[0];
}
// 为所有容量处理所有子数组
for(int i=1; i < n; i++) {
for(int c=1; c <= capacity; c++) {
int profit1= 0, profit2 = 0;
// 如果当前元素的重量不超过容量，包含当前元素
if(weights[i] <= c)
profit1 = profits[i] + dp[i-1][c-weights[i]];
// 不包含当前项
profit2 = dp[i-1][c];
// 取profit1和profit2中的最大值
dp[i][c] = Math.max(profit1, profit2);
}
}
//右下角为最大的利润
return dp[n-1][capacity];
}
public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {1, 6, 10, 16};
int[] weights = {1, 2, 3, 5};
int maxProfit = ks.solveKnapsack(profits, weights, 7);
System.out.println("Total knapsack profit ---> " + maxProfit);
maxProfit = ks.solveKnapsack(profits, weights, 6);
System.out.println("Total knapsack profit ---> " + maxProfit);
}
}JavaScript
class Knapsack {
solveKnapsack(profits, weights, capacity) {
// 基准检查
if (capacity <= 0 || profits.length === 0 || weights.length !== profits.length)
return 0;
const n = profits.length;
const dp = new Array(n).fill(0).map(() => new Array(capacity + 1).fill(0));
// 填充capacity=0的那列，0容量0利润
for (let i = 0; i < n; i++)
dp[i][0] = 0;
// 如果我们只有一个重量，如果它不超过承载量，我们就接受它
for (let c = 0; c <= capacity; c++) {
if (weights[0] <= c)
dp[0][c] = profits[0];
}
// 为所有容量处理所有子数组
for (let i = 1; i < n; i++) {
for (let c = 1; c <= capacity; c++) {
let profit1 = 0, profit2 = 0;
// 如果当前元素的重量不超过容量，包含当前元素
if (weights[i] <= c)
profit1 = profits[i] + dp[i - 1][c - weights[i]];
// 不包含当前项
profit2 = dp[i - 1][c];
// 取profit1和profit2中的最大值
dp[i][c] = Math.max(profit1, profit2);
}
}
// 右下角为最大的利润
return dp[n - 1][capacity];
}
}
const ks = new Knapsack();
const profits = [1, 6, 10, 16];
const weights = [1, 2, 3, 5];
let maxProfit = ks.solveKnapsack(profits, weights, 7);
console.log("Total knapsack profit ---> " + maxProfit);
maxProfit = ks.solveKnapsack(profits, weights, 6);
console.log("Total knapsack profit ---> " + maxProfit);Python
class Knapsack:
def solveKnapsack(self, profits, weights, capacity):
# 基准检查
if capacity <= 0 or len(profits) == 0 or len(weights) != len(profits):
return 0
n = len(profits)
dp = [[0] * (capacity + 1) for _ in range(n)]
# 填充capacity=0的那列，0容量0利润
for i in range(n):
dp[i][0] = 0
# 如果我们只有一个重量，如果它不超过承载量，我们就接受它
for c in range(capacity + 1):
if weights[0] <= c:
dp[0][c] = profits[0]
# 为所有容量处理所有子数组
for i in range(1, n):
for c in range(1, capacity + 1):
profit1, profit2 = 0, 0
# 如果当前元素的重量不超过容量，包含当前元素
if weights[i] <= c:
profit1 = profits[i] + dp[i - 1][c - weights[i]]
# 不包含当前项
profit2 = dp[i - 1][c]
# 取profit1和profit2中的最大值
dp[i][c] = max(profit1, profit2)
# 右下角为最大的利润
return dp[n - 1][capacity]
ks = Knapsack()
profits = [1, 6, 10, 16]
weights = [1, 2, 3, 5]
max_profit = ks.solveKnapsack(profits, weights, 7)
print("Total knapsack profit --->", max_profit)
max_profit = ks.solveKnapsack(profits, weights, 6)
print("Total knapsack profit --->", max_profit)Go
package main
import (
"fmt"
)
type Knapsack struct{}
func (ks Knapsack) SolveKnapsack(profits []int, weights []int, capacity int) int {
// 基准检查
if capacity <= 0 || len(profits) == 0 || len(weights) != len(profits) {
return 0
}
n := len(profits)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, capacity+1)
}
// 填充capacity=0的那列，0容量0利润
for i := 0; i < n; i++ {
dp[i][0] = 0
}
// 如果我们只有一个重量，如果它不超过承载量，我们就接受它
for c := 0; c <= capacity; c++ {
if weights[0] <= c {
dp[0][c] = profits[0]
}
}
// 为所有容量处理所有子数组
for i := 1; i < n; i++ {
for c := 1; c <= capacity; c++ {
profit1, profit2 := 0, 0
// 如果当前元素的重量不超过容量，包含当前元素
if weights[i] <= c {
profit1 = profits[i] + dp[i-1][c-weights[i]]
}
// 不包含当前项
profit2 = dp[i-1][c]
// 取profit1和profit2中的最大值
dp[i][c] = max(profit1, profit2)
}
}
// 右下角为最大的利润
return dp[n-1][capacity]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
ks := Knapsack{}
profits := []int{1, 6, 10, 16}
weights := []int{1, 2, 3, 5}
maxProfit := ks.SolveKnapsack(profits, weights, 7)
fmt.Println("Total knapsack profit --->", maxProfit)
maxProfit = ks.SolveKnapsack(profits, weights, 6)
fmt.Println("Total knapsack profit --->", maxProfit)
}