背包问题

爱被打了一巴掌 2021-09-27 10:10 329阅读 0赞

参考博客：  
[https://www.cnblogs.com/fengziwei/p/7750849.html][https_www.cnblogs.com_fengziwei_p_7750849.html]

思路都是，先放第一个物品，容量从1到max 的最大收益

1.0-1背包问题  
0-1背包问题是指每一种物品都只有一件，可以选择放或者不放。现在假设有n件物品，背包承重为m。

import java.util.Scanner;
    
    /** * Created by zfr on 2018/09/07. * 完全背包问题，每个物品可以放无数个 */
    public class Main { 
        public static void main(String args[]){
            Scanner scanner = new Scanner(System.in);
            int Max = scanner.nextInt();//背包的容量
            int counts = scanner.nextInt();//总共有多少种东西
            //每个东西的重量和价值
            int[] weights = new int[counts];
            int[] values = new int[counts];
            for(int i = 0 ; i < counts ; i++ ){
                weights[i] = scanner.nextInt();
                values[i] = scanner.nextInt();
            }
            int[][] f = new int[counts+1][Max+1] ;
            for(int i = 1 ; i < counts ; i++){
              // System.out.println(i);
                for(int j = 1 ; j <= Max;j++){
                   // System.out.println(j);
                    if(weights[i] > j){
       //容量不够，不放
                        f[i][j] = f[i-1][j];
                    }else {
       //容量够，选择放或者不放的最大值
                        f[i][j] = Math.max(f[i-1][j] , f[i-1][j - weights[i]] + values[i]);
                    }
                }
            }
            System.out.println(f[counts-1][Max]);
        }
    }

测试用例：

> 10  
> 5  
> 2 6  
> 2 3  
> 6 5  
> 5 4  
> 4 6  
> 输出：11

2.完全背包问题  
完全背包问题是指每种物品都有无限件。

import java.util.Scanner;
    
    /** * Created by zfr on 2018/09/07. */
    public class Main { 
        public static void main(String args[]){
            Scanner scanner = new Scanner(System.in);
            int Max = scanner.nextInt();//背包的容量
            int counts = scanner.nextInt();//总共有多少种东西
            //每个东西的重量和价值
            int[] weights = new int[counts];
            int[] values = new int[counts];
            for(int i = 0 ; i < counts ; i++ ){
                weights[i] = scanner.nextInt();
                values[i] = scanner.nextInt();
            }
            int[][] f = new int[counts+1][Max+1] ;
            for(int i = 1 ; i < counts ; i++){
                // System.out.println(i);
                for(int j = 1 ; j <= Max;j++){
                    // System.out.println(j);
                    if(weights[i] > j){
       //容量不够，不放
                        f[i][j] = f[i-1][j];
                    }else {
       //容量够，选择不放、放1个...最大值，取最优
                        //放1个或者多个
                        int count = j / weights[i] ;//不放的情况
                        f[i][j] = f[i-1][j] ;
                        for (int k = 1 ; k <= count ; k++ ){
                            f[i][j] = Math.max(f[i][j] , f[i-1][j - k * weights[i]] + k * values[i]);
                        }
                    }
                }
            }
            System.out.println(f[counts-1][Max]);
        }
    }

> 10  
> 5  
> 2 6  
> 2 3  
> 6 5  
> 5 4  
> 4 6  
> 输出15

[https_www.cnblogs.com_fengziwei_p_7750849.html]: https://www.cnblogs.com/fengziwei/p/7750849.html