目录

01背包问题

宁柠057 收录于 leetcode

2023-05-06 约 324 字预计阅读 1 分钟

/01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/featured-image.png

目录

简介：01背包 dp

2 动态规划设计

2.15 0-1背包问题

问题描述

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。

其中第 i 个物品的重量为 wt[i]，价值为 val[i]

现在让你用这个背包装物品，最多可以装的价值是多少？

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


public int bag01(int W, int N, int[] wt, int[] val) {
    //dp
    //dp数组定义：dp[i][j]代表：对于前i个物体，当前背包容量为j，可以装下的最大价值
    int[][] dp = new int[N+1][W+1];
    //base case：当 W == 0 或者 N == 0，最多可以装的价值都是0
    //即dp[i][0] = 0, dp[0][j] = 0
    //状态转移方程
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= W; j++) {
            if(j < wt[i-1]) {
                //背包容量不够，只能选择不装入背包
                dp[i][j] = dp[i-1][j];
            } else {
                //装入背包或者不装入背包，择优
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1]);
            }
        }
    }
    //返回值
    return dp[N][W];
}