01背包最大盈利

题目

已知N个物品的重量和利润，我们将这些物品放入容量为C的背包。目标是背包中的物品中获得最大的利润。每个物品只能选择一次。

示例：

物品：物品1、物品2、物品3、物品4
单个物品重量：2、3、1、4
单个物品盈利：4、5、3、7
背包容量：5

题解

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);
  }
}

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);

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)

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