动态规划——完全背包问题(公式推导，组合、排列)

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

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

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

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

目录

完全背包问题

二维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  max (dp[i-1][j-weight[i] * k] + value[i]*k), dp[i-1][j] }.