Python 官方文档:入门教程 => 点击学习
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 动态规划 动态规划 (Dynamic Programming) 的核心思想是把大问题划分为小
从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.
动态规划 (Dynamic Programming) 的核心思想是把大问题划分为小问题进行解决. 先求解子问题, 然后从这些子问题的解得到原问题的解.
动态规划的优点:
动态规划的缺点:
背包问题 (Knapsack Problem) 指有 N 件物品和一个容量为 V 的背包. 第 i 件物品的费用是 c[i],价值是 w[i]. 求解将哪些物品装入背包可使价值总和最大.
public class 背包问题 {
public static void main(String[] args) {
int[] w = {1, 2, 3}; // 物品重量
int[] val = {6, 10, 12}; // 物品价值
int m = 5; // 背包容量
int n = val.length; //
// 创建二维数组
int[][] v = new int[n + 1][m + 1];
// 将第一行和第一列赋值为0
for (int i = 0; i < v.length; i++) {
v[i][0] = 0;
}
for (int i = 0; i < v[0].length; i++) {
v[0][i] = 0;
}
// 动态处理
for (int i = 1; i < v.length; i++) {
for (int j = 1; j < v[0].length; j++) {
if (w[i - 1] > j) {
// 不装入背包
v[i][j] = v[i - 1][j];
} else {
// 装入背包
v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
}
}
}
// 输出二维数组
for (int i = 1; i < v.length; i++) {
for (int j = 1; j < v[0].length; j++) {
System.out.print(v[i][j] + "\t");
}
System.out.println();
}
}
}
输出结果:
6 6 6 6 6
6 10 16 16 16
6 10 16 18 22
到此这篇关于Java 数据结构与算法系列精讲之背包问题的文章就介绍到这了,更多相关Java 背包问题内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: Java数据结构与算法系列精讲之背包问题
本文链接: https://www.lsjlt.com/news/139612.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0