当前位置：首页 > news >正文

背包问题（1）

news 2025/5/23 7:31:48

大一学了大三复习一下巩固一下知识；

装箱问题_牛客题霸_牛客网https://www.nowcoder.com/practice/55100a6608ad4656849dbd1f16d044cb?tpId=308&tqId=170605&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

实例

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 caseint a = in.nextInt();int b = in.nextInt();System.out.println(a + b);}}
}

第一次试错（贪心）:

import java.util.Scanner;//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {public static void main(String[] args) {//TIP Press <shortcut actionId="ShowIntentionActions"/> with your caret at the highlighted text// to see how IntelliJ IDEA suggests fixing it.Scanner scanner = new Scanner(System.in);//箱子容量int boxv= scanner.nextInt();//物品数量int object_num = scanner.nextInt();int[] object = new int[object_num];for(int i = 0; i < object_num; i++){object[i] = scanner.nextInt();}int res = boxv;for(int i = 0; i < object_num; i++){if (boxv-object[i] > 0) {boxv = Math.min(boxv - object[i], boxv);}}System.out.println(boxv);}}

错误之处贪心思想只能解决局部最优无法结局全局最优

解题思路

动态规划

import java.util.Scanner;//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {public static void main(String[] args) {//TIP Press <shortcut actionId="ShowIntentionActions"/> with your caret at the highlighted text// to see how IntelliJ IDEA suggests fixing it.Scanner scanner = new Scanner(System.in);//箱子容量int boxv= scanner.nextInt();//物品数量int object_num = scanner.nextInt();int[] object = new int[object_num+1];for(int i = 0; i < object_num; i++){object[i] = scanner.nextInt();}int[] dp = new int[boxv+1];//盒子中的体积for(int i = 0; i < object_num; i++){//每个物品只使用一次 倒序遍历for (int j = boxv; j >= object[i]; j--){dp [j] = Math.max(dp[j],dp[j-object[i]]+object[i]);}}System.out.println(boxv-dp[boxv]);}}

状态定义：
dp[j] 表示容量为 j 时能装入的最大总体积。
这个定义直接对应问题目标：我们需要的最终结果就是 dp[V]（容量为 V 时的最大装入体积）。

回溯剪枝

import java.util.Scanner;public class Main {static int[][] f; // 记忆化数组public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int V = scanner.nextInt(); // 箱子容量int n = scanner.nextInt(); // 物品数量int[] v = new int[n];      // 物品体积数组// 读取每个物品的体积for (int i = 0; i < n; i++) {v[i] = scanner.nextInt();}// 初始化记忆化数组，-1表示未计算f = new int[n + 1][V + 1];for (int i = 0; i <= n; i++) {for (int j = 0; j <= V; j++) {f[i][j] = -1;}}// 计算最大能装入的体积int maxVolume = dp(v, V, n);// 输出剩余空间System.out.println(V - maxVolume);}// 递归函数：计算前n个物品，容量为V时的最大装入体积static int dp(int[] v, int V, int n) {// 如果已经计算过，直接返回结果if (f[n][V] >= 0) {return f[n][V];}// 边界条件：没有物品时，最大体积为0if (n == 0) {return 0;}// 当前物品体积小于等于容量，可以选或不选if (V >= v[n - 1]) {f[n][V] = Math.max(dp(v, V, n - 1),dp(v, V - v[n - 1], n - 1) + v[n - 1]);} else {// 当前物品体积大于容量，不能选f[n][V] = dp(v, V, n - 1);}return f[n][V];}
}

状态转移逻辑：
对于每个物品体积 w，有两种选择：
- 不选：则容量为 j 时的最大体积仍为 dp[j]。
- 选：前提是 j≥w，此时需要用前 i−1 个物品填满 j−w 的容量，再加上当前物品的体积 w，即 dp[j-w] + w。
  因此，状态转移方程为：dp[j]=max(dp[j], dp[j−w]+w)
  逆序遍历容量（从 V 到 w）是为了确保每个物品只被选一次（避免重复计算），这是 01 背包的核心优化技巧。