DP 动态规划(一) ——背包问题学习总结（闫氏DP分析法）

CPT1024 2023-09-29 原文

🌟一、了解动态规划DP

指的是将一个复杂的问题，分解成简单的问题（用一种递归的方式）——WIKI
本质：分治（与递归没有本质区别）+ 最优解，很多就是一些细节的不同。

🌟二、闫式DP分析法

y总的方法

🌟三、01背包 [DP入门]

[0-1]背包最基础动态规划，也是所以背包问题的基础，特点是：每种物品仅有一件，可以选择放或不放。
题目链接
题目

闫式DP分析
①状态表示

集合f[i][j]:所有只从前i个物品中选,并且总体积≤j的选法的【核心】请记住这句话，DP就是一直围绕这句话实现的
属性：MAX

②状态计算

当前背包容量不够（j < v[i]），没得选，因此前 i 个物品最优解即为前 i−1个物品最优解：f[i][j] = f[i - 1][j]。
如果可以选：f[i][j] = f[i - 1][j - v[i]] + w[i]。

③二维分析过程↓

就第一步举例：首先对f(4,8)的理解，其中4是指第i个物品就行选择（选 or不选），8是指背包的容量，看图，下一步是f(3,x) 表示是对第4个物品进行了抉择（不管选还是不选 4必须减去1），如果选择的话，背包容量就会减去第i个物品的体积（表示当前背包容量），后面加上的第i物品价值 +w[i], 图中的+8，就是现在背包的价值.。

代码
二维写法
时间复杂度 O(n*m)

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];//v:体积  w：价值
int f[N][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 = 1; j <= m; j ++) {
                f[i][j] = f[i - 1][j];
            if (j >= v[i]) {
                 f[i][j] =max (f[i][j],f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

一维写法 [优化：对代码等价变形]

优化↓

for (int i = 1; i <= n; i ++) {
        //for (int j = 1; j <= m; j ++) { 更改顺序
            for(int j = m; j >= 0; j --) {
            if (j < v[i]) {//体积超出背包容量，不选
                //f[i][j] = f[i - 1][j];
                f[j] = f[j] //优化
            }
            else  {//决策要不要选
                //f[i][j] =max (f[i - 1][j],f[i - 1][j - v[i]] + w[i]);
                f[i][j] = max(f[j], f[j - v[i]] + w[i]); //优化
            }
        }
    }

进一步优化↓

for(int i = 1; i <= n; i++)
{
    for(int j = m; j >= v[i]; j --) { //可以选时才会更新状态
        f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
}

终极版本

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];//v:体积  w：价值
int f[N];//集合表示 一开始全为0

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 = m; j >= v[i]; j --) { //可以选时才会更新状态
          f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    } 
    cout << f[m] << endl;
    return 0;
}

🌟四、完全背包

与 [0-1]背包的区别 ——每件物品可以选无限次
题目链接

题目

闫式DP分析

先从朴素(baoli)算法时间复杂度接近 O(n³)

优化：错位相减的思路↓

图中橘色部分与f[i,j-v]相差w
得到：f[i][j]=max(f[i-1][j],f[i,j-v]+w ) 完全背包
对比：f[i][j]=max(f[i][j],f[i,j-v]+w ) 01背包

最终代码

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];//v:体积  w：价值
int f[N];//集合表示 一开始全为0

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;
}

🌟五、多重背包

与完全背包有点相似 —— 每件物品最多有 s[i]种选择
题目链接

