01背包问题个人学习，java算法实现

Love The Way You Lie 2022-12-01 14:22 122阅读 0赞

## 问题描述：有一个背包，可放入12斤物品，现有5个物品,每个物品的重量分别为：2斤，4斤，6斤，8斤，10斤，每个物品的价值为4元，8元，12元，16元，20元，计算出可在背包中装入的最大价值？（每次每种物品只能装一次） ##

解析1：将物品编号为a,b,c,d,e,重量和价值对应为：a(2斤)(4元) 、b(4斤)(8元)、c(6斤)(12元)、d(8斤)(16元)、e(10斤)(20元)  
当每种物品放入一次，符合背包容量，其最大价值为20元；  
当物品两两放入，可分为：(2斤，4斤)(4元，8元)，(2斤，6斤)(4元，12元)，(2斤，8斤)(4元，16元)，(2斤，10斤)(4元，20元)，(4斤，6斤)(8元，12元)，(4斤，8斤)(8元，16元)，符合背包容量，其最大价值为24元；  
当物品三三放入，可分为：(2斤，4斤，6斤)(4元，8元，12元)，其最大价值为24元；

解析2：如下表所示

从表中可看出，价值最大为24元，有三种放入方法：  
1、（6斤，4斤，2斤）（12元，8元，4元）  
2、（8斤，4斤）（16元，8元）  
3、（10斤，2斤）（20元，4元）

解析3：使用java实现算法

public static void main(String[] args){ 
    	//物品数量
    	int N = 5；
    	//背包容量
    	int V = 12；
    	//定义一个长度为N+1的数组,物品的重量
        int[] v = { 0,2,4,6,8,10} ;
        //定义一个长度为N+1的数组，物品的价值
        int[] w = { 0,4,8,12,16,20} ;
        //定义二阶矩阵,其中N+1，V+1 表示当去0号物品时，器重量为0，价值为0,故+1，将0号物品排除
        int[][] arr2 = new int[N+1][V+1];
        arr2[0][0] = 0;
    	//i 是物品编号1-5
        for(int i = 1; i <= N; i++){ 
            //j 是背包的容量0-12
            for(int j = 0; j <= V; j++){ 
    
                if(j >= v[i]){ 
                    // 当背包容量大于或等于第i个物品的重量时
                    arr2[i][j] = Math.max(arr2[i-1][j], arr2[i-1][j-v[i]] + w[i]);
                }else{ 
                    // 当背包容量小于第i个物品的重量时，即第一种情况
                    arr2[i][j] = arr2[i-1][j];
                }
            }
        }
        System.out.println("最大价值："+arr2[N][V]);
    }

根据上述算法，结果为24