当前位置：网站首页>DP背包问题

DP背包问题

2022-07-20 03:23:00 【库里不会投三分】

0-1 背包问题

经典的DP问题，还是四步走，明确状态——>明确选择——> 定义 dp 数组/函数的含义 ——>base case
明确状态
首先会变化的就是背包的容量
其次会变的就是能够选择的物品
明确选择
对于一个物品，要么不选
要么就是选
明确定义dp数组含义
dp[i][j]表示可以选择前i个物品，j为表示当前背包的容量,dp[i][j]表示能装的最大价值
明确base case
dp[0][i]表示可选择的物品为0，肯定最大价值为0
dp[i][0]表示，容量为0，最大价值肯定为0
核心——写出状态转换方程
代码
public int backPackII(int m, int[] a, int[] v) {
        // write your code here
        int row=a.length;
        int column=m;
        //base case dp[0][0...column-1] dp[0...row-1][0]
        int dp[][]=new int[row+1][column+1];
        for (int i = 1; i <=row; i++) {
            for (int j = 1; j <=column; j++) {
                if(j<a[i-1]){
                    dp[i][j]=dp[i-1][j];
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-a[i-1]]+v[i-1]);
                }
            }
        }
        return dp[row][column];
    }