【算法数据结构Java实现】Java实现动态规划(背包问题)-阿里云开发者社区

开发者社区> 傲海> 正文

【算法数据结构Java实现】Java实现动态规划(背包问题)

简介: 1.背景      追随着buptwusuopu大神的脚步,最近在研习动态规划。动态规划应该叫一种解决问题的思想,记得又一次去某公司面试就被问到了这个。        多于动态规划的理解,大致是这样的,从空集合开始,每增加一个元素就求它的最优解,直到所有元素加进来,就得到了总的最优解。             比较典型的应用就是背包问题,有一个重量一定的包,有若干件物品,他们各自有不同的重量
+关注继续查看

1.背景

     追随着buptwusuopu大神的脚步,最近在研习动态规划。动态规划应该叫一种解决问题的思想,记得又一次去某公司面试就被问到了这个。
       多于动态规划的理解,大致是这样的,从空集合开始,每增加一个元素就求它的最优解,直到所有元素加进来,就得到了总的最优解。
    
       比较典型的应用就是背包问题,有一个重量一定的包,有若干件物品,他们各自有不同的重量和价值,怎样背才能取得最大价值。
       错误的理解:去价值/重量比最大的物品多装(之前我也是这么想的,但是在背包重量一定的情况下这么做并不合理,范例很容易想到)

2.题目

       要实现的题目是摘抄于另一位大神的博客,讲的很好,可惜不是java实现的,有兴趣可以看下面的引用。

题目描述:

有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?

name weight value 1 2 3 4 5 6 7 8 9 10
a 2 6 0 6 6 9 9 12 12 15 15 15
b 2 3 0 3 3 6 6 9 9 9 10 11
c 6 5 0 0 0 6 6 6 6 6 10 11
d 5 4 0 0 0 6 6 6 6 6 10 10
e 4 6 0 0 0 6 6 6 6 6 6 6


3.代码实现

public class Main {
 
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub        		
		final int packageWheight=10;//包的重量
		Package[] pg={
		   new Package(6,2,"a"),
		   new Package(3,2,"b"),
		   new Package(5,6,"c"),
		   new Package(4,5,"d"),
		   new Package(6,4,"e")		   
		};
		
		int[][] bestValues = new int[pg.length+1][packageWheight+1];
	
		for(int i=0;i<=pg.length;i++){
			for(int j=0;j<=packageWheight;j++){
				if(i==0||j==0){
					bestValues[i][j]=0;//临界情况
				}
				else{
					if(j<pg[i-1].getWheight()){
						bestValues[i][j] = bestValues[i-1][j];//当第n件物品重量大于包的重量时,最佳值取前n-1件的
					}
					else{
						   int iweight = pg[i-1].getWheight(); //当第n件物品重量小于包的重量时,分两种情况,分别是装第n件或不装,比较取最大
	                        int ivalue = pg[i-1].getValue();    
	                        bestValues[i][j] =     
	                            Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]);          
					}
				}
			}
		}
		
		System.out.print(""+bestValues[pg.length][packageWheight]);
		}
	}


public class Package {

	int value;
	int wheight;
	String name;
	Package(int value,int wheight,String name){
		this.value=value;
		this.wheight=wheight;
		this.name=name;
	}
	public int getWheight(){
		return wheight;
	}
	public int getValue(){
		return value;
	}
	public String getName(){
		return name;
	}
}


有兴趣的同学可以到我的github去clone这个工程:https://github.com/jimenbian/DynamicPrograme


                 



/********************************

* 本文来自博客  “李博Garvin“

* 转载请标明出处:http://blog.csdn.net/buptgshengod

******************************************/


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序算法大数据量测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; using System.IO; namespace Sort { class Program
812 0
物件捆绑 背包问题 动态规划 求解
  物件捆绑背包问题:给定N元钱,要购买一些器件。器件有主件和附件之分,也即主件可以单独购买,然而购买附件必须购买对应的主件。下表就是一些主件与附件的例子: 主件 附件 电脑      打印机、扫描仪 书柜 图书 书桌          台灯 工作椅 无      把每件物品规定一个重要度,分为5等:用整数1~5表示,第5等最重要。
828 0
海量数据处理的 Top K算法(问题) 小顶堆实现
  问题描述:有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k或者Top 10)   问题分析:由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相当的不可取的。
832 0
回溯法解决0-1背包问题
问题描述:   有n件物品和一个容量为c的背包。第i件物品的价值是v[i],重量是w[i]。求解将哪些物品装入背包可使价值总和最大。所谓01背包,表示每一个物品只有一个,要么装入,要么不装入。回溯法:   01背包属于找最优解问题,用回溯法需要构造解的子集树。
1122 0
图的单源最短路径,Floyd算法(数据结构c++)
这个算法结构很是简单,但是理解还是有一定的困难,一开始做的时候想不明白,跟着算法自己动手画画就知道这个算法具体是怎么回事了。 时间复杂度是O(N*3) 算法有点动态规划的意思,有两个数组,一个(dis[])是记录俩顶点之间的最短路径的长度的,一个[path]数组是记录俩结点的中间结点的。
727 0
+关注
傲海
著有《机器学习实践应用》,阿里云机器学习PAI产品经理,个人微信公众号&ldquo;凡人机器学习&rdquo;。
302
文章
10
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载