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

OpenJudge_ 简单英文题_04:0/1 Knapsack

题目

描述
Given the weights and values of N items, put a subset of items into a knapsack of capacity C to get the maximum total value in the knapsack. The total weight of items in the knapsack does not exceed C.

输入
First line: two positive integers N (N <= 100) and C (C <= 1000).
Second line: N positive integers w[i] (w[i] <= 1000), indicating the weight of the i-th item.
Third line: N positive integers v[i] (v[i] <= 1000), indicating the value of the i-th item.
输出
One line contains several integers, indicating the indexes of the selected items.
样例输入
5 10
2 4 6 2 5
1 3 4 2 8
样例输出
2
5

翻译

题目:
0/1背包
描述:
给定N个物品的权重和值,将一个子集的物品放入容量为C的背包中,以获得背包中的最大总值。背包中物品的总重量不超过C。
输入:
第一行:两个正整数N(N<=100)和C(C<=1000)。
第二行:N个正整数w[i](w[i]<=1000),表示第i个项目的权重。
第三行:N个正整数v[i](v[i]<=1000),表示第i项的值。
输出:
一行包含几个整数,表示所选项目的索引。

代码

#include <bits/stdc++.h>
using namespace std;
int n,//物品数量
c,//背包容量
w[1001],//每物品重量
v[1001],//每物品价值
f[101][1001];//多少重量时对应的最大价值
/*
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
f[几个物品][重量]=最大(f[不要该物品][同样重量],f[不要该物品][重量-该物品重量]+该物品价值);
没有该重量时的最大价值+该物品价值。
*/
struct node{
int i,j;
}p[101][1001]; //该物品的上个物品
void view(){//观察数据
cout<<“数据:\n”;
cout<<“重量\t\t”;for(int j=0;j<=c;j++)cout<<j<<“\t”;cout<<endl;
for(int i=1;i<=n;i++){
cout<<i<<“:\t”<<w[i]<<“,”<<v[i]<<“\t”;for(int j=0;j<=c;j++)cout<<f[i][j]<<“\t”;cout<<endl;
cout<<“\t\t”;for(int j=0;j<=c;j++)cout<<p[i][j].i<<“,”<<p[i][j].j<<“\t”;cout<<endl;
}
cout<<endl;
}
int main(){
//freopen(“data.cpp”,“r”,stdin);
cin>>n>>c;
//cout<<“物品数量”<<n<<“\t背包容量”<<c<<endl;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=1;i<=n;i++)//行,各物品
for(int j=0;j<=c;j++){//列,每重量
f[i][j]=f[i-1][j];//该重量时能取得的最大价值可以初步认定为不用该物品就取得的最大价值
p[i][j]=node{i-1,j};
if(j>=w[i])//如果重量超过该物品的重量,可以考虑用该物品
if(f[i][j]<f[i-1][j-w[i]]+v[i]){//不用该物品(i-1)不算该物品重量(j-w[i])时取得的最大价值上+该物品的价值
f[i][j]=f[i-1][j-w[i]]+v[i];
p[i][j]=node{i-1,j-w[i]};
}
}
//view();
stack s;
int pi=n,pj=c;
while(f[pi][pj]!=0){//只要有价值就算
node px=p[pi][pj];//找到前一状态
if(pj!=px.j)s.push(pi);//如果两状态的重量一样就不算。
pi=px.i,pj=px.j;
}
while(!s.empty()){//逆序输出采用的各物品
cout<<s.top()<<endl;s.pop();
}
return 0;
}

小结

动态规划就怕画表格,画完表格就清楚了。
初始状态是怎样,随着阶段的变化状态怎样变化。
然后就能找到动态转移方程。

相关文章:

OpenJudge_ 简单英文题_04:0/1 Knapsack

