黄小华的个人网站
熬过无人问津的日子才有诗和远方!
背包问题

1 01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数,表示最大价值。

public class beibao01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[] v = new int[N];
        int[] w = new int[N];
        for(int i = 0; i < N; i ++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        System.out.println(maxValue(N, V ,v, w));
    }
    private static int maxValue(int N , int V , int[] v, int[] w){
        int[] m = new int[V+1];
        for(int i = 0; i < N; i ++){
            for(int j = V; j >= v[i]; j-- ){
                m[j] = Math.max(m[j],m[j - v[i]] + w[i]);
            }
        }
        return m[V];
    }
}

2 完全背包

有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。

第 i 种物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

public int wanquanbeibao(int N , int V , int[] v, int[] w){
       int[] dp=new int[V+1];
        for(int i=0;i<N;i++){
            // 代码与01背包的区别,从小到大遍历
            for(int j=0;j<=V;j++){
                if(j>=v[i]){
                    dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
        }
       return dp[V];
}

3 多重背包

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

public int maxValue(int N , int V , int[] v, int[] w,int[] s){
       int[] f = new int[V+1];
       for(int i = 0 ; i < N; i++){
           for(int j = 0; j <= V; j++){
              for(int k = 1 ;k < s[i];k++){
                  if(j>=k*v[i]){
                      f[j] = Math.max(f[j],f[j - k*v[i]]+k*w[i]);
                  }
              }
           }
       }
       return f[V] ;
    }

4 混合背包

有 N 种物品和一个容量是 V 的背包。

物品一共有三类:

第一类物品只能用1次(01背包);
第二类物品可以用无限次(完全背包);
第三类物品最多只能用 si 次(多重背包);
每种体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        List<Thing> things=new ArrayList<>();
        for(int i=0;i<N;i++){
            int v=sc.nextInt();
            int w=sc.nextInt();
            int s=sc.nextInt();
            if(s<0){
                things.add(new Thing(-1,v,w));
            }else if(s==0){
                things.add(new Thing(0,v,w));
            // 多重背包转化为01背包
            }else{
                for(int k=1;k<=s;k=k*2){
                    s=s-k;
                    things.add(new Thing(-1,k*v,k*w));
                }
                if(s>0){
                    things.add(new Thing(-1,s*v,s*w));
                }
            }
        }
        int[] dp=new int[V+1];
        for(int i=1;i<=things.size();i++){
            int kind=things.get(i-1).kind;
            if(kind<0){
                // 01背包,体积从大到小遍历
                for(int j=V;j>=things.get(i-1).v;j--){
                    dp[j]=Math.max(dp[j],dp[j-things.get(i-1).v]+things.get(i-1).w);
                }
            }else{
                // 完全背包,体积从小到大遍历
                for(int j=things.get(i-1).v;j<=V;j++){
                    dp[j]=Math.max(dp[j],dp[j-things.get(i-1).v]+things.get(i-1).w);
                }
            }
        }
        System.out.println(dp[V]);
    }
}
class Thing{
    int kind;
    int v;
    int w;
    public Thing(int kind,int v,int w){
        this.kind=kind;
        this.v=v;
        this.w=w;
    }
}

5 二维费用背包

有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。
输出最大价值

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int M = sc.nextInt();
        int[][] dp = new int[V+1][M+1];
        int[] v = new int[N];
        int[] m = new int[N];
        int[] w = new int[N];
        for(int i = 0; i < N; i ++){
            v[i] = sc.nextInt();
            m[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for(int i = 0;i < N; i++){
            for(int j = V; j >= v[i]; j--){
                for(int k = M; k >= m[i]; k--){
                    dp[j][k] = Math.max(dp[j][k],dp[j - v[i]][k - m[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[V][M]);
    }
}

6 分组背包

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V=sc.nextInt();
        int[] dp=new int[V+1];
        for(int i=0;i<N;i++){
            int S=sc.nextInt();
            int[] v=new int[S];
            int[] w=new int[S];
            for(int t=0;t<S;t++){
                v[t]=sc.nextInt();
                w[t]=sc.nextInt();
            }
            // 每组之间是01背包问题
            for(int j=V;j>=0;j--){
                // 组内遍历
                for(int k=0;k<S;k++){
                    if(j>=v[k]){
                        dp[j]=Math.max(dp[j],dp[j-v[k]]+w[k]);
                    }
                }
            }
        }
        System.out.println(dp[V]);
    }
}

7 背包问题求方案数

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

输出 最优选法的方案数。注意答案可能很大,请输出答案模10000007的结果

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int mod=1000000007;
        int N=sc.nextInt();
        int V=sc.nextInt();
        int[] v=new int[N];
        int[] w=new int[N];
        for(int i=0;i<N;i++){
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
        }
        int[] dp=new int[V+1];
        int[] count=new int[V+1];
        for(int i=0;i<=V;i++){
            count[i]=1;
        }
        for(int i=0;i<N;i++){
            for(int j=V;j>=v[i];j--){
                int value=dp[j-v[i]]+w[i];
                if(value>dp[j]){
                    dp[j]=value;
                    count[j]=count[j-v[i]];
                }else if(value==dp[j]){
                    // 有两条路径
                    count[j]=(count[j-v[i]]+count[j])%mod;
                }
            }
        }
        System.out.println(count[V]);
    }
}

8 求最优的具体方案

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

import java.util.*;
public class Main{

    public static void main(String[] args) {
        // N个物品
        int N;

        // 背包体积
        int V;

        // 每个物品的体积
        int[] v;

        // 每一个物品的价值
        int[] w;

        //代表物品的输入index
        int[] index;
        // start input
        Scanner input = new Scanner(System.in);
        N = input.nextInt();
        V = input.nextInt();

        v = new int[N + 1];
        w = new int[N + 1];
        index = new int[N + 1];
        int index_temp = 0;
        for (int i = N; i >= 1; i--) {
            v[i] = input.nextInt();
            w[i] = input.nextInt();
            index[i] = ++index_temp;
        }
        input.close();
        // start solution
        Main solution = new Main();
        List<Integer> ans = solution.solution_scheme(N,V,v,w, index);
        for(int i = 0; i < ans.size() -1; i++){
            System.out.print(ans.get(i));
            System.out.print(" ");
        }
        System.out.print(ans.get(ans.size() -1));


    }


    public List<Integer> solution_scheme(int N, int V, int[] v, int[] w, int[] index){
        // 首先标准的01问题解决方案,这里用原始方法求解,即dp矩阵是二维的
        int[][] dp = new int[N+1][V+1];
        for(int i = 1; i <= N; i++){
            for(int j = 0; j <= V; j++){
                if(j >= v[i]){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        ArrayList<Integer> ans = new ArrayList<>();
        // 这里开始反推方案
        int volumn_left = V;
        for(int i = N; i >= 1; i--){

            if(volumn_left >= v[i] && dp[i][volumn_left] == (dp[i-1][volumn_left-v[i]] + w[i])){
                // 说明选择了当前物品
                ans.add(Integer.valueOf(index[i]));

                // 背包减去当前物品的体积
                volumn_left -= v[i];
            }

            if(volumn_left <= 0){
                break;
            }
        }

        return ans;
    }
}