首页 > 宝盒
开通博客写题解
头像 shyyhs
发表于 2020-04-04 18:37:45
大水题..先介绍下第一种做法dp观察数据易知..每个数大概就是0~100之间,然后最多100组,所以建立一个dp数组dp[i][j]表示到第i组,价值为j的数量是多少?然后转移就更简单了,思想就是桶,你这个转态肯定是有上一个转态+a[i][j]组成a[i][j]表示第i组位于j的价值..然后注意把第 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 _LRJ_
发表于 2020-04-08 20:43:05
题意是：给你n个背包，每个背包装了mi个物品，每个背包选一个，要求出选出物品价值前k小 的不同方案种数，很容易联想到背包dp。那么怎么做呢？我们可以考虑dp[i][j]表示前i个背包选出来价值和为j的方案个数，则有 dp[i][k]+=dp[i-1][k-a[i][j]];这个是状态转移方程，具体看 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 CCCCCHHHGG
发表于 2020-04-11 14:05:57
背包dp问题 dp[i][j] 是在前i个背包内选择价值j的方案数状态转移方程是dp[i][j] += dp[i - 1 ][j - a[i][j]]dp[0][0] = 1 代表的意义是在前 0 个背包 价值为 0的方案数是1 #include <iostream> #include 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”