无限背包最大盈利

题目

已知N个物品的重量和利润，我们被要求把这些物品放在一个容量为C的背包里。目标是从背包中的物品中获得最大的利润。0/1背包问题和这个问题的唯一区别是，我们可以使用无限数量的物品。

示例：

物品：物品1、物品2、物品3
单个物品重量：1、2、3
单个物品盈利：15、20、50
背包容量：5

题解

暴力求解

class Knapsack {

  public int solveKnapsack(int[] profits, int[] weights, int capacity) {
    return this.knapsackRecursive(profits, weights, capacity, 0);
  }

  private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
    // 基准检查
    if (capacity <= 0 || profits.length == 0 || weights.length != profits.length || 
        currentIndex >= profits.length)
      return 0;

    // 选择当前物品后，通过不增长索引来递归调用所有的物品
    int profit1 = 0;
    if (weights[currentIndex] <= capacity)
      profit1 = profits[currentIndex]
          + knapsackRecursive(profits, weights, capacity - weights[currentIndex], currentIndex);

    //排除当前索引的物品后递归调用
    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 = { 15, 50, 60, 90 };
    int[] weights = { 1, 3, 4, 5 };
    int maxProfit = ks.solveKnapsack(profits, weights, 8);
    System.out.println(maxProfit);
  }
}

class Knapsack {
  solveKnapsack(profits, weights, capacity) {
    return this.knapsackRecursive(profits, weights, capacity, 0);
  }

  knapsackRecursive(profits, weights, capacity, currentIndex) {
    // 基准检查
    if (capacity <= 0 || profits.length === 0 || weights.length !== profits.length || currentIndex >= profits.length)
      return 0;

    // 选择当前物品后，通过不增长索引来递归调用所有的物品
    let profit1 = 0;
    if (weights[currentIndex] <= capacity)
      profit1 = profits[currentIndex] + this.knapsackRecursive(profits, weights, capacity - weights[currentIndex], currentIndex);

    // 排除当前索引的物品后递归调用
    let profit2 = this.knapsackRecursive(profits, weights, capacity, currentIndex + 1);

    return Math.max(profit1, profit2);
  }

  static main(args) {
    const ks = new Knapsack();
    const profits = [15, 50, 60, 90];
    const weights = [1, 3, 4, 5];
    const maxProfit = ks.solveKnapsack(profits, weights, 8);
    console.log(maxProfit);
  }
}

Knapsack.main();

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 len(profits) == 0 or len(weights) != len(profits) or currentIndex >= len(profits):
            return 0

        # 选择当前物品后，通过不增长索引来递归调用所有的物品
        profit1 = 0
        if weights[currentIndex] <= capacity:
            profit1 = profits[currentIndex] + self.knapsackRecursive(profits, weights, capacity - weights[currentIndex], currentIndex)

        # 排除当前索引的物品后递归调用
        profit2 = self.knapsackRecursive(profits, weights, capacity, currentIndex + 1)

        return max(profit1, profit2)

    @staticmethod
    def main():
        ks = Knapsack()
        profits = [15, 50, 60, 90]
        weights = [1, 3, 4, 5]
        maxProfit = ks.solveKnapsack(profits, weights, 8)
        print(maxProfit)

Knapsack.main()

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 || len(profits) == 0 || len(weights) != len(profits) || currentIndex >= len(profits) {
		return 0
	}

	// 选择当前物品后，通过不增长索引来递归调用所有的物品
	profit1 := 0
	if weights[currentIndex] <= capacity {
		profit1 = profits[currentIndex] + ks.knapsackRecursive(profits, weights, capacity-weights[currentIndex], currentIndex)
	}

	// 排除当前索引的物品后递归调用
	profit2 := ks.knapsackRecursive(profits, weights, capacity, currentIndex+1)

	if profit1 > profit2 {
		return profit1
	}
	return profit2
}

func main() {
	ks := Knapsack{}
	profits := []int{15, 50, 60, 90}
	weights := []int{1, 3, 4, 5}
	maxProfit := ks.solveKnapsack(profits, weights, 8)
	fmt.Println(maxProfit)
}

自顶向下(备忘录)

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 || profits.length == 0 || weights.length != profits.length ||
        currentIndex >= profits.length)
      return 0;

    // 检查我们是否已经处理过相似子问题
    if(dp[currentIndex][capacity] == null) {
      // 选择当前物品后，通过不增长索引来递归调用所有的物品
      int profit1 = 0;
      if( weights[currentIndex] <= capacity )
          profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights,
                  capacity - weights[currentIndex], currentIndex);

      //排除当前索引的物品后递归调用
      int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);

      dp[currentIndex][capacity] = Math.max(profit1, profit2);
    }

    return dp[currentIndex][capacity];
  }

  public static void main(String[] args) {
    Knapsack ks = new Knapsack();
    int[] profits = {15, 50, 60, 90};
    int[] weights = {1, 3, 4, 5};
    System.out.println(ks.solveKnapsack(profits, weights, 8));
    System.out.println(ks.solveKnapsack(profits, weights, 6));
  }
}

class Knapsack {
  solveKnapsack(profits, weights, capacity) {
    let 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 ||
      profits.length === 0 ||
      weights.length !== profits.length ||
      currentIndex >= profits.length
    ) {
      return 0;
    }

