文档章节

01背包问题 动态规划 java实现

FL_NC
 FL_NC
发布于 2016/08/12 20:11
字数 526
阅读 205
收藏 0

日常吐槽,日常打代码,理论可以去看其他博客,只贴出代码,代码有注释

public static int Knapsack(int v[],int w[],int c,int n,int m[][])
      {
	   int jMax=Min(w[n]-1,c);//自底向上,若最后一个物体的重量小于背包的总容量,取最后一个物体的重量为界限
	                          //小于w[n]都放不不了
	   for(int j=0;j<=jMax;j++)m[n][j]=0;//背包容量小于最后一个物品的重量,不能放入该物品
	   for(int j=w[n];j<=c;j++) m[n][j]=v[n];//大于w[n]能放入
	   int i;
	   for(i=n-1;i>0;i--){//从n-1到1
	    jMax=Min(w[i]-1,c);
	    for(int j=0;j<=jMax;j++){//背包容量j小于物体w[i],则不能放入
	    	m[i][j]=m[i+1][j];
	    }
	    for(int j=w[i];j<=c;j++) {
	    	m[i][j]=Max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//大于则尝试放入,与不放入相比,区总价值大的
	    }
	   }
	   m[0][c]=m[1][c];//此时m[1][c],m[2][c],m[3][c]......m[n-1][c],m[n][c]的最优值已算出来
	   if(c>=w[0]){
		  m[0][c]=Max(m[i+1][c],m[i+1][c-w[1]]+v[0]);//此时i等于0
	   }
	 return m[0][c];
	}
 //输出选取物体的下标,从0开始
public static void Tracback(int v[],int w[],int c,int n,int m[][]){
	int x[] = new int[5];
	for(int i=0;i<n;i++){
		if(m[i][c]==m[i+1][c]){//相等则该物体不屈
			x[i]=0;
		}else{
			c=c-w[i];//取该物体后背包容量建w[i]
			x[i]=1;
		}	
	}
	if(m[n][c]>w[n]) {//只剩最后一个一物体,若背包容量能装下,则一定取
		x[n]=1;
	}else{
		x[n]=0;
	}
	for(int i=0;i<x.length;i++){
		System.out.println(x[i]);
	}
}
  public static	int Max(int a,int b){
	  if(a>=b){
	    return a;
	  }else{
	    return b;
	  }
	}
  public static 	int Min(int a,int b){
	  if(a<b){
	    return a;
	  }else{
	    return b;
	  }
	}

代码测试

//测试函数
    @org.junit.Test
	public void Test1(){
    	//背包容量
    	   int c=10;
    	   //物体个数
    	    int n=4;
    	    //物品质量
    	    int w[]={2,2,6,5,4};
    	    //物品价值
    	    int v[]={6,3,5,4,6};
    		  int m[][] =new int[200][200];
    	//    int m[][] ={};
    	System.out.println(ZeroOne.Knapsack(v,w,c,n,m));
    	ZeroOne.Tracback(v,w,c,n,m);
		
	}

 

© 著作权归作者所有

共有 人打赏支持
FL_NC
粉丝 7
博文 7
码字总数 5117
作品 0
哈尔滨
程序员
白话版 动态规划法

关于动态规划法的解释, 大多都是基于背包问题的, 但背包问题背负了很多算法的解释工作,经常让初学者混淆,刚刚刷leetcode的时候,发现了一个很不错的关于动态规划算法的例题,特来分享一下! 这是...

木子昭
01/31
0
0
java_面试_01_一个月的面试总结(java)

重点知识 由于我面试的JAVA开发工程师,针对于JAVA,需要理解的重点内容有: JVM内存管理机制和垃圾回收机制(基本每次面试都会问,一定要搞得透彻) JVM内存调优(了解是怎么回事,一般做项...

rayner
03/07
0
0
877. Stone Game - LeetCode

Question 877. Stone Game Solution 题目大意: 说有偶数个数字,alex和lee两个人比赛,每次轮流从第一个数字或最后一个数字中拿走一个(偶数个数字,所以他俩拿的数字个数相同),最后比谁拿...

yysue
08/22
0
0
152. Maximum Product Subarray - LeetCode

Question 152. Maximum Product Subarray Solution 题目大意:求数列中连续子序列的最大连乘积 思路:动态规划实现,现在动态规划理解的还不透,照着公式往上套的,这个问题要注意正负,需要...

yysue
08/14
0
0
JAVA区块链项目实战视频课程

课程介绍 全国首套,基于java的区块链实战教程。目的是让更多的java编程者了解区块链,掌握区块链开发。 1、区块链理论:以node.js例子区块链原理有深刻理解; 2、区块链java实战:深刻理解区...

小红牛
09/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

初级开发-编程题

` public static void main(String[] args) { System.out.println(changeStrToUpperCase("user_name_abc")); System.out.println(changeStrToLowerCase(changeStrToUpperCase("user_name_abc......

小池仔
今天
4
0
现场看路演了!

HiBlock
昨天
12
0
Rabbit MQ基本概念介绍

RabbitMQ介绍 • RabbitMQ是一个消息中间件,是一个很好用的消息队列框架。 • ConnectionFactory、Connection、Channel都是RabbitMQ对外提供的API中最基本的对象。Connection是RabbitMQ的s...

寰宇01
昨天
9
0
官方精简版Windows10:微软自己都看不过去了

微软宣布,该公司正在寻求解决方案,以减轻企业客户的Windows 10规模。该公司声称,企业客户下载整个Windows 10文件以更新设备既费钱又费时。 微软宣布,该公司正在寻求解决方案,以减轻企业...

linux-tao
昨天
14
0
TypeScript基础入门之JSX(二)

转发 TypeScript基础入门之JSX(二) 属性类型检查 键入检查属性的第一步是确定元素属性类型。 内在元素和基于价值的元素之间略有不同。 对于内部元素,它是JSX.IntrinsicElements上的属性类型...

durban
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部