背包问题（整理）

在这里推荐一些，关于背包九讲，非常好的视频讲解和相关的博客学习
背包九讲 —— yxc 直播回放   B站 大雪菜
背包九讲 —— 全篇详细理解与代码实现   CSDN 良月澪二，博主提供了很多背包方面的题解。
结合视频和博客的学习，这里提供一些 java 的实现版本，其实就是翻译一下，大佬们的 C++ 程序 。
这些题都可以在 AcWing 题库第一页就能找到，是不是很方便。
这里也只介绍了四类背包问题， 因为其他的类型，本人太菜了，还没学会 ( T—T ) ， 后期再慢慢加上。

01背包

传送门

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

完全背包

传送门

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

多重背包

传送门

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int N = input.nextInt();
            int V = input.nextInt();
            int[] f = new int[V + 1];
            for(int i = 0;i < N;i ++){
                int v = input.nextInt();
                int w = input.nextInt();
                int s = input.nextInt();
                int num = Math.min(s , V / v);
                for(int k = 1;num > 0;k <<= 1){
                    if(k > num) k = num;
                    num -= k;
                    for(int j = V;j >= v * k;j --){
                        f[j] = Math.max(f[j] , f[j - k * v] + k * w);
                    }
                }
            }
            System.out.println(f[V]);
        }
        input.close();
    }
}

分组背包

传送门

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