吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 3360|回复: 1
收起左侧

[会员申请] 申请会员ID:longlongtime

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

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

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

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

Hmily 发表于 2020-3-27 13:38
抱歉,未能达到申请要求,申请不通过,可以关注论坛官方微信(吾爱破解论坛),等待开放注册通知。
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-3-28 20:10

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表