0-1背包问题

我们的题目是

背包的填表过程

package com.atguigu.dynamic;
public class KnapsackProblem {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] w = {1, 4, 3};//物品的重量
        int[] val = {1500, 3000, 2000}; //物品的价值 这里val[i] 就是前面讲的v[i]
        int m = 4; //背包的容量
        int n = val.length; //物品的个数
        //创建二维数组，
        //v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
        int[][] v = new int[n+1][m+1];
        //为了记录放入商品的情况，我们定一个二维数组
        int[][] path = new int[n+1][m+1];
        //初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
        for(int i = 0; i < v.length; i++) {
            v[i][0] = 0; //将第一列设置为0
        }
        for(int i=0; i < v[0].length; i++) {
            v[0][i] = 0; //将第一行设置0
        }
        //根据前面得到公式来动态规划处理
        for(int i = 1; i < v.length; i++) { //不处理第一行 i是从1开始的
            for(int j=1; j < v[0].length; j++) {//不处理第一列, j是从1开始的
                //公式
                if(w[i-1]> j) { // 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
                    v[i][j]=v[i-1][j];
                } else {
                    //说明:
                    //因为我们的i 从1开始的， 因此公式需要调整成
                    //v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
                    //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    //为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
                    if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];        //之所以对此处进行标记，是因为只有这个地方会出现多个商品的情况
                        //把当前的情况记录到path
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }
        //输出一下v 看看目前的情况
        for(int i =0; i < v.length;i++) {
            for(int j = 0; j < v[i].length;j++) {
                System.out.print(v[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("============================");
        //从后往前来处理，是因为动态规划是不断优化以至结果最优，那么必然要从后往前看
        int i = path.length - 1; //行的最大下标
        int j = path[0].length - 1;  //列的最大下标
        while(i > 0 && j > 0 ) { //从path的最后开始找
            if(path[i][j] == 1) {    //因为只允许一个商品，所以判断完一行，就该下一行了
                System.out.printf("第%d个商品放入到背包\n", i); 
                j -= w[i-1]; //w[i-1]，i代表商品的重量，j代表能容纳的重量，所以确定剩余的可容纳重量，就直接确定行数了
            }
            i--;    //确定完一个商品后，进入下一个商品的确定
        }
    }
}

子集背包问题

要求划分为两个和相等的子集，实际上可以表达为
给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满
这样就转换为背包问题了

package ActualCombat;
public class two {
    public static void main(String[] args) {
        int w=0;    
        int s=0;
        int[] sumweight = {1,5,11,5};
        int[] sumweight1 = new int [sumweight.length];    //存储数组1
        int[] sumweight2 = new int [sumweight.length];    //存储数组2
        int sum = 0;
        for (int i = 0; i < sumweight.length; i++) {    //计算总和，判断是否可分割
            sum += sumweight[i];
        }
        int key2;
        int key1 = key2 = sum/2;
        if (sum%2 != 0) {        
            System.out.println("false");        //余数不为0，表示不可分割
        }else {
            for (int i = 0; i < sumweight.length; i++) {    //逐渐递减，相差大于0，表示可以存储进数组1，反之用数组2存储
                if ((key1 - sumweight[i]) >= 0) {
                    key1 = key1 - sumweight[i];
                    sumweight1[w] = sumweight[i];
                    w++;        //记录数组1存储的个数
                }else {
                    key2 = key2 - sumweight[i];
                    sumweight2[s] = sumweight[i];
                    s++;        //记录数组2存储的个数
                }
            }
            for (int i = 0; i < w; i++) {
                System.out.print(sumweight1[i]+"\t");
            }
            System.out.println("\n");
            for (int i = 0; i < s; i++) {
                System.out.print(sumweight2[i]+"\t");
            }
        }
    }
}

示例1运行结果

示例2运行结果

本小节代码为我亲自所写，不像前一小节是老师的代码，而且只是在理解基础上，希望将来再次写0-1背包问题，可以自己写出来。当我每次强调是自己写出的时候，主要是想说也许这不是最简洁最快的方法，因为我基础不怎样，所以还是以解决问题为主。希望后面的进步越来越大
说句来说话，当可以分割的时候，后面的思路更像是我前面做的零钱兑换，接下来的这个完全背包其实也就是零钱兑换问题

完全背包问题

题目实际上就是把0-1背包问题的只允许拿一件物品改为可以无限拿同一个物品
我就不写这个代码了，你自己去看零钱兑换那一小节
零钱兑换