✏️ 纠错
第 216 题 / 共 226 题
第 15 题 给定n个物品和⼀个最大承重为W的背包，每个物品有⼀个重量wt[i]和价值val[i]，每个物品只能选择放或不放。⽬标是选择若干个物品放入背包，使得总价值最大，且总重量不超过W，则横线上应填写（ ）。
你真棒！
📝 题目解析
答案：D
考纲知识点：动态规划（01背包问题的状态转移）
详细解析：01 背包的核心是 “每个物品仅选或不选”，状态转移需比较两种情况：不选第i个物品：dp[w]保持不变；选第i个物品：dp[w - wt[i]] + val[i]（承重w-wt [i]的最大价值+第i个物品的价值）。因此状态转移方程为dp[w] = max(不选的价值,选的价值)，即dp[w] = max(dp[w], dp[w - wt[i]] + val[i])，对应选项D。
考纲知识点：动态规划（01背包问题的状态转移）
详细解析：01 背包的核心是 “每个物品仅选或不选”，状态转移需比较两种情况：不选第i个物品：dp[w]保持不变；选第i个物品：dp[w - wt[i]] + val[i]（承重w-wt [i]的最大价值+第i个物品的价值）。因此状态转移方程为dp[w] = max(不选的价值,选的价值)，即dp[w] = max(dp[w], dp[w - wt[i]] + val[i])，对应选项D。