网站可以做的兼职,做旅游的网站的目的和意义,seo外包怎么收费,有做a50期货的网站Java手写背包问题算法应用拓展案例
1. 0-1背包问题
实际案例#xff1a;购物问题
假设你是一个购物爱好者#xff0c;你去商场购物#xff0c;商场里有很多商品#xff0c;每个商品有自己的重量和价值。你只有一个背包#xff0c;它的容量是有限的。你希望在购物过程中…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[n1][capacity1];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];}
}输出结果为
最大总价值为9根据以上代码我们可以得到购物问题的最优解选择重量为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[capacity1];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];}
}输出结果为
最大总价值为12根据以上代码我们可以得到旅行问题的最优解选择重量为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[capacity1];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];}
}输出结果为
最大总价值为22根据以上代码我们可以得到装箱问题的最优解选择重量为2、3和5的货物总价值为22。
以上就是Java手写背包问题算法应用拓展案例的完整代码和实际案例。通过这些案例我们可以更好地理解和应用背包问题算法。
商品选择问题
在电商平台的商品推荐系统中根据用户的购买历史和偏好需要选出一组适合的商品推荐给用户。这可以视为一个背包问题的应用。下面是使用Java手写背包问题算法解决商品选择问题的完整代码。
定义商品类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;}
}实现背包问题算法Knapsack
import java.util.ArrayList;
import java.util.List;class Knapsack {ListItem 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];}}}ListItem 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;}
}测试代码
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();ListItem selectedItems knapsack.selectItems(items, maxWeight);System.out.println(选择的商品);for (Item item : selectedItems) {System.out.println(item.name);}}
}工程任务调度问题
在一个工程项目中有多个任务需要执行这些任务存在依赖关系即某些任务必须在其他任务完成之后才能开始。通过背包问题算法可以解决工程任务调度问题。下面是使用Java手写背包问题算法解决工程任务调度问题的完整代码。
定义任务类Task
class Task {String name;int duration;ListTask dependencies;public Task(String name, int duration, ListTask dependencies) {this.name name;this.duration duration;this.dependencies dependencies;}
}实现背包问题算法TaskScheduler
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;class TaskScheduler {SetTask selectedTasks new HashSet();void scheduleTasks(ListTask 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);}
}算法应用总结
当涉及到手写背包问题算法的应用和拓展案例时以下是一个总结 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时的最大价值。 完全背包问题每个物品可以无限次地放入背包中。 算法思路同样使用动态规划算法但是需要对物品的放入次数进行遍历判断。算法步骤 初始化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时的最大价值。
这些是背包问题的基本算法总结和应用案例通过调整问题的约束条件和算法思路还可以进行更多的扩展如多重背包问题、分数背包问题等。
