初识背包问题之 「 0-1 背包 」

简介: 本文主要为大家讲解传统算法中的背包问题。

35.jpeg

原文链接

前言

背包问题可以说是一个老生常谈的问题,通常被用作面试题来考查面试者对动归的理解,我们经常说学算法,初学者最难理解的就是 “二归”,一个叫递归,另一个叫动归。
而背包问题属于特殊的一类动归问题,也就是按值动归,这篇文章主要讲解  0-1 背包 问题,如果读者能看明白,那么弄懂后续的 完全背包 以及 多重背包 这两个知识点问题也是不大的。
通常背包这一类题目,题目大概就是给你一个容量或者大小固定的背包,然后要求你去用这个背包去装物品,一般来说这些物品都是大小固定的,但是题目对物品的限定不同,衍生出来多种背包问题。

  • 0-1 背包 问题中,物品个数有且仅有一个;
  • 完全背包 问题中的物品个数是无限的;
  • 多重背包 问题中的针对不同的物品,个数不一样。

通常题目会要你求出背包能装的最大价值(每个物品都会有容量和价值),当然也会有不一样的问法,类似背包能否被装满,还有背包能装的最大容量是多少,多少种方式填满背包。
但是这些并不是背包问题的所有,还有 分组背包 问题,依赖背包 问题等等,因为考虑到这篇文章主要是针对面试,而不是竞赛,这些有机会再去介绍。

0-1 背包

题目描述

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 C[i]  ,得到的价值是 W[i] 。求解将哪些物品装入背包可使价值总和最大。求出最大总价值。

题目分析

对于每一个物品可以考虑放,或者不放;如果当前是第 i 个物品,当前背包里面物品总价值是 W,背包当前容量是 V ,如果取这个物品,背包总价值会变成  Wcurrent + W[i] ,背包容量会变成 V – C[i] 。
之前我们提到过,背包是属于按值动归,我们把背包划分为 1-V个区间,也就是背包所有可能的大小,然后针对所有的物品,看看每个背包容量下能存放的最大价值,代码如下:

public static int zeroOnePack(int V, int[] C, int[] W) { 
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }
    int n = C.length;
    // dp[i][j]: 对于下标为 0~i 的物品,背包容量为 j 时的最大价值
    int[][] dp = new int[n + 1][V + 1];
    // 背包空的情况下,价值为 0
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= V; ++j) {
            // 不选物品 i 的话,当前价值就是取到前一个物品的最大价值,也就是 dp[i - 1][j]
            dp[i][j] = dp[i - 1][j];
            // 如果选择物品 i 使得当前价值相对不选更大,那就选取 i,更新当前最大价值
            if ((j >= C[i - 1]) && (dp[i][j] < dp[i - 1][j - C[i - 1]] + W[i - 1])) {
                dp[i][j] = dp[i - 1][j - C[i - 1]] + W[i - 1];
            }
        }
    }
    // 返回,对于所有物品(0~N),背包容量为 V 时的最大价值
    return dp[n][V];
}

代码优化

空间优化:  
仅仅看代码就可以发现,其实 dp 数组当前行的计算只用到了前一行,我们可以利用 滚动数组 来优化,但是再仔细看下去的话,你就会发现其实还可以更优,当前行的遍历用到的值是上一行的前面列的值,如果我们第二层 for 循环遍历的时候倒着遍历的话,保证了前面更新的值不会被新计算的值覆盖掉,我们仅仅用一维数组就可以完美解决问题,代码如下:

public static int zeroOnePackOpt(int V, int[] C, int[] W) { 
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }
    int n = C.length;
    int[] dp = new int[V + 1];
    // 背包空的情况下,价值为 0
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= C[i]; --j) {
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }
    return dp[V];
}

极端情况优化:
当背包的 V 特别大的时候,对于每一个物品都去遍历一遍没有意义,通过阈值来进行优化,优化的同时可以考虑将数组从大到小排个序:

public static int zeroOnePackOpt(int V, int[] C, int[] W) {
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }
    int n = C.length;
    int[] dp = new int[V + 1];
    int bound, sum = 0, total = 0;
    for (int i : C) {
        total += i;
    }
    for (int i = 0; i < n; ++i) {
        bound = Math.max(V - total + sum, C[i]);
        sum += C[i];
        for (int j = V; j >= bound; --j) {
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }
    return dp[V];
}

总结

0-1 背包 基本概况就是这些,当然可能问题的问法会不一样,例如:

  • 背包能不能被装满
    解题思路就是将 int 数组换成 boolean 数组,也不用去考虑物品的价值来,直接看容量够不够,能不能装进背包即可
  • 背包能装的最大容量
    也很简单,解法和上面 “背包能不能被装满” 一样,只不过最后需要从后往前遍历 dp 数组,直到找到 true
  • 多少种方式塞满背包
    同样是不用考虑物品的价值,用 int 数组,但是里面记录的是个数,背包被填充的个数,也就是把这里的个数当作价值来看待,只不过 W[i] = 1。

来源 | 五分钟学算法
作者 | P.yh

相关文章
|
JavaScript 前端开发 索引
|
3天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
1661 2
|
6天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
6天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
3天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
3177 0
|
19天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
8547 58
|
13天前
|
Linux 开发工具 iOS开发
2026最新codex下载安装保姆级使用教程(下载+安装+登录+使用,含所有历史版本)
本文详解OpenAI Codex国内快速上手指南:提供Win/macOS/Linux全平台免安装包、npm/Homebrew等多方式安装、账号/API Key双登录、简体中文切换,覆盖下载、安装、汉化、使用及高频避坑(如微软商店失败、npm超时等),10分钟即可跑通。
3034 9
|
19天前
|
JavaScript API iOS开发
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(DSH)是DeepSeek于2026年开源的MIT协议AI Agent框架,支持插件化组装模型、工具、沙箱与UI,兼容主流大模型。本文提供免Node.js的桌面端安装包(Win/macOS),含详细图文教程及热门插件推荐。
5814 69
|
7天前
|
云安全 人工智能 安全