01背包问题

解法一：二维数组+动态规划

• 总钱数 -> 背包总容量
• 每件物品的价格 -> 体积
• 每件物品的价格乘以重要度 -> 价值

i:从前i个物品中选
j：当前背包总容量
v：当前物品的体积
w：当前物品的价值
dp[i,j]：前i个物品中v*w的最大和

状态转移方程：
不选i：dp[i][j] = dp[i-1][j]
选i：dp[i][j] = dp[i-1][j-v[i]] + v[i] * w[i]

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int totalV = scan.nextInt();
        int num = scan.nextInt();

        int[] v = new int[40];
        int[] w = new int[40];

        for(int i=1; i<=num; i++){
            v[i] = scan.nextInt();
            w[i] = scan.nextInt();
        }

        int[][] dp = new int[num + 10][totalV+10];

        for(int i=1; i<=num; i++){
            for(int j=0; j<=totalV; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= v[i]){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v[i]] + v[i]*w[i]);
                }
            }
        }

        System.out.println(dp[num][totalV]);

    }
}

解法二：一位数组+动态规划
因为在解法一中，状态转移方程只使用到了i-1和j-a[i]，所以对于二维数组来说，其他记录的状态都是多余的，所以我们可以使用滚动数组来对解法一进行优化
状态转移方程：dp[j] = dp[j-a[i]] + v[i]*w[i]

注意：因为在顺序遍历过程中会导致i-1层的数据先被覆盖，所以需要逆序遍历，这样就会先计算高层元素而不会影响低层元素

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int totalV = scan.nextInt();
        int num = scan.nextInt();

        int[] v = new int[40];
        int[] w = new int[40];

        for(int i=1; i<=num; i++){
            v[i] = scan.nextInt();
            w[i] = scan.nextInt();
        }

        int[] dp = new int[totalV+10];

        for(int i=1; i<=num; i++){
            for(int j=totalV; j>=v[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-v[i]] + v[i]*w[i]);
            }
        }

        System.out.println(dp[totalV]);

    }
}