技术标签： dp
题意：每一组物品都有一个盒子，要买该组的物品必须先要买盒子，问能够获得的价值最大是多少。
解题思路：这题有点像分组背包，但是每一组里面要买物品必须要先买盒子。其实我的想法还是和分组背包的思路一样，只是把盒子看成一个单独的物品，dp[i][j]表示前i组物品，容量为j时的最大价值。为了防止盒子没有买就买了这一组的物品，我们最开始的dp[i][j]赋值为-1，在该组里做一次01背包，同样，还是需要做一次分类，该组里面的物品是第一个放入的还是之前已放入过其他物品。但如果认为这样就完成任务了，那么就game over了，如果该组没有一个放入背包，那么dp[i]的所有值都会为-1，连之前的状态都会丢失，所以还要把之前的值复制过来。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,box[55],cost[55][11],value[55][11];
int dp[55][100005],num[55];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,-1,sizeof(dp));
memset(dp[0],0,sizeof(dp[0]));
for(int i = 1; i <= n; i++)
{
scanf("%d",&box[i]);
scanf("%d",&num[i]);
for(int j = 1; j <= num[i]; j++)
scanf("%d%d",&cost[i][j],&value[i][j]);
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= num[i]; j++)
for(int v = m; v >= cost[i][j]; v--)
{
if(dp[i][v-cost[i][j]] != -1) //之前就放过物品了，直接01背包
dp[i][v] = max(dp[i][v],dp[i][v-cost[i][j]]+value[i][j]);
if(v >= box[i] + cost[i][j]) //该组里面第一个放入背包的物品
{
if(dp[i-1][v-box[i]-cost[i][j]] != -1)
dp[i][v] = max(dp[i][v],dp[i-1][v-box[i]-cost[i][j]]+value[i][j]);
}
}
for(int v = 0; v <= m; v++)
dp[i][v] = max(dp[i][v],dp[i-1][v]);
}
printf("%d\n",dp[n][m]);
}
return 0;
}文章浏览阅读123次。概述 您可能有大量应用程序产生的JSON数据，您可能需要对这些JSON数据进行整理，去除不想要的字段，或者只保留想要的字段，或者仅仅是进行数据查询。 那么，利用阿里云Data Lake Analytics或许是目前能找到的云上最为便捷的达到这一目标的服务了。仅仅需要3步，就可以完成对海量..._什么云服务可以直接存储json数据
文章浏览阅读413次。diff 算法 虚拟dom 理论_react diff 面试题
文章浏览阅读1.2w次，点赞23次，收藏104次。文章目录前言从传统学习引出元学习对比机器学习和元学习如何实现元学习参考链接前言元学习Meta Learning，含义为学会学习，即learn to learn，带着对人类的“学习能力”的期望诞生的。Meta Learning希望使得模型获取一种 “学会学习” 的能力，使其可以在获取已有“知识”的基础上快速学习新的任务。从传统学习引出元学习传统的机器学习方法是针对一个特定的，一般是有大量数据的数据集 ，试图学习出一个预测模型 ，使得模型对于测试集上的数据的预测有最小的误差。这个思路在数据集 D_meta learning
文章浏览阅读362次。一、类型相关操作1.type函数理解：type(数据)获取指定数据类型例如：type(100) #直接输入是不会打印,需要printprint(type(100)) #整型(int) #得出结果：100print(type(1.25)) #浮点型(float) #得出结果：1.25print(type('陈某某')) #字符串(str) #得出结果：陈某某print(type(10>20)) #布尔(bool) _type({100})
文章浏览阅读798次。在运行idea时常常提示端口被占用，在cmd查询该端口，但显示端口没有被占用怎么办？_unable to open debugger port 12208
文章浏览阅读312次。docker不容置疑，目前最为成熟最广泛的虚拟容器产品，虽然k8s在docker编排基础上，基于战略原因，协同google，ibm推出了CRI标准，兼容一切符合CRI标准的容器厂商，而带动了podman等其他容器产品的百花齐放，但是docker依然在诸多的容器产品里鹤立鸡群，强就是强，无惧大厂商的霸权，今天这里谈谈docker使用里查看容器启动命令的一个工具。runcommandruncommand是一款使用golang实现的基于容器管理的工具，市面上也有一些同类产品的实现，比如笔者我，在没有开发runco_docker joinsunsoft
文章浏览阅读7.9w次，点赞53次，收藏235次。若该文为原创文章，未经允许不得转载原博主博客地址：https://blog.csdn.net/qq21497936本文章博客地址：https://blog.csdn.net/qq21497936/article/details/94585803目录前话相关博客QGLWidget概述QGLWidget子类示例更新绘制覆盖层绘制技术线程方案一：在线程中进..._qt 用qopenglwidget生成release版,依赖什么库
文章浏览阅读5.3k次。C 语言的浮点数类型_c语言float和double保留小数点后几位
文章浏览阅读3k次，点赞4次，收藏2次。gradle 打包时报以下错误：二、解决方法在 build.gradle 文件中找到 http://mirrors.huaweicloud.com/repository/maven/ 所在的位置，增加 allowInsecureProtocol = true 一行：_gradle using insecure protocols with repositories, without explicit opt-in,
文章浏览阅读7.3k次。微信群,请扫描二维码加入 本人在北京，主场北京,位置不限, 仅限java行业交流，C C##以及python请另外加群，谢谢欢迎准 java行业的进入，杜绝假冒程序员加入，精兵简政群内与java无关私事请私聊,任何java的问题,欢迎讨论——————————————————————————————————如若二维码失效，请加微信拉群..._java开发接单群
文章浏览阅读3.7k次，点赞2次，收藏43次。一、数据库系统概述数据库的四个基本概念：数据、数据库、数据库管理系统、数据库系统：1、数据：描述事物的符号记录称为数据。 （1）、数据是数据库中存储的基本对象。 （2）、数据是分类型的。 （3）、数据的含义称为数据的语义，数据与其语义是不可分的。 2、数据库：数据库是长期储存在计算机内、有组织的、可共享的大量数..._系统的数据管理逻辑
文章浏览阅读315次。java.sql.SQLException: The server time zone value ‘�й���ʱ��’ is unrecognized or represents more than one time zone. You must configure either the server or JDBC driver (via the serverTimezone configuration property) to use a more specifc time zone value i_mybatis plus servertimezone=gmt+8未生效 原因