Java手写背包问题算法应用拓展案例

Java手写背包问题算法应用拓展案例

1. 0-1背包问题

实际案例：购物问题

假设你是一个购物爱好者，你去商场购物，商场里有很多商品，每个商品有自己的重量和价值。你只有一个背包，它的容量是有限的。你希望在购物过程中选择一些商品放入背包中，使得背包中的商品总价值最大。

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5}; // 商品的重量
        int[] values = {3, 4, 5, 6}; // 商品的价值
        int capacity = 8; // 背包的容量

        int maxValue = knapsack01(weights, values, capacity);
        System.out.println("最大总价值为：" + maxValue);
    }

    // 定义函数，求解0-1背包问题
    public static int knapsack01(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n+1][capacity+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i-1] <= j) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        return dp[n][capacity];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

输出结果为：

最大总价值为：9
1

根据以上代码，我们可以得到购物问题的最优解，选择重量为2和3的商品，总价值为9。

2. 完全背包问题

实际案例：旅行问题

假设你是一个旅行爱好者，你计划去旅行，旅行地有很多景点，每个景点有自己的重量和价值。你只有一个背包，它的容量是有限的。你希望在旅行过程中选择一些景点参观，使得背包中的景点总价值最大。

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5}; // 景点的重量
        int[] values = {3, 4, 5, 6}; // 景点的价值
        int capacity = 8; // 背包的容量

        int maxValue = knapsackComplete(weights, values, capacity);
        System.out.println("最大总价值为：" + maxValue);
    }

    // 定义函数，求解完全背包问题
    public static int knapsackComplete(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity+1];

        for (int i = 0; i < n; i++) {
            for (int j = weights[i]; j <= capacity; j++) {
                dp[j] = Math.max(dp[j], dp[j-weights[i]] + values[i]);
            }
        }

        return dp[capacity];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

输出结果为：

最大总价值为：12
1

根据以上代码，我们可以得到旅行问题的最优解，选择重量为2和3的景点，总价值为12。

3. 多重背包问题

实际案例：装箱问题

假设你是一个货物装箱员，你需要将一批货物装箱，每个货物有自己的重量和价值，而且每个货物的数量是有限的。你只有一个箱子，它的容量是有限的。你希望在装箱过程中选择一些货物放入箱子中，使得箱子中的货物总价值最大。

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5}; // 货物的重量
        int[] values = {3, 4, 5, 6}; // 货物的价值
        int[] counts = {1, 2, 3, 4}; // 货物的数量
        int capacity = 8; // 箱子的容量

        int maxValue = knapsackMultiple(weights, values, counts, capacity);
        System.out.println("最大总价值为：" + maxValue);
    }

    // 定义函数，求解多重背包问题
    public static int knapsackMultiple(int[] weights, int[] values, int[] counts, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity+1];

        for (int i = 0; i < n; i++) {
            for (int j = capacity; j >= weights[i]; j--) {
                for (int k = 1; k <= counts[i] && k*weights[i] <= j; k++) {
                    dp[j] = Math.max(dp[j], dp[j-k*weights[i]] + k*values[i]);
                }
            }
        }

        return dp[capacity];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

输出结果为：

最大总价值为：22
1

根据以上代码，我们可以得到装箱问题的最优解，选择重量为2、3和5的货物，总价值为22。

以上就是Java手写背包问题算法应用拓展案例的完整代码和实际案例。通过这些案例，我们可以更好地理解和应用背包问题算法。

商品选择问题

在电商平台的商品推荐系统中，根据用户的购买历史和偏好，需要选出一组适合的商品推荐给用户。这可以视为一个背包问题的应用。下面是使用Java手写背包问题算法解决商品选择问题的完整代码。

1. 定义商品类（Item）：

class Item {
    String name;
    int value;
    int weight;
    
