笔试题回顾：动态规划+装箱+01背包问题

题目描述

华为的笔试，就写出来这一题。 其实就是01背包问题

输入 第一行货车的容量K 第二行箱子的种类数量N 第三行箱子的重量w 第四行箱子的价值v输出 货车能装的最大价值。输入用例 9 5 2 2 4 6 3 3 4 8 9 6输出用例 18

$$dp[i][j]=\{\begin{array}{ll}dp[i-1][j]& \text{ ,当第i件物品太重以至于放不进去 }\\ \text{Math.max}& \{\begin{array}{l}dp[i-1][j-\text{weight}[i]]+\text{value}[i],\text{ 把第i件物品放进去需要先腾出w[i]空间 }\\ dp[i-1][j],\text{ 不放进去 }\end{array}\end{array}$$

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int K = Integer.parseInt(sc.nextLine().trim()); //货车容量 int N = Integer.parseInt(sc.nextLine().trim()); //箱子种类 String[] strw = sc.nextLine().trim().split(" "); String[] strv = sc.nextLine().trim().split(" "); int[] w = new int[N+1];//箱子尺寸 int[] v = new int[N+1];//箱子价值 for (int i = 0; i < strw.length; i++) w[i+1] = Integer.parseInt(strw[i]); for (int i = 0; i < strv.length; i++) v[i+1] = Integer.parseInt(strv[i]); //以上是输入数据。 int[][] dp = new int[N + 1][K + 1]; for (int i = 1; i < N + 1; i++) { for (int j = 1; j < K + 1; j++) { if (j >= w[i]) {//关键代码，状态转移方程 dp[i][j] = Math.max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]); }else dp[i][j] =dp[i-1][j]; } } System.out.println(dp[N][K]); } } weight数组: [0, 2, 2, 4, 6, 3] value数组： [0, 3, 4, 8, 9, 6] dp数组情况如下： [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 3, 3, 3, 3, 3, 3, 3, 3] [0, 0, 4, 4, 7, 7, 7, 7, 7, 7] [0, 0, 4, 4, 8, 8, 12, 12, 15, 15] [0, 0, 4, 4, 8, 8, 12, 12, 15, 15]

PS：本人水平有限，文中如有错漏，欢迎大家指出。转载请注明来源。欢迎大家积极回复，学习的路上不想单机（︶︿︶）