朴素做法

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;//物品 体积
int v[N], w[N], s[N];// 体积 ：价值 ：个数
int f[N][N];//集合
int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> v[i] >> w[i] >> s[i];
    }
    for (int i = 1; i <= n; i ++) { //枚举种类
        for (int j = 0; j <= m; j ++) {//枚举体积
            for (int k = 0; k <= s[i] && k * v[i] <=j ; k++) { //枚举第i个物品选多少个
                            //个数限制     体积限制
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

优化

用前面错位相减的思路这道题用不了

如果一件一件选的话，暴力时间复杂度：O(n³) 而且数据类型还是1000 + 一定会TLE
所以， 考虑二进制优化 —> 优化后时间复杂度 : O(nlogn)
步骤：拆分第i件物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2^(k) , s[i]-2^k+1 + 1.(C)[下图的C]，且k是满足s[i] - 2^k+1 + 1>0 的最大整数,并且C < 2^k+1。

举个栗子，如果s[i]为13，就将这种物品分成系数分别为1,2,4,6(C)的四件物品。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 25000;//2000 * log2 1000
int n, m;
int v[N], w[N];
int f[N];
int cnt = 0;//记录物品编号

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int a, b, s;//体积：价值：个数
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s) {
            cnt++;
            v[cnt] = a * k; 
            w[cnt] = b * k;
            s -= k;
            k *= 2;	//二进制优化
        }
        if (s >0) {//补上最后的C
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt; //更新n
    for (int i = 1; i <= n; i ++) {
        for (int j = m; j >= v[i]; j --) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
  
}

🌟六、分组背包问题

与前面的背包的区别 ——前面背包都是每件物品选几次，而分组背包问题是第i组物品选哪个？
题目
题目链接

思路

把分组背包问题 化解为 01背包问题

AC代码

朴素做法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int s[N], f[N][N], v[N][N], w[N][N];
int n, V;

int main () {
    cin >> n >> V;
    for (int i = 1; i <= n; i ++ ) {
        cin >> s[i];
        for(int j = 1; j <= s[i]; j ++) {
            cin >> v[i][j] >> w[i][j];
        }
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++ ) {
        for(int j = V; j >= 0; j --) {
            f[i][j] = f[i - 1][j];
            for(int k = 1; k <= s[i]; k ++) {
                if(j >= v[i][k])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }
    
    cout << f[n][V] << endl;
    return 0;
}

优化为一维

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N],s[N];//s：每组物品个数
int f[N];

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {//枚举所有体积
        cin >> s[i];//读入每一组的体积 和价值
        for (int j = 0; j < s[i]; j ++) {
            cin >> v[i][j] >> w[i][j];
        }
    }
    for (int i = 1; i <= n;i ++) {   // 枚举每一组物品 s
        for (int j = m; j >= 0; j --)//从大到小枚举每一组体积 同前面背包
            for (int k = 0; k < s[i]; k ++) { //枚举所有选择 
                if (v[i][k] <= j) {
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                }
            }
    }
    cout << f[m] << endl;
    return 0;
  
}

🌟七、个人总结

01背包 & 完全背包

原式：
[01]f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
完全背包f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
一维：f[j] = max(f[j], f[j - v[i]] + w[i])[相同]

for(int i = 1; i <= n; i++) {
        for(int j = m; j >= v[i]; j --) { //01背包
     // for(int j = v[i]; j <= m; j --) { //完全背包
          f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

为什么01背包按照V…0 逆序，而完全背包于此相反？
如果转移的时候用的是上一层i - 1的状态的话，就从大到小来枚举体积[可以保证我们算体积所用到的体积都是没有被计算过的 ] 即要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来的。。如果是本层i的状态的话（完全背包），于此相反就要从小到大来枚举体积【因为完全背包：每种物品可选无限件，考虑选第i件物品的时候，却正需要一个可能已选入第i种物品的子结果f[i][j-v[i]]】。

多重背包&多组背包

多重背包：采用二进制优化为01背包问题
多组背包：多了枚举每一组物品，从而转化为01背包问题

🌟 八、文章参考

y总的算法基础课

🌟 九、最后

分享一段学习中看到的快乐

感谢你能看完，如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞鼓励下🌹🌹🌹

有关DP 动态规划(一) ——背包问题学习总结（闫氏DP分析法）的更多相关文章

ruby - 在 Ruby 中动态创建数组 - 2
有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.
ruby - 是否可以将 IRB 提示配置为动态更改？ - 2
我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO
ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2
首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟
ruby - 在 Ruby 中动态生成多维数组 - 2
我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常，但在我的实际使用中，我不会事先知道需要多少个数组。有一个更好的方法吗？谢谢最佳答案不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]
ruby-on-rails - 使用 gmaps4rails 动态加载谷歌地图标记 - 2
如何只加载map边界内的标记gmaps4rails？当然，在平移和/或缩放后加载新的。与此直接相关的是，如何获取map的当前边界和缩放级别？最佳答案我是这样做的，我只在用户完成平移或缩放后替换标记，如果您需要不同的行为，请使用不同的事件监听器:在你看来(index.html.erb):{"zoom"=>15,"auto_adjust"=>false,"detect_location"=>true,"center_on_user"=>true}},false,true)%>在View的底部添加:functiongmaps4rail
ruby - 动态方法链？ - 2
如何在对象上调用方法名称的嵌套哈希？例如，给定以下哈希:hash={:a=>{:b=>{:c=>:d}}}我想创建一个方法，给定上面的散列，执行以下操作:object.send(:a).send(:b).send(:c).send(:d)我的想法是我需要从一个未知的关联中获取一个特定的属性(这个方法不知道，但程序员知道)。我希望能够指定一个方法链来以嵌套哈希的形式检索该属性。例如:hash={:manufacturer=>{:addresses=>{:first=>:postal_code}}}car.execute_method_hash(hash)=>90210
ruby - 如何使用 method_missing 动态声明方法？ - 2
我有一个ruby程序，我想接受用户创建的方法，并使用该名称创建一个新方法。我试过这个:defmethod_missing(meth,*args,&block)name=meth.to_sclass我收到以下错误:`define_method':interningemptystring(ArgumentError)in'method_missing'有什么想法吗？谢谢。编辑:我以不同的方式让它工作，但我仍然很好奇如何以这种方式做到这一点。这是我的代码:defmethod_missing(meth,*args,&block)Adder.class_evaldodefine_method
ruby - 动态扩展现有方法或覆盖 ruby 中的发送方法 - 2
假设我们有A、B、C类。Adefself.inherited(sub)#metaprogramminggoeshere#takeclassthathasjustinheritedclassA#andforfooclassesinjectprepare_foo()as#firstlineofmethodthenrunrestofthecodeenddefprepare_foo#=>prepare_foo()neededhere#somecodeendendBprepare_foo()neededhere#somecodeendend如您所见，我正在尝试将foo_prepare()调用注入
ruby - 使用 jbuilder 创建具有动态哈希键的 JSON - 2
这里我想输出带有动态组名的json而不是单词组@tickets.eachdo|group,v|json.group{json.array!vdo|ticket|json.partial!'tickets/ticket',ticket:ticketend}end@ticket是这样的散列{a:[....],b:[.....]}我想要这样的输出{a:[.....],b:[....]} 最佳答案感谢@AntarrByrd，这个问题有类似的答案:JBuilderdynamickeysformodelattributes使用上面的逻辑我已经
ruby - 在 Rakefile 中动态生成 Rake 测试任务(基于现有的测试文件) - 2
我正在根据Rakefile中的现有测试文件动态生成测试任务。假设您有各种以模式命名的单元测试文件test_.rb.所以我正在做的是创建一个以“测试”命名空间内的文件名命名的任务。使用下面的代码，我可以用raketest:调用所有测试require'rake/testtask'task:default=>'test:all'namespace:testdodesc"Runalltests"Rake::TestTask.new(:all)do|t|t.test_files=FileList['test_*.rb']endFileList['test_*.rb'].eachdo|task|n

DP 动态规划(一) ——背包问题 学习总结（闫氏DP分析法）

目录