发表于 2020-3-26 08:23

申请会员ID:longlongtime

1、申请ID:longlongtime
2、个人邮箱:robot1497833202@163.com
3、原创技术文章:“无敌复杂”“无敌难”的C++背包问题
背包问题总是被许多“年轻”同学叨叨:“诶亚,这么难,我做不了! ”“我才不想做哩 ”
今天,我给大家分享整理一下我做背包问题的整体思路与算法。
背包问题的终极框架:“01背包”
【例n】有一个旅行者,他有一个无敌的背包,容量大得很:V。然后,他有N件不知名的物品,把某件物品放入背包可以获得这件物品的价值c,又会使无敌背包减少还能装下的重量。所以,现在他想要让背包装得下,又要让自己获得最大的价值,请问,应该放哪些物品呢?

第一眼看上去似乎难到不得了。我第一次学习背包问题时的想法使者样的:(请勿学习)
“嘿嘿,我把每个物品的价值除以重量,不就得到了平均价值了吗?”
似乎看上去很对呀~ 可惜,我没办法把费用和价值放在一块,却又增加一个平均价值?岂不是更复杂?

希望读者都学过动态规划。。在这里我就讲一下不讲了吧 ~~谅解谅解
终极框架的特点
最基础最基础···(*100)的背包问题,每个物品只有一个,放,或者不放。
啊哈,“01”的意思就是一个。真是明白。
推导子问题定义状态
用f 表示前i件物品(不放、部分、全部)放入容量为v的背包可以获得的最大价值,则其状态转移方程就是:
f(i)(v)=max(f(i−1)(v),f(i−1)(v−w(i))+c(i))f(i)(v)=max(f(i−1)(v),f(i−1)(v−w(i))+c(i))
如果你没看懂,那恭喜你,你终于迈不进迈进了背包问题的大门。
别着急,我来讲解一下:
f(i)(v)f(i)(v)
不用讲了吧
max应该也知道了吧(虽然我第一次时不知道max是最大的意思)
f(i−1)(v)f(i−1)(v)
意思是第i件物品不放进去,重量没有变化,但处在的物品发生了改变,所以i-1
f(i−1)(v−w(i))+c(i)f(i−1)(v−w(i))+c(i)
第i件物品放进去,首先是容量发生变化,减掉本次物品重量。其次加上物品的价值。
如果你这个方程看懂了,以后的其他什么“完全背包”“多重背包”的方程,你就能看的懂。
注意! 本方程有一个缺点,f有意义且仅当存在一个前i个物品的子集,其费用为v。所以,最终的答案并不是f而是f的最大值。不过,你只要把每一个f(读入)的初始值复位0,你就会发现f也是最终答案。
优化时间与空间
这样一来,时间复杂度和空间复杂度均为 O(N∗V)O(N∗V)   O(N*V)O(N∗V)。时间复杂度基本不能在进行优化了,但空间复杂度却可以优化为O(V)O(V)      O(V)O(V)。
在这里,我们先考虑上面的思路怎样实现。肯定有一个主循环for(1…n)每次算出来二维数组f的所有值。如果只用一个数组f能不能保证第i次循环完后f中表示着f呢?实际,这要求在每次主循环中我们以v=V…0的逆序推f,这样能保证f时f]保存的是状态f]的值。所以,伪代码如下:
for(i=1...N)
         for(v=V...0)
                  f=max{f,f]+c};12
其中,for(v=V…0)0是不必要的。都没有空间了,你还烦什么?所以,修改:
for(i=1...N)
         for(v=V...w)
                  f=max{f,f]+c};12
最后,提供上最终的代码:
#include<iostream>
#include<cstdio>
using namespace std;
int thing;         //重量(w)是thing[?],价值(c)是thing[?],f是thing[?]
int max(int a,int b)
{
          return a>b? a:b;
}
int main()
{
          int n,V;
          cin>>V>>n;
          for(int i=1;i<=n;i++)cin>>thing>>thing;
          for(int i=1;i<=n;i++)
                  for(intv=V;v>=thing;v--)
                  {
                        thing=max(thing,thing]+thing);
                }
         cout<<thing;
         return0;
}
————————————————
版权声明:本文为CSDN博主「robotlongtime」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/robotlongtime/article/details/105095786
我在之前曾经申请过,这使我有点不敢再申请。这段时间我努力进步,写了一些文章,还是希望能在论坛内与大家交流。请通过我的申请吧!

Hmily 发表于 2020-3-27 13:38

抱歉,未能达到申请要求,申请不通过,可以关注论坛官方微信(吾爱破解论坛),等待开放注册通知。
页: [1]
查看完整版本: 申请会员ID:longlongtime