无锡网站搜索引擎优化,石家庄是几线城市,专业搭建网站,采集微信公众号 做网站#x1f4cc;题目描述
#x1f4cc;解题思路
#x1f4cc;完整代码 #x1f4cc;举例 #x1f4cc;题目描述 #x1f4cc;解题思路 动态规划#xff08;DP#xff09; 问题#xff0c;核心是 “前 i 种物品#xff0c;每种物品最多可以使用x 次#xff0c;组成总和…题目描述
解题思路
完整代码 举例 题目描述 解题思路 动态规划DP 问题核心是 “前 i 种物品每种物品最多可以使用x 次组成总和 j 的方案数” dp[i, j] dp[i - 1, j] dp[i - 1, j - 1] ... dp[i - 1, j - a[i]] 完整代码
#include iostreamusing namespace std;const int N 110, mod 1000007;int n, m, dp[N][N];int main()
{cin n m;dp[0][0] 1; // 初始化0个物品凑成0的方案数为1for (int i 1; i n; i){int x;cin x; // 读取物品 i 可用的最大次数for (int j 0; j m; j){// k 不能超过当前背包容量 j也不能超过当前物品数量 xfor (int k 0; k j k x; k){dp[i][j] (dp[i][j] dp[i - 1][j - k]) % mod;}}}cout dp[n][m] endl; // 输出方案数return 0;
}三重循环 外层 i遍历 n 个物品中层 j遍历 0~m 的总和内层 k最多遍历 x 次。 时间复杂度O(n × m × x) 在 x 取较大值时可能会 超时。 举例
n 33种花m 5总共需要摆放5朵花每种花的数量限制如下
第1种花最多可以用3次。第2种花最多可以用2次。第3种花最多可以用1次。
迭代第1种花 dp[1][0] 1
dp[1][1] 1
dp[1][2] 1
dp[1][3] 1
dp[1][4] 0
dp[1][5] 0迭代第2种花 dp[2][0] 1
dp[2][1] 2
dp[2][2] 3
dp[2][3] 4
dp[2][4] 2
dp[2][5] 1 迭代第3种花 dp[3][0] 1
dp[3][1] 3
dp[3][2] 6
dp[3][3] 10
dp[3][4] 11
dp[3][5] 10
最终dp[3][5] 10表示用3种花摆放5朵花的方案数为10。
