Java实现01背包问题

比眉伴天荒 2023-07-20 05:44 52阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

参考视频：https://www.bilibili.com/video/BV1jt411m7Rc

package algorithm;
    
    import java.util.Arrays;
    
    public class Knapsack {
        
    
    	/**
    	 * 01背包问题
    	 * @param w 物品的重量
    	 * @param v 物品的价值
    	 * @param c 背包的容量
    	 * @return 
    	 */
    	public static int knapsack01(int[] w, int[] v, int c) {
        
    		int[][] dp = new int[w.length+1][c+1];
    		int[][] path = new int[w.length+1][c+1];
    		int n1,n2;
    		for(int i=1; i<dp.length; i++) {
        
    			for(int j=1; j<dp[0].length; j++) {
        
    				if(w[i-1] > j) {
        
    					dp[i][j] = dp[i-1][j];
    				}else {
        
    					n1 = dp[i-1][j];
    					n2 = v[i-1] + dp[i-1][j-w[i-1]];
    					if(n1 < n2) {
        
    						dp[i][j] = n2;
    						path[i][j] = 1;
    					}
    					else {
        
    						dp[i][j] = n1;
    					}
    				}
    			}
    		}
    		int i=dp.length-1;
    		int j=dp[0].length-1;
    		//打印哪几个物品放入了背包
    		while(i>0 && j>0) {
        
    			if(path[i][j] == 1) {
        
    				System.out.println(i);
    				j = j - w[i-1];
    			}
    			i--;
    		}
    		return dp[dp.length-1][dp[0].length-1];
    	}
    	//一维数组的01背包问题，第二层循环倒序，如果是完全背包问题是正序
    	public static int knapsack(int[] w, int[] v, int C) {
        
    		int size = w.length;
            int[] dp = new int[C + 1];
    
            System.out.println(Arrays.toString(dp));
            for (int i = 0; i < size; i++) {
        
                for (int j = C; j >= w[i]; j--) {
        
                    dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
                }
            }
    		System.out.println(Arrays.toString(dp));
    		return dp[C];
    	}
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    
    		int[] w = {
        2,1,3,2};
            int[] v = {
        12,10,20,15};
            System.out.println(knapsack01(w,v,5));
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982