第31272题 单选题
已知有面额为1、2、5的三种硬币,每种硬币数量无限制,需要凑出总金额11的最少硬币数,该问题属于完全背包变种应用,下列说法正确的是?

基础完全背包模型定义为:给定n种物品和容量为V的背包,每种物品可无限次选取,求装入背包的最大物品总价值。请结合该模型判断下列选项的正确性。

A

dp[i]定义为凑出金额i所需的最少硬币数,初始化时需将dp数组所有元素赋值为0,最终dp[11]即为答案

B

状态转移方程可写为dp[i] = min(dp[i], dp[i - coin] + 1),遍历金额时需从小到大遍历,保证同种硬币可被多次选取

C

遍历金额时需从大到小遍历,避免同一种硬币被重复选取,降低算法时间复杂度

D

该问题与基础完全背包的求解目标完全一致,仅状态定义存在差异

程序运行统计
暂无判题统计
提交0次 正确率0.00%
答案解析