【算法数据结构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

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


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

分享: