现有无限张面额分别为1、2、5的硬币,要求计算凑成总金额5的不同排列数目(顺序不同视为不同方案,如1+2和2+1属于两种不同方案),该问题属于完全背包变种,下列实现逻辑描述正确的是?

wa503352 单选题 共 个子题

普通完全背包问题默认求最大价值或不考虑顺序的组合数,本题考查完全背包求排列数的核心差异点。

A

外层遍历背包容量从小到大,内层遍历硬币面额,dp数组定义为dp[i]表示凑成金额i的排列数,初始dp[0]=1,转移方程为dp[i] += dp[i - coin](当i >= coin时),该实现可得到正确结果

B

外层遍历硬币面额,内层遍历背包容量从小到大,其余逻辑同选项A,该实现可得到正确结果

C

为了避免硬币被重复计数,内层遍历背包容量必须从大到小,其余逻辑同选项A,该实现可得到正确结果

D

该问题需要考虑选择顺序,无法基于完全背包模型求解,只能通过回溯法暴力枚举所有方案统计结果

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