【自用】0-1背包问题与完全背包问题的Java实现

引言

背包问题是计算机科学领域的一个经典优化问题,分为多种类型,其中最常见的是0-1背包问题和完全背包问题。这两种问题的核心在于如何在有限的空间内最大化收益,但它们之间存在一些关键的区别:0-1背包问题允许每个物品只能选择一次,而完全背包问题则允许无限次选取同一物品。本篇博客将分别介绍这两个问题的动态规划解法,并附带相应的Java代码实现。

0-1背包问题

问题描述

假设你有一个背包,其最大承重能力为W千克,现在有一系列物品,每个物品有自己的重量Wi和价值Vi。你的任务是从这些物品中挑选一部分装入背包,使得背包的价值尽可能大,但不能超过背包的最大承重限制。

解决方案

我们可以采用动态规划的方法来求解这个问题。定义一个二维数组dp[i][j]表示从前i个物品中选择若干个放入容量为j的背包所能获得的最大价值。状态转移方程

Java代码实现

package dp;import java.util.ArrayList;
import java.util.List;public class Knapsack {public static void main(String[] args) {int n = 4; // 物品数量int bagweight = 16; // 背包最大容量int[] weight = {5, 7, 3, 4}; // 物品重量int[] value = {2, 5, 8, 1}; // 物品价值// 初始化 dp 数组int[][] dp = new int[n + 1][bagweight + 1];// 动态规划填充 dp 数组for (int i = 1; i <= n; i++) {for (int j = 0; j <= bagweight; j++) {if (j < weight[i - 1]) {dp[i][j] = dp[i - 1][j]; // 不选择当前物品} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]); // 选择或不选择当前物品}}}// 输出最大价值System.out.println("最大价值: " + dp[n][bagweight]);// 回溯找到具体的物品List<Integer> selectedItems = new ArrayList<>();int i = n, j = bagweight;while (i > 0 && j > 0) {if (dp[i][j] != dp[i - 1][j]) {selectedItems.add(i - 1); // 物品索引从0开始j -= weight[i - 1];}i--;}// 输出选择的物品System.out.print("选择的物品: ");for (int item : selectedItems) {System.out.print(item + " (重量: " + weight[item] + ", 价值: " + value[item] + ") ");}System.out.println();}
}

完全背包问题

问题描述

完全背包问题与0-1背包问题类似,不同之处在于每个物品的数量不限,即你可以无限制地选择同一个物品。

解决方案

对于完全背包问题,我们需要稍微修改一下状态转移方程。由于每个物品都可以多次选择,因此需要在循环中考虑是否要加入该物品到背包中。

  1. 状态表示

    • dp[i][j] 表示前 i 种物品放入容量为 j 的背包里任意取的最大价值。
  2. 确定边界和遍历顺序

    • 先遍历背包重量 (内层),再遍历物品 (外层循环)。
      for(int i=1;i<=n;i++) // 物品数量for(int j=1;j<=m;j++) // 背包容量if(j>=w[i]) // 判断是否能放得下第i件物品dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); // 更新dp数组else dp[i][j]=dp[i-1][j]; // 不选第i件物品
  3. 找到状态转移方程

    • 状态转移方程是关键部分,它描述了如何从已知的状态推导出新的状态。
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
    • 这意味着,对于每一件物品,可以选择放进去或者不放,比较两种情况下所能获得的最大价值。

Java代码实现

package dp;import java.util.ArrayList;
import java.util.List;public class AllPack {public static void main(String[] args) {int n = 3; // 物品数量int bagweight = 7; // 背包最大容量int[] weight = {3, 4, 2}; // 物品重量int[] value = {4, 5, 3}; // 物品价值// 初始化 dp 数组int[][] dp = new int[n + 1][bagweight + 1];// 动态规划填充 dp 数组for (int i = 1; i <= n; i++) {for (int j = 0; j <= bagweight; j++) {dp[i][j] = dp[i - 1][j]; // 不选择当前物品if (j >= weight[i - 1]) {dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i - 1]] + value[i - 1]); // 选择或不选择当前物品}}}// 输出最大价值System.out.println("最大价值: " + dp[n][bagweight]);// 回溯找到具体的物品List<Integer> selectedItems = new ArrayList<>();int i = n, j = bagweight;while (i > 0 && j >= 0) {if (j >= weight[i - 1] && dp[i][j] != dp[i - 1][j]) {selectedItems.add(i - 1); // 物品索引从0开始j -= weight[i - 1];}i--;}// 输出选择的物品System.out.print("选择的物品: ");for (int item : selectedItems) {System.out.print(item + " (重量: " + weight[item] + ", 价值: " + value[item] + ") ");}System.out.println();}
}

  1. 0-1背包问题

    • 每个物品只能选择一次。
    • 回溯逻辑中,一旦确定选择了某个物品,就从当前的背包容量中减去该物品的重量,并且继续回溯下一个物品。
  2. 完全背包问题

    • 每个物品可以选择多次,直到背包容量不允许为止。
    • 回溯逻辑中,需要检查在当前背包容量下可以选择该物品的次数。这通常涉及到一个循环,直到背包容量不足以再添加一个该物品为止。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/471046.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

今日 AI 简报 | 开源 RAG 文本分块库、AI代理自动化软件开发框架、多模态统一生成框架、在线图像背景移除等

❤️ 如果你也关注大模型与 AI 的发展现状&#xff0c;且对大模型应用开发非常感兴趣&#xff0c;我会快速跟你分享最新的感兴趣的 AI 应用和热点信息&#xff0c;也会不定期分享自己的想法和开源实例&#xff0c;欢迎关注我哦&#xff01; &#x1f966; 微信公众号&#xff…

UniApp 应用、页面与组件的生命周期详解

UniApp 应用、页面与组件的生命周期详解 在uni-app中包含了 应用生命周期、页面生命周期、和组件生命周期&#xff08; Vue.js的&#xff09;函数。 应用生命周期 应用生命周期仅可在App.vue中监听&#xff0c;在其它页面监听无效。 <script>export default {onLaunc…

1111111111待修改--大流量分析(三)-BUUCTF

总结摘要 题目来来源URL https://buuoj.cn/challenges#%E5%A4%A7%E6%B5%81%E9%87%8F%E5%88%86%E6%9E%90%EF%BC%88%E4%B8%89%EF%BC%89 答题过程 这道题是看大佬写着说查找phpinfo&#xff0c;我现在也不知道为什么能够一下子就定位到这里了 这里先按照phpinfo进行&#xff…

PHP多门店医疗服务系统小程序源码

&#x1f3e5; 多门店医疗服务系统&#xff1a;打造全方位健康守护网络 &#x1f3e5; &#x1f3f7;️ 引言&#xff1a;为何需要多门店医疗服务系统&#xff1f; 在这个快节奏的时代&#xff0c;健康成为了我们最宝贵的财富。然而&#xff0c;面对突如其来的疾病或日常的健…

Jetpack 之 Ink API初探

前言 近期看到谷歌官方推文有一篇关于Jetpack Ink API的文章&#xff0c;随即进行了了解和研究&#xff0c;该SDK主要就是低延时的手写绘制&#xff0c;比如通过手指或者触控笔在安卓设备上面进行笔记记录或者在安卓设备上面进行素描之类类似于纸张上面的操作。当然了可能现在…

SpringBoot参数注解

SpringBoot参数注解 常用参数注解 RequestParmPathVariableRequestHeaderCookieValueRequestbody 1.请求参数注解&#xff1a;RequestParm 用途&#xff1a;用于将方法参数绑定到URI查询参数或者表单参数。他可以帮助我们或者HTTP请求中的参数值并将其作为方法的参数进行处…

HarmonyOS的@State装饰器的底层实现

HarmonyOS的State装饰器的底层实现 序言准备工作实现State装饰器 序言 ArkTS是鸿蒙生态的应用开发语言。它在保持TypeScript&#xff08;简称TS&#xff09;基本语法风格的基础上&#xff0c;进一步通过规范强化静态检查和分析&#xff0c;使得在程序运行之前的开发期能检测更…

C语言 | Leetcode C语言题解之第557题反转字符串中的单词III

题目&#xff1a; 题解&#xff1a; char* reverseWords(char* s) {int length strlen(s);char* ret (char*)malloc(sizeof(char) * (length 1));ret[length] 0;int i 0;while (i < length) {int start i;while (i < length && s[i] ! ) {i;}for (int p …

响应式网页设计--html

一&#xff0c;HTML 文档的基本结构 一个典型的 HTML 文档包含了几个主要部分&#xff0c;基本结构如下(本文以下出现的所有代码都可以套入下面示例进行测试)&#xff1a; <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8&q…

Linux git-bash配置

参考资料 命令提示符Windows下的Git Bash配置&#xff0c;提升你的终端操作体验WindowsTerminal添加git-bash 目录 一. git-bash配置1.1 解决中文乱码1.2 修改命令提示符 二. WindowsTerminal配置git-bash2.1 添加git-bash到WindowsTerminal2.2 解决删除时窗口闪烁问题 三. VS…

【HarmonyOS NEXT】一次开发多端部署(以轮播图、Tab栏、列表为例,配合栅格布局与媒体查询,进行 UI 的一多开发)

关键词&#xff1a;一多、响应式、媒体查询、栅格布局、断点、UI 随着设备形态的逐渐增多&#xff0c;应用界面适配也面临着很大问题&#xff0c;在以往的安卓应用开发过程中&#xff0c;往往需要重新开发一套适用于大屏展示的应用&#xff0c;耗时又耗力&#xff0c;而鸿蒙提供…

向日葵软件Windows系统连接苹果系统(MacOS)的无反应问题解决办法

前言 向日葵软件最近开始收费了的&#xff0c;打算收割我们。这也是没有办法的事情&#xff0c;毕竟他们的程序员也是需要吃饭的&#xff0c;我也表示理解。 所以&#xff0c;我在连接了几次发现反应很迟钝后&#xff0c;果断的买了158元的包年会员。 但是&#xff0c;在买了会…

neo4j desktop基本入门

下载安装不在赘述&#xff0c;本文只记述一些neo4j的基本入门操作 连接本地neo4j数据库 1. 点击ADD添加连接 端口一般是7687 账户名和密码忘记了&#xff0c;可以通过neo4j web&#xff08;默认为neo4jneo4j://localhost:7687/neo4j - Neo4j Browser&#xff09;重置密码 AL…

编写红绿起爆线指标(附带源码下载)

编写需求&#xff1a; 想问问有没有能标注行情起爆点的指标。 效果展示&#xff1a; 红线上&#xff0c;出现绿柱转红柱做多。 蓝线下&#xff0c;出现红柱转绿柱做空。 源码展示&#xff08;部分源码&#xff0c;完整源码需下载源码文件&#xff09;&#xff1a; IsMainIn…

ubuntu20.04 解决Pytorch默认安装CPU版本的问题

ubuntu20.04 解决Pytorch默认安装CPU版本的问题 在使用Anaconda安装支持CUDA的PyTorch版本时&#xff0c;遇到只能安装CPU版本的PyTorch是一个常见问题。这通常由于Anaconda环境配置、镜像源设置不当或版本匹配问题导致。以下是详尽的解决方案和步骤&#xff0c;以确保能够正确…

C++《继承》

在之前学习学习C类和对象时我们就初步了解到了C当中有三大特性&#xff0c;分别是封装、继承、多态&#xff0c;通过之前的学习我们已经了解了C的封装特性&#xff0c;那么接下来我们将继续学习另外的两大特性&#xff0c;在此将分为两个章节来分别讲解继承和多态。本篇就先来学…

数字孪生在智慧能源项目中的关键作用,你了解多少?

随着能源行业不断向智能化、数字化转型&#xff0c;数字孪生技术在智慧能源项目中扮演的角色愈发重要。数字孪生不仅带来了前所未有的资源优化和成本节约方式&#xff0c;还为整个能源系统的可持续运营奠定了坚实基础。那么&#xff0c;为什么数字孪生技术在智慧能源项目中如此…

Window下PHP安装最新sg11(php5.3-php8.3)

链接: https://pan.baidu.com/s/10yyqTJdwH_oQJnQtWcwIeA 提取码: qz8y 复制这段内容后打开百度网盘手机App&#xff0c;操作更方便哦 (链接失效联系L88467872) 1.下载后解压文件&#xff0c;将对应版本的ixed.xx.win文件放进php对应的ext目录下&#xff0c;如图所示 2.修改ph…

Postman上传图片如何处理

打开Postman&#xff0c;创建一个新的请求 URL: http://90.104.232.49:80/dev-api/appcommon/upload 如果有解密进入上传就在请求头添加 点击“Body”选项卡。 选择“form-data”类型。 在“KEY”列中输入文件字段的名称&#xff0c;例如file。 在“VALUE”列中&#xff0…

陪诊问诊APP开发实战:基于互联网医院系统源码的搭建详解

时下&#xff0c;开发一款功能全面、用户体验良好的陪诊问诊APP成为了医疗行业的一大热点。本文将结合互联网医院系统源码&#xff0c;详细解析陪诊问诊APP的开发过程&#xff0c;为开发者提供实用的开发方案与技术指导。 一、陪诊问诊APP的背景与功能需求 陪诊问诊APP核心目…