动态规划之完全背包问题

动态规划之完全背包问题 题目描述

3. 完全背包问题 - AcWing题库

有  种物品和一个容量是  的背包，每种物品都有无限件可用。

第  种物品的体积是 ，价值是 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，，用空格隔开，分别表示物品种数和背包容积。

接下来有行，每行两个整数 ，，用空格隔开，分别表示第 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

题目分析 

完全背包问题在性质与解法上其实就是01背包的姊妹篇

动态规划之01背包问题_AryCra_07的博客-CSDN博客

（如果您并不了解01背包建议浏览一下上面的博客，以获得一些基本的分析）

它们唯一的区别在于，完全背包问题中每件物品有无限个，而01背包问题只有1个。

同样，我们令表示前件物品放进容量为的背包中所能获得的最大价值。

同样，对于任意物品我们有两种策略：

不放第件物品，有；放第件物品。这里与01背包不同的地方在于，由于每件物品可以放任意件，所以只要背包容量允许，我们可以放进去很多个第件物品，直到第二维的小于0为止。所以状态转移方程为边界条件：

看上去和01背包很像，唯一的区别在于max的第二个参数是而不是。

那么根据我们在01背包那篇博客里的分析，这里的状态转移方程可以很方便地转成一维形式，并且不再有烧脑的逆序遍历 *** 作。一维状态转移方程：

边界条件：

这里与01背包的区别在于，完全背包是正序遍历。

给出代码：

#include 
#include 
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N];
int main(){
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%d%d", &v[i], &w[i]);
    for(int i = 1; i <= n; i ++)
        for(int j = v[i]; j <= m; j ++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    printf("%dn", dp[m]);
    return 0;
}