题目 描述 Given the weights and values of N items, put a subset of items into a knapsack of capacity C to get the maximum total value in the knapsack. The total weight of items in the knapsack does not exceed C. 输入 First line: two positive integers N (…...

深入探索离散 Hopfield 神经网络

一、离散 Hopfield 神经网络的起源与发展 离散 Hopfield 神经网络由约翰・霍普菲尔德在 1982 年提出&#xff0c;这一创新性的成果在当时引起了广泛关注&#xff0c;成为早期人工神经网络的重要代表之一。 在那个时期&#xff0c;人工神经网络的发展还处于相对初级的阶段。霍…...

[智能车摄像头是一种安装在汽车上用于辅助驾驶和提高安全性的重要设备]

智能车摄像头是一种安装在汽车上用于辅助驾驶和提高安全性的重要设备。它们通常包括几个不同类型&#xff0c;如前视摄像头、环视摄像头、行车记录仪等。这些摄像头的主要功能有&#xff1a; 前视摄像头&#xff08;Forward Camera&#xff09;&#xff1a;用于提供驾驶员前方…...

前端vue 列表中回显并下拉选择修改标签

1&#xff0c;vue数据列表中进行回显状态并可以在下拉框中选择修改&#xff0c;效果如下 2&#xff0c;vue 页面关键代码 <el-table-column label"审核" align"center" class-name"small-padding fixed-width" prop"status" >&…...

hbase未来的发展趋势

HBase 作为一个开源的分布式、可伸缩的 NoSQL 数据库,依托于 Hadoop 生态系统,以处理海量结构化数据为优势。随着大数据技术的发展,HBase 的发展趋势主要体现在以下几个方面: 1. 与云计算深度集成 随着企业向云迁移,HBase 也正在越来越多地部署在云环境中。云服务商(如 …...

Rust 语言学习笔记(二)

再继续快速学习一下 Rust 的以下几个知识点&#xff0c;就可以开始着手做点小工具了 基本数据类型复合数据类型基本的流程控制 Rust 设计为有效使用内存考虑的&#xff0c;它提供了非常细力度的数据类型&#xff0c;如整数分为有无符号&#xff0c;宽度从 8 位到 128 位&…...

【postman】怎么通过curl看请求报什么错

获取现成的curl方式&#xff1a; 1&#xff0c;拿别人给的curl 2&#xff0c;手机app界面通过charles抓包&#xff0c;点击接口复制curl 3&#xff0c;浏览器界面-开发者工具-选中接口复制curl 拿到curl之后打开postman&#xff0c;点击import&#xff0c;粘贴curl点击send&am…...

Python 编程入门指南(一)

1. Python 简介 Python是一种广泛使用的高级编程语言,因其简洁的语法和强大的功能而备受欢迎。Python由Guido van Rossum于20世纪90年代初设计,旨在提供易于阅读和编写的代码,适合从初学者到专业开发者的各个水平。它是一种解释型语言,这意味着在编写和执行代码之间不需要…...

macOS 设置固定IP

文章目录 以太网Wifi![请添加图片描述](https://i-blog.csdnimg.cn/direct/65546e966cae4b2fa93ec9f0f87009d8.png) 基于 macOS 15.1 以太网 Wifi...

redis实现消息队列的几种方式

一、了解 众所周知&#xff0c;redis是我们日常开发过程中使用最多的非关系型数据库&#xff0c;也是消息中间件。实际上除了常用的rabbitmq、rocketmq、kafka消息队列&#xff08;大家自己下去研究吧~模式都是通用的&#xff09;&#xff0c;我们也能使用redis实现消息队列。…...

debian 系统更新升级

系统升级能够有效避免漏洞导致的损害 不过需要做好提前和后续的测试&#xff0c;避免现有运行程序的错误。 debian安装参考&#xff1a;链接 一、清理过时和不再使用的源 1.清理源 vi /etc/apt/sources.list2.在下面的文件夹下清理不需要的 cd /etc/apt/sources.list.d二、…...

STM32学习笔记-----UART的概念

在 STM32 中&#xff0c;UART&#xff08;Universal Asynchronous Receiver/Transmitter&#xff09;是一种常用的串行通信接口&#xff0c;广泛应用于嵌入式系统中。STM32 提供了丰富的硬件资源来支持 UART 通信&#xff0c;可以通过标准库&#xff08;STM32 HAL 或者标准外设…...

Pytest-Bdd-Playwright 系列教程(9):datatable 参数的使用

Pytest-Bdd-Playwright 系列教程&#xff08;9&#xff09;&#xff1a;datatable 参数的使用 前言一、什么是 datatable 参数&#xff1f;Gherkin 表格示例 二、datatable 参数的基本使用feature文件&#xff1a;获取用户信息并执行相关操作的使用 datatable 处理表格数据Give…...

【408】SDN重点笔记

总特征&#xff1a;数据平面&#xff08;负责转发&#xff09;与控制平面&#xff08;负责控制&#xff09;分离 控制平面&#xff1a; 由服务器和软件组成。控制平面完成转发表&#xff0c;并分发。 路由器不再需要路由选择协议&#xff0c;不再交换信息&#xff0c;只负责收到…...

云运维基础

笔记内容侵权联系删除 云审计&#xff08;CTS&#xff09; 云审计云上资源变更均可被管控&#xff0c;实时系统性记录所有人的操作&#xff0c;无需手工统计。云审计服务支持将操作记录合并&#xff0c;周期性地生成事件文件实时同步转存到OBS存储桶&#xff0c;帮助用户实现…...

基于微信小程序的平安驾校预约平台的设计与实现(源码+LW++远程调试+代码讲解等)

摘 要 互联网发展至今&#xff0c;广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对高校教师成果信息管理混乱&#xff0c;出错率高&#xff0c;信息安全性差&#xff0c;劳动强度大&#xff0c;费时费力…...

Rust开发一个命令行工具(一,简单版持续更新)

依赖的包 cargo add clap --features derive clap命令行参数解析 项目目录 代码 main.rs mod utils;use clap::Parser; use utils::{editor::open_in_vscode,fs_tools::{file_exists, get_file, is_dir, list_dir, read_file}, }; /// 在文件中搜索模式并显示包含它的行。…...

实战:深入探讨 MySQL 和 SQL Server 全文索引的使用及其弊端

在数据库中处理大量文本数据时,包含搜索(例如查找包含特定单词的文本)往往是必需的。然而,直接使用 LIKE %text% 的方式在大数据量中进行模糊查询会造成性能瓶颈。为了解决这一问题,MySQL 和 SQL Server 提供了全文索引(Full-Text Indexing)功能,可以显著加速文本数据的…...

情景2 虚拟化世界 自己答案的理解

1、什么是虚拟化&#xff1f; 答:版本很多&#xff0c;选了两个作为参考。 定义1&#xff1a;虚拟化是创造设备或者资源的虚拟版本&#xff0c;如服务器、存储设备、网络或者操作系统。 定义2&#xff1a;虚拟化是资源的逻辑表示&#xff0c;它不受物理限制的约束。 2、寄生…...

【国产操作系统对Qt支持有哪些?】

国产操作系统 鸿蒙操作系统:由华为开发,主要用于智能设备和物联网领域。 深度操作系统:基于Linux的操作系统,适用于个人电脑和服务器。 中标麒麟:由中国电子科技集团公司研发,适用于服务器和桌面环境。 悠然操作系统:面向教育和个人用户的Linux发行版。 红旗Linux:早期…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...