K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知0-1背包问题中，背包最大容量为W，共有n个物品，每个物品的重量存储在数组wt中，价值存储在数组val中，每个物品仅可被选取一次。假设使用二维动态规划数组dp[i][j]表示前i个物品放入容量为j的背包可获得的最大价值，以下说法正确的是？
wt
val
dp[i][j]
i
j
初始化时dp[0][j] = val[0]当j >= wt[0]，否则为0
dp[0][j] = val[0]
j >= wt[0]
递推公式为：当j >= wt[i-1]时，dp[i][j] = max(dp[i-1][j], dp[i-1][j - wt[i-1]] + val[i-1])；当j < wt[i-1]时，dp[i][j] = dp[i-1][j]
j >= wt[i-1]
dp[i][j] = max(dp[i-1][j], dp[i-1][j - wt[i-1]] + val[i-1])
j < wt[i-1]
dp[i][j] = dp[i-1][j]
二维DP实现的遍历顺序必须先遍历背包容量，再遍历物品
一维滚动数组优化的0-1背包实现中，遍历背包容量时从前往后（从小到大）遍历也能保证正确性