首页 > 其他分享 >P1776 宝物筛选

P1776 宝物筛选

时间:2024-04-04 12:22:30浏览次数:18  
标签:int 二进制 P1776 拆分 new 筛选 include 宝物 dp

知识点:多重背包,也就是一个物品有多个,然后求总价值。
算法竞赛上的板子题目:

链接:https://www.luogu.com.cn/problem/P1776
介绍二进制拆分优化
就是把几个完全相同的拆成1+2+4+...+2^n+mod,然后再进行dp的办法
代码:
重点在new_n,new_w,new_m这几个

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef unsigned long long ll;
using namespace std;

const int N = 1e5 + 10;
int n, C, dp[N], w[N], c[N], m[N];
int new_n;//二进制拆分后的新物品总数量
int new_w[N], new_c[N], new_m[N];//二进制拆分后的新物品
int main()
{
	cin >> n >> C;
	for (int i = 1; i < n + 1; i++)cin >> w[i] >> c[i] >> m[i];//价值,重量,数量
	new_n = 0;
	//二进制拆分
	for (int i = 1; i <= n; i++)
	{
		//这里就是利用二进制的思想:把一个数拆成以最小二进制和它的余数表示:
		//如把25 = 1 + 2 + 4 + 8 + 10
		//意思就是把25个i物体看成1、2、4、8、10个物体的集合
		for (int j = 1; j <= m[i]; j <<= 1)
		{
			m[i] -= j;
			new_c[++new_n] = j * c[i];
			new_w[new_n] = j * w[i];
		}
		if (m[i])
		{
			new_c[++new_n] = m[i] * c[i];
			new_w[new_n] = m[i] * w[i];
		}
	}
	//滚动数组版本的0/1背包
	for (int i = 1; i <= new_n; i++)
		for (int j = C; j >= new_c[i]; j--)//枚举背包容量
			dp[j] = max(dp[j], dp[j - new_c[i]] + new_w[i]);
	cout << dp[C];
	return 0;
}

标签:int,二进制,P1776,拆分,new,筛选,include,宝物,dp
From: https://www.cnblogs.com/zzzsacmblog/p/18114066

相关文章

  • 根据一个数组筛选另一个数组的数据,组合成一个新数组
    这段代码定义了两个数组:fixedArray包含国家信息的固定数组,flowArray包含需要筛选的国家代码。然后使用filter方法筛选fixedArray中包含在flowArray中的元素,返回新的数组newArray。最后打印筛选后的新数组。//定义一个包含国家信息的固定数组letfixedArray=[......
  • Applescript实现无痕检测是否注册iMessage服务,iMessages数据筛选,iMessage蓝号检测完
    一、实现iMessage蓝号数据筛选的两种方式:1.人工筛选,将要验证的号码输出到文件中,以逗号分隔。再将文件中的号码粘贴到iMessage客户端的地址栏,iMessage客户端会自动逐个检验该号码是否为iMessage账号,检验速度视网速而定。红色表示不是iMessage账号,蓝色表示iMessage账号。2.编写脚......
  • Finereport11 类Excel筛选
    微信公众号:次世代数据技术关注可了解更多的教程。问题或建议,请公众号留言或联系本人;微信号:weibw162本教程视频讲解可以关注本人B站账号进行观看:weibw162一、需求描述在使用FIneReport软件开发时,我们希望前台报表展示时可以类似Excel表格筛选那样,在表头进行多选筛选过滤显......
  • elementUI表单表头增加筛选
    1、增加过滤条件 2、定义数据,必须包含text以及value 3、使筛选的id与行内元素id一直进行筛选 4、对下拉icon大小更改 ......
  • python + xlwings 根据条件筛选Excel里的所需资料
    实际有用,有效,满足我的个人需要。点击查看代码importxlwingsasxwdeffiler():try:app=xw.App(visible=False,add_book=False)app2=xw.App(visible=False,add_book=True)wb=app.books.open('new_file.xlsx')#打开原始数据表......
  • AI金融预测领域综述文章筛选,附论文及代码链接,2021年版
    21年的综述最近读了3篇,总结笔记如下:(2021)SystematicLiteratureReview:StockPricePredictionUsingMachineLearningandDeepLearning评价:原文不值得看,精华是下面那4篇论文。但这篇综述的写法比较典型,都是先描述问题,搜解决策略(按关键字搜、按数据源搜比如某个领域的期刊),......
  • react 开发一个 类似于条件筛选的组件 如下
     最终效果: 记录一下其中要点: 1.react 的数据被useState后,都不允许直接修改,都需要使用hooks才可以修改       2. useState必须要放到组件渲染函数中     3. 在jsx中不允许使用if 除了三元运算符和isChecked为真假来做标识符外......
  • sql语句基础语法之 数据表的添加相关 ​字段相关操作 ​数据筛选相关操作 ​数据排序
    3月18日数据表的筛选数据,字段操作,聚合函数内容如下:​数据表的添加相关​字段相关操作​数据筛选相关操作​数据排序相关操作​聚合函数数据表的添加相关usemydb;createtableclass_img(`id`intuniquekeyauto_incrementcomment'序号',`grade`i......
  • 小型研发型企业,如何筛选合适的内外网数据交换方案?
    研发型企业是社会经济发展的重要组成,研发型企业是一种以研发创新为主要驱动力的企业。这些企业主要注重技术创新和产品研发,致力于将新的科技成果转化为市场竞争力。它们通常拥有强大的研发团队和研发设施,投入大量资源用于技术研究和产品开发。研发型企业的核心竞争力来自于科学技......
  • 筛选器Filter
    参考:https://learn.microsoft.com/zh-cn/aspnet/core/mvc/controllers/filters?view=aspnetcore-6.01、什么是筛选器通过使用ASP.NETCore中的筛选器,可在请求处理管道中的特定阶段之前或之后运行代码。可以创建自定义筛选器,用于处理横切关注点。横切关注点的示例包括错误处......