网站源码商城,网站服务公司有哪些,wordpress 手机号注册,重庆的网站设计公司价格一#xff1a;思考 1.某天早上公司领导找你解决一个问题#xff0c;明天公司有N个同等级的会议需要使用同一个会议室#xff0c;现在给你这个N个会议的开始和结束 时间#xff0c;你怎么样安排才能使会议室最大利用#xff1f;即安排最多场次的会议#xff1f;电影的话 那… 一思考 1.某天早上公司领导找你解决一个问题明天公司有N个同等级的会议需要使用同一个会议室现在给你这个N个会议的开始和结束 时间你怎么样安排才能使会议室最大利用即安排最多场次的会议电影的话 那肯定是最多加票价最高的入场率。综合算法 2.双十一马上就要来了小C心目中的女神在购物车加了N个东西突然她中了一个奖可以清空购物车5000元的东西不能找零每个东西只能买一件那么她应该如何选择物品使之中奖的额度能最大利用呢如果存在多种最优组合你只需要给出一种即可嘿嘿 现在女神来问你你该怎么办(动态规划) 二 贪心算法 概念贪心算法又叫做贪婪算法它在求解某个问题是总是做出眼前最大利益。 也就是说只顾眼前不顾大局所以它是局部最优解。核心点通过局部最优推出全局最优。 举例 1.某天早上公司领导找你解决一个问题明天公司有N个同等级的会议需要使用同一个会议室现在给你这个N个会议的开始和结束时间你怎么样安排才能使会议室最大利用即安排最多场次的会议 现在我们怎么去贪也就这个我们选择的贪心策略、 1.1 选时间最短1-32~4,3~5,4~6 1.2 按结束时间从小到大排序首先把第一个加入我们可以开会的列表。之后只要开始时间是大于我们上一个的结束时间的就可以开 代码如下 package tx;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/*** 贪心算法1.某天早上公司领导找你解决一个问题明天公司有N个同等级的会议需要使用同一个会议室* 现在给你这个N个会议的开始和结束时间你怎么样安排才能使会议室最大利用即安排最多场次的会议** 策略按结束时间从小到大排序首先把第一个加入我们可以开会的列表。之后只要开始时间是大于我们上一个的结束时间的就可以开* 核心排序*/
class Metting implements ComparableMetting {int meNum; // 编号int startTime; // 开始时间int endTime; // 结束时间public Metting(int meNum, int startTime, int endTime) {super();this.meNum meNum;this.startTime startTime;this.endTime endTime;}public int compareTo(Metting o) {if (this.endTime o.endTime)return 1;return -1;}Overridepublic String toString() {return Metting [meNum meNum , startTime startTime , endTime endTime ];}}public class MettingTest {public static void main(String[] args) {Scanner cin new Scanner(System.in);ListMetting mettings new ArrayListMetting();int n cin.nextInt(); //n个会议for (int i 0 ;i n; i){int start cin.nextInt();int end cin.nextInt();Metting metting new Metting(i1, start, end);mettings.add(metting);}mettings.sort(null);int curTime 0; //当前的时间,从一天的0点开始,如果领导要求从8点开始 那curTime8for(int i 0 ; i n; i ){Metting metting mettings.get(i);if(metting.startTime curTime){ //会议的开始时间比我们当前的要大 表示可以开System.out.println(metting.toString());curTime metting.endTime;}}}
}2.1 贪心算法的核心思想 贪心算法的套路一定会有一个排序。哈夫曼编码贪心算法压缩算法。最短路径 贪心算法不是对所有问题都能得到整体最优解关键是贪心策略的选择选择的贪心策略必须具备无后效性即某个状态以前的过程不会影响以后的状态只与当前状态有关。 贪心算法其最重要的两个点就是 贪心策略排序 通过局部最优解能够得到全局最优解 一般通过以下问题就可以通过贪心算法解决 1.针对某个问题有限制值以及有一个期望的最好结果通常是从某些数据中选出其中一些达到最好的结果。 2.一般会有一个排序找出贡献最大的。 3.举例看贪心是否可以解决。 一般用在任务调度教师排课等系统。 实际上用贪心算法解决问题的思路并不总能给出最优解。 三动态规划 经典问题 背包问题 小偷去某商店盗窃背有一个背包容量是5kg现在有以下物品物品不能切分,且只有一个请问小偷应该怎么拿才能得到最大的价值 5kg的袋子 物品 钱6 10 12 Kg1 2 4 思路我们把5kg的袋子拆分成1kg1kg这样子计算里面的表格就表示当前重量下能装的最多的钱。表格的数列就表示是要装的物品 1kg 2kg 3kg 4kg 5kg 加入物品1 6 6 6 6 6 加入物品2 6 10 10616 10616 16 加入物品3 6 10 16 16 18 第一个物品 袋子只能装1kg的物品所以价钱为6 第二个物品 袋子当前为1kg 的容量时我们发现物品2装不进去。那我们应该取多少呢是不是只要取物品进来时1kg最大钱 当袋子为2kg时我们发现物品2可以装下去此时可以得到10块钱之前物品1进来时2kg最大是6吧那我们肯定要选择大的这个10而不是6.此时袋子还剩0kg可以装。 袋子为3kg时我们还是可以装下这个物品2,得到10块袋子还剩下1kg。 101kg能装的东西。 第三个物品 袋子为4kg时物品3可以转进来得到12块钱袋子还剩0kg。 我发现我不装物品3 还能得到16呢 袋子为5kg时物品3可以转进来得到12块钱袋子还剩1kg。那么装了物品3就能得到12618块钱 我发现我不装物品3 能得到16比18小所以决定装.。 图解将数值除以10就是上面的题 代码实现
package tx;public class Dp {public static void main(String[] args) {int value [] {60,100,120};int weigth[] {10,20,40}; //购物车那个问题 只需要一个价值就行了重量都都没有。int w 50; //代表我可以装的数量int n 3; //代表三个物品int dp[][] new int[n1][w1]; //n表示是物品w表示重量,初始化全是0for(int i 1; i n; i){ //每次加的物品for(int cw 1 ; cw w ; cw ){ //分割的背包if(weigth[i - 1] cw){ //表示这个物品可以装进去dp[i][cw] Math.max(value[i-1] dp[i-1][cw-weigth[i-1]],dp[i-1][cw]);}else{dp[i][cw] dp[i-1][cw]; //不能装}}}System.out.println(dp[n][w]);}
}四动归和贪心的比较 贪心是只管眼前不会管后的情况而动归不一样它的每次递推都是基于上一次的最优解进行。所以往往动归是一定能求出最优解的而贪心不一定这也是贪心算法的缺点但是大家都看到了动归的时间复杂度是O(n*m)而贪心是O(nlogn)所以贪心算法的是高效的动归如果子问题太多的话 就容易算不出结果而且能用动归的问题往往用贪心都能解决一部分甚至很大一部分。因此如果在实际项目中要求不是特别严的话 我建议使用贪心算法求最优解其实我们很多时候并不用保证100%的准确能尽量准确就可以了贪心恰恰是符合这个规则的。 五购物车代码实现
package tx;public class CardDp {public static void main(String[] args) {int weigth[] {1,2,3,4,5,9}; //购物车那个问题 只需要一个价值就行了重量都都没有。int w 8;int n 6;int dp[][] new int[n1][w1]; //n表示是物品w表示重量,初始化全是0for(int i 1; i n; i){ //每次加的物品for(int cw 1 ; cw w ; cw ){ //分割的背包if(weigth[i - 1] cw){ //表示这个物品可以装进去dp[i][cw] Math.max(weigth[i-1] dp[i-1][cw-weigth[i-1]],dp[i-1][cw]);}else{dp[i][cw] dp[i-1][cw]; //不能装}}}System.out.println(dp[n][w]);}
}
