题目
已知N个物品的重量和利润，我们被要求把这些物品放在一个容量为C的背包里。目标是从背包中的物品中获得最大的利润。0/1背包问题和这个问题的唯一区别是，我们可以使用无限数量的物品。
示例：
物品：物品1、物品2、物品3
单个物品重量：1、2、3
单个物品盈利：15、20、50
背包容量：5
题解
暴力求解
Java
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);
}
}JavaScript
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();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 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()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 || 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)
}自顶向下（备忘录）
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 || 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));
}
}JavaScript
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();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 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))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 := 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))
}自底向上
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的那一列
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));
}
}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);
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));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的那一列
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))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 := 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))
}