申请会员ID:longlongtime
1、申请ID：longlongtime2、个人邮箱：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
我在之前曾经申请过，这使我有点不敢再申请。这段时间我努力进步，写了一些文章，还是希望能在论坛内与大家交流。请通过我的申请吧！ 抱歉，未能达到申请要求，申请不通过，可以关注论坛官方微信（吾爱破解论坛），等待开放注册通知。
页:
[1]