【算法设计实验三】动态规划解决01背包问题

请勿原模原样复制!

01背包dp具体解释详见链接 ↓  

【算法5.1】背包问题 - 01背包 (至多最大价值、至少最小价值)_背包问题求最小价值_Roye_ack的博客-CSDN博客

关于如何求出最优物品选择方案?

  • 先在递归求dp公式时,若进行【选择】则在决策表ck中标记ck[i][j]=1 
  • 遍历求完dp公式后,逆向遍历决策表,从最后一个物品开始,如果ck[i][j]=1且ck[i-1][j-w[i]]=1,则标记st[i]=st[i-1]=1

import java.util.*;public class hdjs {public static void main(String[] args){Scanner sc=new Scanner(System.in);System.out.println("请输入物品数量和背包容量!");int n=sc.nextInt(),m=sc.nextInt();int[] st=new int[n+1]; //记录最终物品选择情况int[][] ck=new int[n+1][m+1];  //记录物品选or不选决策情况int[] w=new int[n+1],v=new int[n+1];System.out.println("请依次输入物品重量!");for(int i=1;i<=n;i++) w[i]=sc.nextInt();System.out.println("请依次输入物品价值!");for(int i=1;i<=n;i++) v[i]=sc.nextInt();int[][] f=new int[n+1][1010]; //f[i][j] 选择前i个物品,体积不超过j的最大价值f[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){if(w[i]>j) //如果装不下该物品,则不选f[i][j]=f[i-1][j];else if(w[i]<=j) //如果可以装得下,则在求max(不选,选){if(f[i-1][j-w[i]]+v[i]>f[i-1][j]) ck[i][j]=1;f[i][j]=Math.max(f[i-1][j],f[i-1][j-w[i]]+v[i]);}}}//逆向追踪最优方案int k=m;for(int i=n;i>=1;i--)if(ck[i][k]==1){st[i]=1;k=k-w[i]; //判断减去该重量是否仍然为1}System.out.println("动态规划记录表如下!");for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)System.out.print(f[i][j]+" ");System.out.println();}System.out.println();System.out.println("物品最优选择情况如下!");for(int i=1;i<=n;i++) System.out.print(st[i]+" ");System.out.println();System.out.print("最大价值为"+f[n][m]);}
}

 

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

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

相关文章

Windows 安装 Docker

目录 前言安装 WSL2WSL2 简介系统要求安装步骤 安装 Docker Desktop下载安装验证 安装 Docker Compose结语开源项目 前言 下图展示了在 Windows 系统上安装 Docker&#xff0c;并利用Docker Compose一键搭建 youlai-mall 微服务商城所需的环境。本篇将先介绍 Windows 上如何安…

linux 系统调用流程分析

x86 1.系统调用 系统调用是用户空间程序与内核交互的主要机制。系统调用与普通函数调用不同&#xff0c;因为它调用的是内核里的代码。使用系统调用时&#xff0c;需要特殊指令以使处理器权限转换到内核态。另外&#xff0c;被调用的内核代码由系统调用号来标识&#xff0c;而…

树与二叉树堆:堆

堆的概念&#xff1a; 一般是把数组的数据在逻辑结构上看成一颗完全二叉树&#xff0c;如下图所示。 注意&#xff1a;别将C语言中的堆和数据结构的堆混为一谈&#xff0c;本文所讲的数据结构的堆是一种完全二叉树&#xff0c;而C语言中的堆其实是一种内存区域的划分 堆的分类…

VMware——WindowServer2012R2环境安装mysql5.7.14解压版_互为主从(图解版)

目录 一、服务器信息二、192.168.132.35服务器上安装mysql&#xff08;主&#xff09;2.1、环境变量配置2.2、安装2.2.1、修改配置文件内容2.2.2、初始化mysql并指定超级用户密码2.2.3、安装mysql服务2.2.4、启动mysql服务2.2.5、登录用户管理及密码修改2.2.6、开启远程访问 三…

docker更换国内源

docker更换国内源 1、编辑Docker配置文件 在终端中执行以下命令&#xff0c;编辑Docker配置文件&#xff1a; vi /etc/docker/daemon.json2、添加更新源 在打开的配置文件中&#xff0c;添加以下内容&#xff1a; {"registry-mirrors": ["https://hub-mirror…

gitlab环境准备

1.准备环境 gitlab只支持linux系统&#xff0c;本人在虚拟机下使用Ubuntu作为操作系统&#xff0c;gitlab镜像要使用和操作系统版本对应的版本&#xff0c;(ubuntu18.04,gitlab-ce_13.2.3-ce.0_amd64 .deb) book100ask:/$ lsb_release -a No LSB modules are available. Dist…

03-瑞吉外卖关于菜品/套餐分类表的增删改查

新增菜品/套餐分类 页面原型 当我们在后台系统中添加菜品/套餐时,需要选择一个菜品/套餐分类,在移动端也会按照菜品分类和套餐分类来展示对应的菜品和套餐 第一步: 用户点击确定按钮执行submitForm函数发送Ajax请求,将新增菜品/套餐表单中输入的数据以json形式提交给服务端,…

算法分析与设计课后练习22

设W(5,7,10,12,15,18,20)和M35&#xff0c;使用过程SUMOFSUB找出W种使得和数等于M的全部子集并画出所生成的部分状态空间树

CV计算机视觉每日开源代码Paper with code速览-2023.11.16

点击CV计算机视觉&#xff0c;关注更多CV干货 论文已打包&#xff0c;点击进入—>下载界面 点击加入—>CV计算机视觉交流群 1.【基础网络架构】ConvNet vs Transformer, Supervised vs CLIP: Beyond ImageNet Accuracy 论文地址&#xff1a;https://arxiv.org//pdf/23…

数据分析思维与模型:多维度拆解分析法

多维度拆解分析法"&#xff08;Multi-Dimensional Analysis and Decomposition Method&#xff09;是一种用于深入分析和解决复杂问题的方法论。这种方法侧重于从多个角度或维度来考察问题&#xff0c;以便于更全面地理解和解决它们。它通常包括以下几个步骤&#xff1a; …

环保回收信息展示预约小程序的效果如何

人们每天在线上的时间非常多&#xff0c;他们会通过线上寻找信息&#xff0c;而环保回收企业也在通过线上寻找客户&#xff0c;但受限于平台限制&#xff0c;无论引流获客还是营销互动、或是数据分析及全面管理方面都面对难题&#xff0c;其中微信/百度/快手/抖音/支付宝/快手等…

我在CSDN开组会1-蒙特卡洛模拟在矿床学的应用展望

各位老师、同学们&#xff0c;大家好。今天组会的内容是蒙特卡洛模拟在矿床学的应用展望。 为什么要讲蒙特卡洛模拟呢&#xff0c;因为我发现在地质学方面已经有不少应用&#xff0c;但是蒙特卡洛模拟延伸的知识太晦涩了&#xff0c;劝退了很多探究者们。因此&#xff0c;计划…

DSP介绍及CCS

文章目录 CCS版本编译器CCS使用注意严禁中文 CCS的基本操作新建工程导入现有工程调整字体的大小工程界面恢复标签的使用 仿真盒小虫子进入在线Debug 芯片TMS320F28355基本介绍特性 DSP中特殊指令dsp指令中的EALLOW EDIS CCS TI官网 版本 CCS版本&#xff1a; CCS8.3.1.0004_…

腾讯云HAI域AI作画

目录 &#x1f433;前言&#xff1a; &#x1f680;了解高性能应用服务 HAI &#x1f47b;即插即用 轻松上手 &#x1f47b;横向对比 青出于蓝 &#x1f424;应用场景-AI作画 &#x1f424;应用场景-AI对话 &#x1f424;应用场景-算法研发 &#x1f680;使用HAI进行…

Web 自动化神器 TestCafe—页面基本操作篇

前 言 Testcafe是基于node.js的框架&#xff0c;以操作简洁著称&#xff0c;是web自动化的神器 今天主要给大家介绍一下testcafe这个框架和页面元素交互的方法。 一、互动要求 使用 TestCafe 与元素进行交互操作&#xff0c;元素需满足以下条件&#xff1a;☟ 元素在 body 页…

怎么让NetCore接口支持Json参数

项目&#xff1a;NetCore Web API 接口支持Json参数需要安装Newtonsoft.Json.Linq和Microsoft.AspNetCore.Mvc.NewtonsoftJson Program代码 //支持json需要安装Microsoft.AspNetCore.Mvc.NewtonsoftJson using Newtonsoft.Json.Serialization;var builder WebApplication.Cr…

【Seata源码学习 】篇三 TM开启全局事务的过程

【Seata源码学习 】篇三 TM开启全局事务的过程 TM发送 单个或批量 消息 以发送GlobalBeginRequest消息为例 TM在执行拦截器链路前将向TC发送GlobalBeginRequest 消息 io.seata.tm.api.DefaultGlobalTransaction#begin(int, java.lang.String) Overridepublic String begin(…

媲美有线操作,支持4KHz响应和无线充电的游戏鼠标,雷柏VT3S上手

对于无线鼠标来说&#xff0c;操作延迟和精度对游戏操作影响很大&#xff0c;常见的游戏鼠标至少都有1KHz的回报率&#xff0c;而雷柏今年已经出了很多支持4KHz回报的鼠标了&#xff0c;像是我现在用的这款VT3S游戏鼠标&#xff0c;就搭载了旗舰级的原相3395引擎&#xff0c;支…

git撤销未git commit的文件

目录 一、问题描述 二、方式1&#xff1a;git命令撤销&#xff08;更专业&#xff09; 1、文件已git add&#xff0c;未git commit 2、本地修改&#xff0c;未git add &#xff08;1&#xff09;撤销处于unstage的文件&#xff0c;即删除已有变动 &#xff08;2&#xff…

netty整合websocket(完美教程)

websocket的介绍&#xff1a; WebSocket是一种在网络通信中的协议&#xff0c;它是独立于HTTP协议的。该协议基于TCP/IP协议&#xff0c;可以提供双向通讯并保有状态。这意味着客户端和服务器可以进行实时响应&#xff0c;并且这种响应是双向的。WebSocket协议端口通常是80&am…