Java 数据结构与算法系列精讲之背包问题

Java 数据结构与算法系列精讲之背包问题

概述

从今天开始, 小白我将带大家开启 java 数据结构 & 算法的新篇章.

动态规划

动态规划 (Dynamic Programming) 的核心思想是把大问题划分为小问题进行解决. 先求解子问题, 然后从这些子问题的解得到原问题的解.

动态规划的优点:

可以帮助我们解决多阶段问题, 化繁为简

动态规划的缺点:

没有统一的处理方法, 具体问题具体分析

当变量的维数增大时, 计算和存储会急剧增大

背包问题

背包问题 (Knapsack Problem) 指有 N 件物品和一个容量为 V 的背包. 第 i 件物品的费用是 c[i]，价值是 w[i]. 求解将哪些物品装入背包可使价值总http://和最大.

代码实现

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) {

// 不装入背包

vhttp://[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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。