算法题/01背包：01背包最大盈利

题目

已知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)
}