目录
来源：购物单_牛客题霸_牛客网
该题类似于0-1背包问题，关于0-1背包请看0-1背包-动态规划算法_哔哩哔哩_bilibili
1、购买附件必须买主件，且一个主件最多有两个附件，每件物品只能购买一次；
2、每件物品有三个属性：价格v、重要度p、是主件还是附件q，满意度是价格v和重要度p的数学期望，q为该附件所属主件的编号，q=0表示该物品是主件；
3、手中有N元钱，要买m件物品，使得产生的满意度最大。
该题与0-1背包相比，难点在于该题有附件关联着，买附件还必须要买主件，有四种情况要讨论：
1、只买主件；
2、买主件+附件一；
3、买主件+附件二；
4、买主件+附件一+附件二；
因为一个主件最多有两个不同的附件，因此两个附件要分开讨论，那么我们遍历物品的时候，可以略过附件，只在买主件的时候考虑附件的情况。
包含上述所说的三个属性v、p、q，另外为了区分附件一和附件二，再加两个属性a1和a2分别代表附件一和附件二，初始化为0表示为主件，并生成相应的set方法，方便对a1和a2进行修改，生成有参构造，以便对物品初始化，toString方法是为了方便调试。
class Goods {
int v; //价格
int p; //重要度
int q; //是否为附件
int a1 = 0, a2 = 0;
public Goods(int v, int p, int q) {
this.v = v;
this.p = p;
this.q = q;
}
@Override
public String toString() {
return "Goods{" +
"v=" + v +
", p=" + p +
", q=" + q +
", a1=" + a1 +
", a2=" + a2 +
'}';
}
public void setA1(int a1) {
this.a1 = a1;
}
public void setA2(int a2) {
this.a2 = a2;
}
}新建方法maxValueShop(int[][] list, int N)，传入控制台输入的参数，list为代表物品的二维数组，N为预算，也就是手中拥有的钱数，首先对接收的物品信息作初始化，新建一维数组v[]、p[]、q[]接收对应的值，list[i][0]表示价格放入v[]中，list[i][1]表示重要度放入p[]中，list[i][2]表示是主件还是附件放入q[]中，类似于0-1背包，三个数组新建的时候，长度要比物品数量大1，因为有一个0作为初始值，同样物品类数组goods[]长度也要大1，用以上的三个数组来构造物品类，因为刚刚构造的物品类主件都不包含附件a1和a2，需要对a1和a2进行初始化，以上实现代码如下：
public static int maxValueShop(int[][] list, int N) {
int len = list.length;
int[] v = new int[len + 1];
int[] p = new int[len + 1];
int[] q = new int[len + 1];
Goods[] goods = new Goods[len + 1];
//初始化v，p，q，goods
goods[0] = new Goods(0,0,0);
for (int i = 1; i < len + 1; i++) {
v[i] = list[i - 1][0];
p[i] = list[i - 1][1];
q[i] = list[i - 1][2];
goods[i] = new Goods(v[i], p[i], q[i]);
}
//对附件进行处理，如果该物品是附件，那么将该附件对应到主件上去
for (int i = 1; i < len + 1; i++) {
if (goods[i].q > 0) {
if (goods[goods[i].q].a1 == 0) {
goods[goods[i].q].setA1(i);
}else if (goods[goods[i].q].a2 == 0) {
goods[goods[i].q].setA2(i);
}
}
}
}初始化完成之后，就要做动态规划真正要做的事情了，首先定义二维数组dp[i][j]表示的涵义是：手中有j元时，买第i件物品时达到的最大满意度是dp[i][j]，因此有如下的公式：
解释：
a.当前物品为附件时，直接跳过，即不买，dp[i][j]=dp[i-1][j]；
b.当前物品为主件时，只考虑主件不考虑附件，dp[i][j]=max{dp[i-1][j],dp[i-1][j-price]+satisfy}，这里的price为主件的价格，即goods[i].v,satisfy为主件的满意度，即goods[i].v*goods[i].p；
c.当前物品为主件时，考虑买主件+附件1，dp[i][j]=max{dp[i-1][j],dp[i-1][j-price1]+satisfy1}，这里的price1为主件的价格+附件1的价格，即goods[i].v+goods[goods[i].a1].v,satisfy1为主件的满意度+附件1的满意度，即goods[i].v*goods[i].p+goods[goods[i].a1].v*goods[goods[i].a1].p；
d.当前物品为主件时，考虑买主件+附件2，dp[i][j]=max{dp[i-1][j],dp[i-1][j-price2]+satisfy2}，这里的price2为主件的价格+附件2的价格，即goods[i].v+goods[goods[i].a2].v,satisfy2为主件的满意度+附件2的满意度，即goods[i].v*goods[i].p+goods[goods[i].a2].v*goods[goods[i].a2].p；
e.当前物品为主件时，考虑买主件+附件1+附件2，dp[i][j]=max{dp[i-1][j],dp[i-1][j-price3]+satisfy3}，这里的price3为主件的价格+附件1的价格+附件2的价格，即goods[i].v+goods[goods[i].a1].v+goods[goods[i].a2].v,satisfy3为主件的满意度+附件2的满意度，即goods[i].v*goods[i].p+goods[goods[i].a1].v*goods[goods[i].a1].p+goods[goods[i].a2].v*goods[goods[i].a2].p；
那么代码如下：
//dp[i][j]代表的是：手中有j元时，买第i件物品时达到的最大满意度是dp[i][j]
int[][] dp = new int[len + 1][N + 1];
for (int i = 1; i < len + 1; i++) {
int price = 0, price1 = 0, price2 = 0, price3 = 0;
int satisfy = 0, satisfy1 = 0, satisfy2 = 0, satisfy3 = 0;
//只考虑主件
price = goods[i].v;
satisfy = goods[i].v * goods[i].p;
//买主件+附件一
if (goods[i].a1 > 0) {
price1 = goods[goods[i].a1].v + price;
satisfy1 = goods[goods[i].a1].v * goods[goods[i].a1].p + satisfy;
}
//买主件+附件二
if (goods[i].a2 > 0 ) {
price2 = goods[goods[i].a2].v + price;
satisfy2 = goods[goods[i].a2].v * goods[goods[i].a2].p + satisfy;
}
//买主件+附件一+附件二
if (goods[i].a1 > 0 && goods[i].a2 > 0) {
price3 = goods[goods[i].a1].v + goods[goods[i].a2].v + price;
satisfy3 = goods[goods[i].a1].v * goods[goods[i].a1].p + goods[goods[i].a2].v * goods[goods[i].a2].p + satisfy;
}
//对dp进行赋值（填充表格）
for (int j = 1; j <= N; j++) {
if (goods[i].q > 0) { //跳过附件
dp[i][j] = dp[i - 1][j];
} else {
//只买主件，对应上面price和satisfy
if (j >= price && price != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - price] + satisfy);
}
//买主件+附件一，对应上面price1和satisfy1
if (j >= price1 && price1 != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - price1] + satisfy1);
}
//买主件+附件二，对应上面price2和satisfy2
if (j >= price2 && price2 != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - price2] + satisfy2);
}
//买主件+附件一+附件二，对应上面price3和satisfy3
if (j >= price3 && price3 != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - price3] + satisfy3);
}
}
}
}但是这个代码有点问题，不知道大家发现了没有，没错，就是N，它是10的整数倍，因此，我们要将N/10，将j*10，代码就变成了：
int[][] dp = new int[len + 1][N / 10 + 1];
for (int i = 1; i < len + 1; i++) {
int price = 0, price1 = 0, price2 = 0, price3 = 0;
int satisfy = 0, satisfy1 = 0, satisfy2 = 0, satisfy3 = 0;
//只考虑主件
price = goods[i].v;
satisfy = goods[i].v * goods[i].p;
//买主件+附件一
if (goods[i].a1 > 0) {
price1 = goods[goods[i].a1].v + price;
satisfy1 = goods[goods[i].a1].v * goods[goods[i].a1].p + satisfy;
}
//买主件+附件二
if (goods[i].a2 > 0 ) {
price2 = goods[goods[i].a2].v + price;
satisfy2 = goods[goods[i].a2].v * goods[goods[i].a2].p + satisfy;
}
//买主件+附件一+附件二
if (goods[i].a1 > 0 && goods[i].a2 > 0) {
price3 = goods[goods[i].a1].v + goods[goods[i].a2].v + price;
satisfy3 = goods[goods[i].a1].v * goods[goods[i].a1].p + goods[goods[i].a2].v * goods[goods[i].a2].p + satisfy;
}
//对dp进行赋值（填充表格）
for (int j = 1; j <= N / 10; j++) {
if (goods[i].q > 0) {
dp[i][j] = dp[i - 1][j];
} else {
//只买主件，对应上面price和satisfy
if (j * 10 >= price && price != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j * 10 - price) / 10] + satisfy);
}
//买主件+附件一，对应上面price1和satisfy1
if (j * 10 >= price1 && price1 != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j * 10 - price1) / 10] + satisfy1);
}
//买主件+附件二，对应上面price2和satisfy2
if (j * 10 >= price2 && price2 != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j * 10 - price2) / 10] + satisfy2);
}
//买主件+附件一+附件二，对应上面price3和satisfy3
if (j * 10 >= price3 && price3 != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j * 10 - price3) / 10] + satisfy3);
}
}
}
}这样对吗，或许对N在100以内的10的整数倍是成立的，但超过100呢，难道要把10再改成100吗，这里我们可以取一个基数，这个基数就是这m个物品中价格最低的数值的最高位（就是基数排序中的基数）
public static int getCardinality(int[] arr){
int[] arrCopy = arr;
Arrays.sort(arrCopy);
int temp = arrCopy[1];
int count = 1;
while (temp / 10 != 0){
temp /= 10;
count *= 10;
}
return count;
}然后将代码的10都替换成基数即可，如下：
int cardinality = getCardinality(v); //基数
//dp[i][j]代表的是：手中有j元时，买第i件物品时达到的最大满意度是dp[i][j]
int[][] dp = new int[len + 1][N /cardinality+ 1];
for (int i = 1; i < len + 1; i++) {
int price = 0, price1 = 0, price2 = 0, price3 = 0;
int satisfy = 0, satisfy1 = 0, satisfy2 = 0, satisfy3 = 0;
//只考虑主件
price = goods[i].v;
satisfy = goods[i].v * goods[i].p;
//买主件+附件一
if (goods[i].a1 > 0) {
price1 = goods[goods[i].a1].v + price;
satisfy1 = goods[goods[i].a1].v * goods[goods[i].a1].p + satisfy;
}
//买主件+附件二
if (goods[i].a2 > 0 ) {
price2 = goods[goods[i].a2].v + price;
satisfy2 = goods[goods[i].a2].v * goods[goods[i].a2].p + satisfy;
}
//买主件+附件一+附件二
if (goods[i].a1 > 0 && goods[i].a2 > 0) {
price3 = goods[goods[i].a1].v + goods[goods[i].a2].v + price;
satisfy3 = goods[goods[i].a1].v * goods[goods[i].a1].p + goods[goods[i].a2].v * goods[goods[i].a2].p + satisfy;
}
//对dp进行赋值（填充表格）
for (int j = 1; j <= N/cardinality; j++) {
if (goods[i].q > 0) { //跳过附件
dp[i][j] = dp[i - 1][j];
} else {
//只买主件，对应上面price和satisfy
if (j * cardinality >= price && price != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j * cardinality - price) / cardinality] + satisfy);
}
//买主件+附件一，对应上面price1和satisfy1
if (j * cardinality >= price1 && price1 != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j * cardinality - price1) / cardinality] + satisfy1);
}
//买主件+附件二，对应上面price2和satisfy2
if (j * cardinality >= price2 && price2 != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j * cardinality - price2) / cardinality] + satisfy2);
}
//买主件+附件一+附件二，对应上面price3和satisfy3
if (j * cardinality >= price3 && price3 != 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j * cardinality - price3) / cardinality] + satisfy3);
}
}
}
}最后返回dp[len][N/cardinality]即为最大满意度。
本题对比了0-1背包问题，复杂之处就在于该题有附件跟主件关联，因此进行了4种情况的讨论，只买主件、买主件+附件1、主件+附件2、主件+附件1+附件2，另外本题的N为10的整数倍，因此做了优化处理，取价格的最小值的最高位作为基数，N/基数，大大增加了运行效率，同时也作了细节处理，第二层循环的j为序号，因此要乘以基数才能跟价格进行比较，否则不会对dp[i][j]进行赋值，结果将为0，后面的j-price也改为(j * cardinality - price) / cardinality。
在VMware16.2.4安装Ubuntu一、安装VMware1.打开VMwareWorkstationPro官网，点击即可进入。2.进入后向下滑动找到Workstation16ProforWindows，点击立即下载。3.下载完成，文件大小615MB，如下图：4.鼠标右击，以管理员身份运行。5.点击下一步6.勾选条款，点击下一步7.先勾选，再点击下一步8.去掉勾选，点击下一步9.点击下一步10.点击安装11.点击许可证12.在百度上搜索VM16许可证，复制填入，然后点击输入即可，亲测有效。13.点击完成14.重启系统，点击是15.双击VMwareWorkstationPro图标，进入虚拟机主
1.在Python3中，下列关于数学运算结果正确的是:（B）a=10b=3print(a//b)print(a%b)print(a/b)A.3，3，3.3333...B.3，1，3.3333...C.3.3333...，3.3333...，3D.3.3333...，1，3.3333...解析： 在Python中，//表示地板除（向下取整），%表示取余，/表示除（Python2向下取整返回3）2.如下程序Python2会打印多少个数:（D）k=1000whilek>1: print(k)k=k/2A.1000 B.10C.11D.9解析： 按照题意每次循环K/2，直到K值小于等
深度学习12.CNN经典网络VGG16一、简介1.VGG来源2.VGG分类3.不同模型的参数数量4.3x3卷积核的好处5.关于学习率调度6.批归一化二、VGG16层分析1.层划分2.参数展开过程图解3.参数传递示例4.VGG16各层参数数量三、代码分析1.VGG16模型定义2.训练3.测试一、简介1.VGG来源VGG（VisualGeometryGroup）是一个视觉几何组在2014年提出的深度卷积神经网络架构。VGG在2014年ImageNet图像分类竞赛亚军，定位竞赛冠军；VGG网络采用连续的小卷积核（3x3）和池化层构建深度神经网络，网络深度可以达到16层或19层，其中VGG16和VGG
开门见山|拉取镜像dockerpullelasticsearch:7.16.1|配置存放的目录#存放配置文件的文件夹mkdir-p/opt/docker/elasticsearch/node-1/config#存放数据的文件夹mkdir-p/opt/docker/elasticsearch/node-1/data#存放运行日志的文件夹mkdir-p/opt/docker/elasticsearch/node-1/log#存放IK分词插件的文件夹mkdir-p/opt/docker/elasticsearch/node-1/plugins若你使用了moba，直接右键新建即可如上图所示依次类推创建
一、概述在之前的一篇博文中，记录了AT24C01、AT24C02芯片的读写驱动，先将之前的相关文章include一下：1.IIC驱动：4位数码管显示模块TM1637芯片C语言驱动程序2.AT24C01/AT24C02读写：AT24C01/AT24C02系列EEPROM芯片单片机读写驱动程序本文记录分享AT24C04、AT24C08、AT24C16芯片的单片机C语言读写驱动程序。二、芯片对比介绍型号容量bit容量byte页数字节/页器件寻址位可寻址器件数WordAddress位数/字节数备注AT24C044k5123216A2A149/1WordAddress使用P0位AT24C088k1024
这个问题在这里已经有了答案:Errorinstallingmysql2:Failedtobuildgemnativeextension(32个答案)关闭5年前。我不知道在ubuntu上安装mysql2:(sudogeminstallmysql2Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingmysql2:ERROR:Failedtobuildgemnativeextension.currentdirectory:/var/lib/gems/2.3.0/gems/mysql2-0.4.4/ext/my
我正在使用sass为我正在开发的一个简单的静态网站编写css。我运行了sass--watchcustom.scss:custom.css，它在启动时编译良好，并显示消息:Sassiswatchingforchanges.PressCtrl-Ctostop.overwritecustom.css但是，每当我更新.scss文件时，什么也没有发生。我以前没有在Rails应用程序的上下文之外使用过SASS，所以我想知道我是否遗漏了什么？我的scss文件也非常简单，所以我怀疑它有什么问题，特别是因为它在第一次运行时就可以工作。sass-v报告Sass3.1.16(BrainyBetty)，在Li
更新前一切正常。将ruby1.9.3p392与RVM和rails(3.2.12)结合使用使用MySQL5.7.16和Nginx和Unicorn日志显示LoadError:libmysqlclient.so.18:cannotopensharedobjectfile:Nosuchfileordirectory-/home/bill/apps/xxx/shared/bundle/ruby/1.9.1/gems/mysql2-0.3.16/lib/mysql2/mysql2.so我试过:卸载/安装mysql2gem运行捆绑安装没有任何效果。更新后有人遇到这个问题吗？
目录一.逻辑控制+方法1.java输入2.循环输入3.switch4.循环结构 5.三种输出6.java生成随机数7.java方法二.习题+方法21.返回二进制中1的个数2.获取一个二进制序列中的偶数位和奇数位，分别输出二进制序列3.JAVA比较字符串是否相同4.牛客网ACM书写格式5.方法的重载一.逻辑控制+方法1.java输入注意大小写！下面代码会出现什么问题？？2.循环输入Ctrl+D结束循环输入3.switch面试问题：不能做switch()参数的类型有哪些？longfloatdoubleboolean(其他的都可以)4.循环结构 continue该程序运行的结果是什么？？5.三种输出
目录类01背包问题，选or不选变种走方格类01背包问题，选or不选不同的子序列_牛客题霸_牛客网问题翻译： S有多少个不同的子串与T相同 S[1:m]中的子串与T[1:n]相同的个数 由S的前m个字符组成的子串与T的前n个字符相同的个数状态： 子状态：由S的前1,2,...,m个字符组成的子串与T的前1,2,...,n个字符相同的个数 F(i,j):S[1:i]中的子串与T[1:j]相同的个数状态递推： 在F(i,j)处需要考虑S[i]=T[j]和S[i]!=T[j]两种情况 当S[i]=T[j]