K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
基础完全背包模型定义为:给定n种物品和容量为V的背包,每种物品可无限次选取,求装入背包的最大物品总价值。请结合该模型判断下列选项的正确性。
dp[i]定义为凑出金额i所需的最少硬币数,初始化时需将dp数组所有元素赋值为0,最终dp[11]即为答案
状态转移方程可写为dp[i] = min(dp[i], dp[i - coin] + 1),遍历金额时需从小到大遍历,保证同种硬币可被多次选取
遍历金额时需从大到小遍历,避免同一种硬币被重复选取,降低算法时间复杂度
该问题与基础完全背包的求解目标完全一致,仅状态定义存在差异