    public Item(String name, int value, int weight) {
        this.name = name;
        this.value = value;
        this.weight = weight;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2. 实现背包问题算法（Knapsack）：

import java.util.ArrayList;
import java.util.List;

class Knapsack {
    List<Item> selectItems(Item[] items, int maxWeight) {
        int n = items.length;
        int[][] dp = new int[n + 1][maxWeight + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= maxWeight; j++) {
                if (items[i - 1].weight <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], items[i - 1].value + dp[i - 1][j - items[i - 1].weight]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        List<Item> selectedItems = new ArrayList<>();
        int i = n, j = maxWeight;
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i - 1][j]) {
                selectedItems.add(items[i - 1]);
                j -= items[i - 1].weight;
            }
            i--;
        }

        return selectedItems;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3. 测试代码：

public class Main {
    public static void main(String[] args) {
        Item item1 = new Item("商品1", 10, 4);
        Item item2 = new Item("商品2", 8, 3);
        Item item3 = new Item("商品3", 6, 2);
        Item item4 = new Item("商品4", 4, 1);

        Item[] items = {item1, item2, item3, item4};
        int maxWeight = 5;

        Knapsack knapsack = new Knapsack();
        List<Item> selectedItems = knapsack.selectItems(items, maxWeight);
        
        System.out.println("选择的商品：");
        for (Item item : selectedItems) {
            System.out.println(item.name);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

工程任务调度问题

在一个工程项目中，有多个任务需要执行，这些任务存在依赖关系，即某些任务必须在其他任务完成之后才能开始。通过背包问题算法可以解决工程任务调度问题。下面是使用Java手写背包问题算法解决工程任务调度问题的完整代码。

1. 定义任务类（Task）：

class Task {
    String name;
    int duration;
    List<Task> dependencies;
    
    public Task(String name, int duration, List<Task> dependencies) {
        this.name = name;
        this.duration = duration;
        this.dependencies = dependencies;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2. 实现背包问题算法（TaskScheduler）：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class TaskScheduler {
    Set<Task> selectedTasks = new HashSet<>();

    void scheduleTasks(List<Task> tasks) {
        for (Task task : tasks) {
            if (!selectedTasks.contains(task)) {
                selectTask(task);
            }
        }
    }

    void selectTask(Task task) {
        for (Task dependency : task.dependencies) {
            if (!selectedTasks.contains(dependency)) {
                selectTask(dependency);
            }
        }
        selectedTasks.add(task);
        System.out.println("执行任务：" + task.name);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

算法应用总结

当涉及到手写背包问题算法的应用和拓展案例时，以下是一个总结：

1. 0/1背包问题：每个物品要么被选中放入背包中，要么不放入。

   • 算法思路：使用动态规划算法，创建一个二维数组dp[i][j]，其中dp[i][j]表示将前i个物品放入容量为j的背包时的最大价值。
   • 算法步骤：
     • 初始化dp数组为0。
     • 对于每个物品i，在容量为j的背包内进行判断：
       • 如果当前物品的重量wi大于背包容量j，则dp[i][j]等于dp[i-1][j]，即不放入该物品。
       • 否则，比较放入该物品的价值（dp[i-1][j-wi]加上当前物品价值）与不放入该物品的价值（dp[i-1][j]）的大小，取较大的值作为dp[i][j]的值。
     • 最终dp数组的最后一个元素dp[n][W]即为背包容量为W时的最大价值。

2. 完全背包问题：每个物品可以无限次地放入背包中。

   • 算法思路：同样使用动态规划算法，但是需要对物品的放入次数进行遍历判断。
   • 算法步骤：
     • 初始化dp数组为0。
     • 对于每个物品i，在容量为j的背包内进行判断：
       • 遍历放入该物品的次数k，从0到j/wi，其中wi为物品的重量：
         • 假设当前放入k个物品i，则背包的容量减少为j-kwi，价值增加为dp[i-1][j-kwi]加上k*vi，其中vi为物品的价值。
         • 比较该情况下的价值与不放入该物品的价值dp[i-1][j]的大小，取较大值作为dp[i][j]的值。
     • 最终dp数组的最后一个元素dp[n][W]即为背包容量为W时的最大价值。

这些是背包问题的基本算法总结和应用案例，通过调整问题的约束条件和算法思路，还可以进行更多的扩展，如多重背包问题、分数背包问题等。