注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

Java如何使用动态规划法解决0-1背包问题代码

JAVA相关 水墨上仙 1929次浏览 已收录 手机上查看

0/1背包问题的动态规划法求解,前人之述备矣,这里所做的工作,不过是自己根据理解实现了一遍,主要目的还是锻炼思维和编程能力,同时,也是为了增进对动态规划法机制的理解和掌握。 转自:http://blog.csdn.net/shuqin1984/article/details/5859223

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp值得提及的一个问题是,在用&nbspJAVA&nbsp实现时,&nbsp是按算法模型建模,还是用对象模型建模呢?&nbsp如果用算法模型,那么&nbsp背包的值、重量就直接存入二个数组里;如果用对象模型,则要对背包以及背包问题进行对象建模。思来想去,还是采用了对象模型,尽管心里感觉算法模型似乎更好一些。有时确实就是这样,对象模型虽然现在很主流,但也不是万能的,采用其它的模型和视角,或许可以得到更好的解法。&nbsp背包建模:

package algorithm.dynamicplan;  
public class Knapsack {  
      
    /** 背包重量  */  
    private int weight;  
      
    /** 背包物品价值  */  
    private int value;  
    /*** 
     * 构造器 
     */  
    public Knapsack(int weight, int value) {  
        this.value = value;  
        this.weight = weight;  
    }  
    public int getWeight() {  
        return weight;  
    }  
      
    public int getValue() {  
        return value;  
    }  
      
    public String toString() {  
        return "[weight: " + weight + " " + "value: " + value + "]";    
    }  
}   
 

背包问题求解:

/** 
 * 求解背包问题: 
 * 给定 n 个背包,其重量分别为 w1,w2,……,wn, 价值分别为 v1,v2,……,vn 
 * 要放入总承重为 totalWeight 的箱子中,  
 * 求可放入箱子的背包价值总和的最大值。 
 *  
 * NOTE: 使用动态规划法求解 背包问题 
 * 设 前 n 个背包,总承重为 j 的最优值为 v[n,j], 最优解背包组成为 b[n]; 
 * 求解最优值: 
 * 1. 若 j < wn, 则 : v[n,j] = v[n-1,j]; 
 * 2. 若  j >= wn, 则:v[n,j] = max{v[n-1,j], vn + v[n-1,j-wn]}。 
 *  
 * 求解最优背包组成: 
 * 1. 若 v[n,j] > v[n-1,j] 则 背包 n 被选择放入 b[n],  
 * 2. 接着求解前 n-1 个背包放入 j-wn 的总承重中,  
 *    于是应当判断 v[n-1, j-wn] VS v[n-2,j-wn], 决定 背包 n-1 是否被选择。 
 * 3. 依次逆推,直至总承重为零。 
 *     
 *    重点: 掌握使用动态规划法求解问题的分析方法和实现思想。 
 *    分析方法: 问题实例 P(n) 的最优解S(n) 蕴含 问题实例 P(n-1) 的最优解S(n-1); 
 *              在S(n-1)的基础上构造 S(n)  
 *    实现思想: 自底向上的迭代求解 和 基于记忆功能的自顶向下递归 
 */  
package algorithm.dynamicplan;  
import java.util.ArrayList;  
public class KnapsackProblem {  
      
    /** 指定背包 */  
    private Knapsack[] bags;  
      
    /** 总承重  */  
    private int totalWeight;  
      
    /** 给定背包数量  */  
    private int n;  
      
    /** 前 n 个背包,总承重为 totalWeight 的最优值矩阵  */  
    private int[][] bestValues;  
      
    /** 前 n 个背包,总承重为 totalWeight 的最优值 */  
    private int bestValue;  
      
    /** 前 n 个背包,总承重为 totalWeight 的最优解的物品组成 */  
    private ArrayList<Knapsack> bestSolution;  
      
    public KnapsackProblem(Knapsack[] bags, int totalWeight) {  
        this.bags = bags;  
        this.totalWeight = totalWeight;  
        this.n = bags.length;  
        if (bestValues == null) {  
            bestValues = new int[n+1][totalWeight+1];  
        }  
    }  
      
