动态规划的一维优化问题

举个例子,0-1背包转移方程如下
图片说明
图片说明
dp数组第i行所依赖的其实都在第i-1行
故可以减去一维
关键思想在于如何实现dp[c] = max(dp[c],dp[c-v[i]]+w[i])
这里最大的问题是式子里,左边的代表第i行,右边的代表第i-1行,dp数组i-1行的值不能在使用之前被第i行的替换掉了,故选择从C->0的顺序遍历。需要确保dp[c-v[i]]存储的是上一行的值,即确保还没有被更新,所以遍历方向是从大到小即

 for (int i = 0; i < N; i++) {
            for (int j = C; j >= v[i]; j--) {
                // 不选该物品
                int n = dp[j]; 
                // 选择该物品
                int y = dp[j-v[i]] + w[i]; 
                dp[j] = Math.max(n, y);
            }
        }

完全背包的转移方程如下:
图片说明
进行一维优化后的状态转移方程如下:
图片说明
与0-1背包不同的是,右边最后一个式子是第i行的值,故要确保它已更新
故是从小到大遍历

for (int i = 0; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况(选择 0 件物品 i)
                int n = dp[j];
                // 考虑第 i 件物品的情况
                int y = j - v[i] >= 0 ? dp[j - v[i]] + w[i] : 0; 
                dp[j] = Math.max(n, y);
            }
        }

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-27 14:35
天津大学_2023
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-11-29 17:43
北京大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-12 12:42
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议