完全背包问题DP详解

发布于:2023-01-07 ⋅ 阅读:(451) ⋅ 点赞:(0)

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

第 i 种物品的体积是 vi,价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围:

0<N,V≤10000
0<vi,wi≤10000

输入样例:

4 5
1 2
2 4
3 4
4 5

输出样例:

10

 f[i][j]表示从前i个物品中选,选出的物品体积之和 <= j的最优解(价值最大)

所有物品的状态都只有 不选 ,选一个,选两个,选k个.......知道背包装不下为之:

所以从:

MAX :   f[i -1][j]  <不选第i个>、f[i -1][j - v[i]] + w[i]、f[i -1][j - 2 * v[i]] + 2 * w[i]、f[i -1][j - k * v[i]] + k * w[i -1] ... 

但是这一个max函数中太多元素了,我们可以发现:

f[i][j - v[i]] <把j 看成j - v[i]> :  把v[i]看成本层的v,w[i]看成本层的w

对比f[i][j]=max: f[i - 1][j] , f[i - 1][j - v] + w , f[i - 1][j - 2v] + 2w , f[i -1][j - 3v] + 3w...

  f[i][j - v]= max:               f[i - 1][j - v] ,        f[i - 1][j - 2v] + w,    f[i - 1][j - 3v] + 2w...

对比发现:f[i][j - v[i]]只是比f[i -1][j - v[i]] + w[i]、f[i -1][j - 2 * v[i]] + 2 * w[i]、f[i -1][j - k * v[i]] + k * w[i -1] ... 

这一堆选1 2 3 4 k...到选不了为之的每一项少一个w[i],在max函数计算后最终结果少个w[i]

所以f[i -1][j - v[i]] + w[i]、f[i -1][j - 2 * v[i]] + 2 * w[i]、f[i -1][j - k * v[i]] + k * w[i -1] ... 这一坨可以等价替换成 f[i][j - v[i]] + w[i]  《注意这里第一维从上一次的 i - 1 换成本层的i了,所以优化成一维后要从小到大遍历,在遍历到 j 之前要先遍历到本层的 j - v[i],更新结果》

所以最终结果的不选:f[i - 1][j] 和 其他选1 ~ 选不了的个数 :f[i][j - v[i]] + w[i] 了;

其他细节与 01背包问题同理, j 从 0 ~ v[i] - 1可以省去遍历,只能选0个第i层物品,所以结果还等与上一层的f[j],结果不变不用再遍历一遍更新了,与 01背包主要区别就是要正着遍历,因为完全背包计算过程,推导结果 f[i][j] = max(f[i - 1][j],f[i][j - v[i]] + w[i]);  中 ,f[i] 为本层遍历结果

具体代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int w[N],v[N];  // f[N][N]
int n,m;
/*         朴素写法
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++ )
        cin >> v[i] >> w[i];
    for(int i = 1;i <= n;i ++ )
        for(int j = 0;j <= m;j ++ )
        {
            if(j >= v[i])
                f[i][j] = max(f[i - 1][j],f[i][j - v[i]] + w[i]);
            else
                f[i][j] = f[i - 1][j];
        }
    cout << f[n][m] << endl;
    return 0;
}
*/
//               优化写法
int f[N];
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++ )
        cin >> v[i] >> w[i];
    for(int i = 1;i <= n;i ++ )
        for(int j = v[i];j <= m;j ++ )
                 f[j] = max(f[j],f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}


网站公告

今日签到

点亮在社区的每一天
去签到

热门文章