    /** 
     * 求解前 n 个背包、给定总承重为 totalWeight 下的背包问题 
     *  
     */  
    public void solve() {  
          
        System.out.println("给定背包:");  
        for(Knapsack b: bags) {  
            System.out.println(b);  
        }  
        System.out.println("给定总承重: " + totalWeight);  
          
        // 求解最优值  
        for (int j = 0; j <= totalWeight; j++) {  
            for (int i = 0; i <= n; i++) {  
              
                if (i == 0 || j == 0) {  
                    bestValues[i][j] = 0;  
                }     
                else   
                {  
                    // 如果第 i 个背包重量大于总承重,则最优解存在于前 i-1 个背包中,  
                    // 注意:第 i 个背包是 bags[i-1]  
                    if (j < bags[i-1].getWeight()) {  
                        bestValues[i][j] = bestValues[i-1][j];  
                    }     
                    else   
                    {  
                        // 如果第 i 个背包不大于总承重,则最优解要么是包含第 i 个背包的最优解,  
                        // 要么是不包含第 i 个背包的最优解, 取两者最大值,这里采用了分类讨论法  
                        // 第 i 个背包的重量 iweight 和价值 ivalue  
                        int iweight = bags[i-1].getWeight();  
                        int ivalue = bags[i-1].getValue();  
                        bestValues[i][j] =   
                            Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]);        
                    } // else  
                } //else           
           } //for  
        } //for  
          
        // 求解背包组成  
        if (bestSolution == null) {  
            bestSolution = new ArrayList<Knapsack>();  
        }  
        int tempWeight = totalWeight;  
        for (int i=n; i >= 1; i--) {  
           if (bestValues[i][tempWeight] > bestValues[i-1][tempWeight]) {  
               bestSolution.add(bags[i-1]);  // bags[i-1] 表示第 i 个背包  
               tempWeight -= bags[i-1].getWeight();  
           }  
           if (tempWeight == 0) { break; }  
        }  
        bestValue = bestValues[n][totalWeight];  
    }  
      
    /** 
     * 获得前  n 个背包, 总承重为 totalWeight 的背包问题的最优解值 
     * 调用条件: 必须先调用 solve 方法 
     *  
     */  
    public int getBestValue() {   
        return bestValue;  
    }  
      
    /** 
     * 获得前  n 个背包, 总承重为 totalWeight 的背包问题的最优解值矩阵 
     * 调用条件: 必须先调用 solve 方法 
     *  
     */  
    public int[][] getBestValues() {  
          
        return bestValues;  
    }  
      
    /** 
     * 获得前  n 个背包, 总承重为 totalWeight 的背包问题的最优解值矩阵 
     * 调用条件: 必须先调用 solve 方法 
     *  
     */  
    public ArrayList<Knapsack> getBestSolution() {  
        return bestSolution;  
    }  
      
}  
 

背包问题测试:

package algorithm.dynamicplan;  
  
public class KnapsackTest {  
      
    public static void main(String[] args) {  
          
        Knapsack[] bags = new Knapsack[] {  
                new Knapsack(2,13), new Knapsack(1,10),  
                new Knapsack(3,24), new Knapsack(2,15),  
                new Knapsack(4,28), new Knapsack(5,33),  
                new Knapsack(3,20), new Knapsack(1, 8)  
        };  
        int totalWeight = 12;  
        KnapsackProblem kp = new KnapsackProblem(bags, totalWeight);  
          
        kp.solve();  
        System.out.println(" -------- 该背包问题实例的解: --------- ");  
        System.out.println("最优值:" + kp.getBestValue());   
        System.out.println("最优解【选取的背包】: ");  
        System.out.println(kp.getBestSolution());  
        System.out.println("最优值矩阵:");  
        int[][] bestValues = kp.getBestValues();  
        for (int i=0; i < bestValues.length; i++) {  
            for (int j=0; j < bestValues[i].length; j++) {  
                System.out.printf("%-5d", bestValues[i][j]);  
            }  
            System.out.println();  
        }  
    }  
}   
 

动态规划法总结:1.&nbsp动态规划法用于求解非最优化问题:当问题实例P(n)的解由子问题实例的解构成时,比如&nbspP(n)&nbsp=&nbspP(n-1)&nbsp+&nbspP(n-2)&nbsp[斐波那契数列]&nbsp,而&nbspP(n-1)&nbsp和&nbspP(n-2)可能包含重合的子问题,可以使用动态规划法,通过自底向上的迭代,求解较小子问题实例的解,并作为求解较大子问题实例的解的基础。关键思想是:&nbsp避免对子问题重复求解。比如:&nbsp求斐波那契数&nbspF(5):F(5)&nbsp&nbsp=&nbspF(4)&nbsp+&nbspF(3);子问题:&nbspF(4)&nbsp=&nbspF(3)&nbsp+&nbspF(2) &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspF(3)&nbsp=&nbspF(2)&nbsp+&nbspF(1);&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspF(2)&nbsp=&nbspF(1)&nbsp+&nbspF(0)&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspF(2)&nbsp=&nbspF(1)&nbsp+&nbspF(0);子问题:&nbspF(3)&nbsp=&nbspF(2)&nbsp+&nbspF(1)&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbspF(2)&nbsp=&nbspF(1)&nbsp+&nbspF(0)由上面的计算过程可知,如果单纯使用递归式,则子问题&nbspF(2)&nbsp被重复计算了2次;当问题实例较大时,这些重复的子问题求解就会耗费大量不必要的时间。&nbsp若使用动态规划法,将&nbspF(2)&nbsp的值存储起来,当后续计算需要的时候,直接取出来,&nbsp就可以节省不少时间。&nbsp另一个比较典型的例子是:&nbsp求解二项式系数&nbsp&nbspC(n,&nbspk)&nbsp=&nbspC(n-1,&nbspk)&nbsp+&nbspC(n-1,&nbspk-1)&nbsp2.&nbsp动态规划法求解最优化问题:&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp当问题实例P(n)&nbsp的最优解&nbsp可以从&nbsp问题实例&nbspP(n-1)&nbsp的最优解&nbsp构造出来时,可以采用动态规划法,一步步地构造最优解。&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp关键是掌握动态规划法求解问题时的分析方法,如何从问题导出&nbsp解的递推式。&nbsp实际上,当导出背包问题的递归式后,后来的工作就简单多了,如何分析背包问题,导出其最优解的递推式,我觉得,这才是最关键的地方!问题分析很重要!


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明Java如何使用动态规划法解决0-1背包问题代码
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……