    if (dp[currentIndex][capacity] === null) {
      let profit1 = 0;
      if (weights[currentIndex] <= capacity) {
        profit1 =
          profits[currentIndex] +
          this.knapsackRecursive(
            dp,
            profits,
            weights,
            capacity - weights[currentIndex],
            currentIndex
          );
      }

      let profit2 = this.knapsackRecursive(
        dp,
        profits,
        weights,
        capacity,
        currentIndex + 1
      );

      dp[currentIndex][capacity] = Math.max(profit1, profit2);
    }

    return dp[currentIndex][capacity];
  }

  static main() {
    let ks = new Knapsack();
    let profits = [15, 50, 60, 90];
    let weights = [1, 3, 4, 5];
    console.log(ks.solveKnapsack(profits, weights, 8));
    console.log(ks.solveKnapsack(profits, weights, 6));
  }
}

Knapsack.main();

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 len(profits) == 0 or len(weights) != len(profits) or currentIndex >= len(profits):
            return 0

        if dp[currentIndex][capacity] is None:
            profit1 = 0
            if weights[currentIndex] <= capacity:
                profit1 = profits[currentIndex] + self.knapsackRecursive(
                    dp, profits, weights, capacity - weights[currentIndex], currentIndex
                )

            profit2 = self.knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1)

            dp[currentIndex][capacity] = max(profit1, profit2)

        return dp[currentIndex][capacity]


if __name__ == "__main__":
    ks = Knapsack()
    profits = [15, 50, 60, 90]
    weights = [1, 3, 4, 5]
    print(ks.solveKnapsack(profits, weights, 8))
    print(ks.solveKnapsack(profits, weights, 6))

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 := range dp {
		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 || len(profits) == 0 || len(weights) != len(profits) || currentIndex >= len(profits) {
		return 0
	}

	if dp[currentIndex][capacity] == 0 {
		profit1 := 0
		if weights[currentIndex] <= capacity {
			profit1 = profits[currentIndex] + ks.knapsackRecursive(dp, profits, weights, capacity-weights[currentIndex], currentIndex)
		}

		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{15, 50, 60, 90}
	weights := []int{1, 3, 4, 5}
	fmt.Println(ks.solveKnapsack(profits, weights, 8))
	fmt.Println(ks.solveKnapsack(profits, weights, 6))
}

自底向上

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的那一列
    for(int i=0; i < n; i++)
      dp[i][0] = 0;

    // 处理所有子数组
    for(int i=0; i < n; i++) {
      for(int c=1; c <= capacity; c++) {
        int profit1=0, profit2=0;
        if(weights[i] <= c)
          profit1 = profits[i] + dp[i][c-weights[i]];
        if( i > 0 )
          profit2 = dp[i-1][c];
        dp[i][c] = profit1 > profit2 ? profit1 : profit2;
      }
    }

    // 最大盈利在右下角
    return dp[n-1][capacity];
  }

  public static void main(String[] args) {
    Knapsack ks = new Knapsack();
    int[] profits = {15, 50, 60, 90};
    int[] weights = {1, 3, 4, 5};
    System.out.println(ks.solveKnapsack(profits, weights, 8));
    System.out.println(ks.solveKnapsack(profits, weights, 6));
  }
}

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);
    for (let i = 0; i < n; i++) {
      dp[i] = new Array(capacity + 1).fill(0);
    }

    // 填充capacity=0的那一列
    for (let i = 0; i < n; i++) {
      dp[i][0] = 0;
    }

    // 处理所有子数组
    for (let i = 0; i < n; i++) {
      for (let c = 1; c <= capacity; c++) {
        let profit1 = 0, profit2 = 0;
        if (weights[i] <= c)
          profit1 = profits[i] + dp[i][c - weights[i]];
        if (i > 0)
          profit2 = dp[i - 1][c];
        dp[i][c] = Math.max(profit1, profit2);
      }
    }

    // 最大盈利在右下角
    return dp[n - 1][capacity];
  }
}

const ks = new Knapsack();
const profits = [15, 50, 60, 90];
const weights = [1, 3, 4, 5];
console.log(ks.solveKnapsack(profits, weights, 8));
console.log(ks.solveKnapsack(profits, weights, 6));

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的那一列
        for i in range(n):
            dp[i][0] = 0

        # 处理所有子数组
        for i in range(n):
            for c in range(1, capacity + 1):
                profit1, profit2 = 0, 0
                if weights[i] <= c:
                    profit1 = profits[i] + dp[i][c - weights[i]]
                if i > 0:
                    profit2 = dp[i - 1][c]
                dp[i][c] = max(profit1, profit2)

        # 最大盈利在右下角
        return dp[n - 1][capacity]


ks = Knapsack()
profits = [15, 50, 60, 90]
weights = [1, 3, 4, 5]
print(ks.solveKnapsack(profits, weights, 8))
print(ks.solveKnapsack(profits, weights, 6))

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 := 0; i < n; i++ {
		dp[i] = make([]int, capacity+1)
	}

	// 填充capacity=0的那一列
	for i := 0; i < n; i++ {
		dp[i][0] = 0
	}

	// 处理所有子数组
	for i := 0; i < n; i++ {
		for c := 1; c <= capacity; c++ {
			profit1, profit2 := 0, 0
			if weights[i] <= c {
				profit1 = profits[i] + dp[i][c-weights[i]]
			}
			if i > 0 {
				profit2 = dp[i-1][c]
			}
			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{15, 50, 60, 90}
	weights := []int{1, 3, 4, 5}
	fmt.Println(ks.solveKnapsack(profits, weights, 8))
	fmt.Println(ks.solveKnapsack(profits, weights, 6))
}