动态规划

2024-06-30 21:13| 来源: 网络整理| 查看: 265

本文章是对于完全背包一些题型(如题目所示，组合、排列和最小值类型)的总结和理解，依次记录一下，方便回顾与复习。

本文章是基于个人所总结实现的，但在其中遇到了一些疑惑与困难，所以总结一篇与完全背包相关的问题。

题型分为完全背包求组合问题、求排列问题、求最小值问题.

但这一切都是基于完全背包，我们先来介绍一下什么是完全背包。

完全背包问题

二维dp

二维优化

一维dp(滚动数组)

完全背包组合和排列问题

完全背包问题

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，其价值为value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。(即如何在有限的空间中尽可能放到整体价值最高).

完全背包和01背包问题唯一不同的地方就是，完全背包每种物品有无限件；而01背包每个物品只有一件。

在这里我认为对你对01背包已经有一定的了解，便不再深入赘述。如果不了解01背包，最好先了解之后再继续阅读。

二维dp

这是 01背包的核心代码

// 二维数组 vector dp(weight.size(), vector(bagweight + 1, 0)); // 初始化 for (int j = weight[0]; j max (dp[i-1][j-weight[i] * k] + value[i]*k), dp[i-1][j] }.

其中(1

【本文地址】

公司简介

联系我们