文档章节

01背包的贪心算法(物品可拆分)

 南桥北木
发布于 2017/04/07 19:33
字数 213
阅读 5
收藏 0

import java.util.Scanner;

public class Shuisou {

public static int p[]=new int[20];
public static int w[]=new int[20];
public static double temp[]=new double[20];
public static void main(String args[]){
	 Scanner in = new Scanner(System.in);
	 int m=in.nextInt();
	 int cap=in.nextInt();
	 for(int i=0;i<m;i++){
		w[i]=in.nextInt();
		p[i]=in.nextInt();
	 }
	 for(int i=0;i<m;i++){
		 temp[i]=p[i]*1.0/w[i];
		
	 }
	 int s;
	s=ff(temp,m);
	int sum=0;
	sum=w[s]+sum;
	double total=0;
	total=total+p[s];
	int mm=0;
	temp[s]=0;
	 System.out.println(total);
	//每次装单位质量最大的
	while(sum<=cap&&mm<m-1){
		 s=ff(temp,m);
		 temp[s]=0;
		
		 sum=w[s]+sum;
		 if(sum<=cap){
			 total=total+p[s];
		 }
		 System.out.println(total);
		
		 mm++;
	}
	//判断是否装满
	 if(cap>sum-w[s]){
		 int cha=cap-sum+w[s];
		 
		 double least=cha*1.0/(w[s]*1.0)*(p[s]);
		 total=total+least;
	 }
	 System.out.println(total);
	
}

public static int ff(double[] temp2,int m){
	double max=temp2[0];
	int k=0;
	for(int i=1;i<m;i++){
		if(max<temp[i]){
			max=temp[i];
			k=i;
		}
	}
	temp[k]=0;
	return k;
	
}

}

© 著作权归作者所有

共有 人打赏支持
上一篇: php连接mysql
下一篇: 水手分椰子
粉丝 1
博文 234
码字总数 40717
作品 0
武汉
私信 提问
动态规划 &

一、 动态规划(Dp问题):解决问题的关键点 1) 递推公式:(最有子结构) 2) 数据的初始化 用例分析: a. 01 背包的问题(Knapsack Problem) 定义: 一个背包的容量V; 存在N个物品:w[i...

Playboy002
2015/07/17
42
0
贪心算法(greedy algorithms)

版权声明:本文为博主原创文章,欢迎转载,但请注明出处,谢谢愿意分享知识的你~~ https://blog.csdn.net/qq_32690999/article/details/84967905 贪心算法(greedy algorithms) 作者:Bluem...

蓝色枫魂
2018/12/12
0
0
js算法初窥05(算法模式02-动态规划与贪心算法)

  在前面的文章中(js算法初窥02(排序算法02-归并、快速以及堆排)我们学习了如何用分治法来实现归并排序,那么动态规划跟分治法有点类似,但是分治法是把问题分解成互相独立的子问题,最...

zaking
2018/05/29
0
0
零基础学贪心算法

本文在写作过程中参考了大量资料,不能一一列举,还请见谅。 贪心算法的定义: 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某...

angel_kitty
2017/02/24
0
0
“365算法每日学计划”:03打卡-贪心算法

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。 “计划”的主要目的: 1、想通过这样...

wx好好学java
2018/06/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

AWS的自动部署工具codedeploy 部署前的准备工作

开始部署codedeploy: 1.先预置IAM用户: 创建一个IAM用户或使用一个与AWS相关联的用户; 复制以下的策略附加到IAM用户,向IAM用户赋予对codedeploy(及codedeploy所依赖的AWS服务和操作)的...

守护-创造
27分钟前
0
0
这可能是最详细的一线大厂Mysql面试题详解了

1、MySQL的复制原理以及流程 基本原理流程,3个线程以及之间的关联; 主:binlog线程——记录下所有改变了数据库数据的语句,放进master上的binlog中; 从:io线程——在使用start slave 之后...

Java干货分享
37分钟前
1
0
人的精力是什么?如何强化精力

人的精力是什么? 人的精力是什么? 精力指精神和体力。精神包括一个人的精神状态,兴奋度,做事情的投入度,专注度,持续时间等。 人的精力来源 人的精力有4种来源,身体的、情感的、思想的和...

莫库什勒
56分钟前
2
0
JFinal开发的旅游线路营销Saas平台演示系统我部署了一个

今天部署了一个旅游线路营销管理系统的演示版: 演示地址:http://lvyou.jfinalxueyuan.com 演示账号:(暂时只给一个门店版的吧,批发商和总部的如果需要 演示看看 单独联系我微信:1876673...

山东-小木
今天
2
0
如何学习大数据技术

学习大数据技术,首先要明确大数据的概念。 大数据的概念作者认为有如下几点: 1.数据的来源多样性。例如关系数据库+文本+excel等 2.数据量大。TB级别的数据。 3.业务应用领域。实时性高与实...

董黎明
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部