背包问题

一不小心，背包问题就结束了呢，刚学完acwing里的背包，得看书和找个问题巩固下

其实背包问题就是最基本的dp，最主要的状态转移方程要弄清楚，每一步选什么，怎么选，选几个都是很重要的问题

在这里我要diss我自己，明明多重背包学过了，后来做了一道题，一个循环的方式和里面的明明很像，做错了，hhh....

功夫不到家，dp的题要多练，没办法，多多积累经验吧

好，言归正传

学背包的时候，从二维开始入手，弄清楚每一步的意思，然后通过一维来优化，分析嘛，可以用闫式分析法，嘻嘻

01背包：

就是有n个物品和m的背包容量，告诉你价值，每个物品只能选一次，问求得的最大价值：

这里的每个物品只能选一次很关键啊，这里决定了到底用的是正序还是逆序，（具体为什么看之前的博客hhh）

所以咱们就先把所有的情况枚举下来，一个个来看

从第一个开始判断选还是不选，第二个再判断选还是不选，第三个再判断...一直判断到最后一个，选还是不选

这也就是01背包的名字的来源，0和1代表着选还是不选

所以状态转移方程就是//这里令f[i][j]是背包容量为j的情况下，第i的物品的最优解

f[i][j]=max(f[i-1][j],f[i-1][j-v[i])+w[i])

#include
using namespace std;
const int N=1e3+10;
int f[N][N],v[N],w[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j<v[i])
                f[i][j]=f[i-1][j];
            else
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<endl;
    return 0;
} 

转化到一维的情况：就是f[j]为背包容量为j下的最优解（为什么可以转化：题目意思很明确让求n个物品的最大价值，所以说又干嘛浪费空间去把每第几个物品的最优解求出来呢）

然后在不选的时候，反正不选也就不选了，背包容量没有任何改变，所以还是f[j]，状态转移方程是:

f[j]=max(f[j],f[j-v[i]]+w[i])

#include
using namespace std;
const int N=1e3+10;
int f[N],v[N],w[N];
int main(){
    int n,m;
    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<endl;
    return 0;
} 

分组背包：

这个可能看起来和01背包最像了，（个人认为），并不是说代码啥的像，而是思想方法很像，完全就是选与不选的问题，这个像是01背包的拓展吧

问题就是把物品们分组了，但是这每一组只能选择一个，其他条件都一样

这个就是枚举每个组数，这下的描述方法就要改一下了，刚刚的01背包是枚举n个物品，看看第i个选还是不选。这个分组背包，因为每组只能选1一个，就枚举每个分组

这下的描述是：要么选第1个，要么选第2个，要么选第3个...要么选第n个，所以直接用n个物品，求最大值就是了，很简单

#include
using namespace std;
const int N=110;
int f[N],v[N],w[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i)
    {
        int s;
        cin>>s;
        for(int j=0;j>v[j]>>w[j];
        for(int j=m;j>=0;j--)
        {
            for(int k=0;k)
            {
                if(j>=v[k])
                    f[j]=max(f[j],f[j-v[k]]+w[k]);
            }
        }
    }
    cout<endl;
    return 0;
} 

看代码，注意啊！！！这里的j是从大到小枚举体积（因为只能选择一次），for(int j=m;j>=0;j--)这里的j>=0,因为思维定势，我之前写成了j>=v[i]，还想不明白....但其实，要弄清楚原理啊，

之前的>=v[i]是枚举i个物品的时候背包容量要大于等于物品体积，那个时候i枚举的就是物品，而这里不一样，这里的i枚举的是分组，而真正的决策是在k上面，就是选与不选的问题

没办法判断了，所以>=0枚举，不过在全部枚举的时候最后加了个判断条件么，这里的细节需要弄清楚！

多重背包：

这里的多重背包就加了个条件而已，就是某个物品最多可以选择s次，就这个，我喜欢把它拆成01背包来写嘻嘻嘻嘻

所以啊，枚举决策个数的时候，多加了个循环，这里要看数据范围了，如果很小就是可以三层for循环，很大就是简单粗暴的拆成01背包再优化（使用二进制）

小数据：

#include
using namespace std;
const int N=110;
int f[N][N],v[N],w[N],s[N];
int main(){
    int n,m;
    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++)
            {
                f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
            }
        }
    }
    cout<endl;
    return 0;
} 

大数据：

#include
using namespace std;
const int N=1e5+10;
int f[N],v[N],w[N];
int main(){
    int n,m;
    cin>>n>>m;
    int t=0;
    for(int i=0;i)
    {
        int a,b,c;
        cin>>a>>b>>c;
        int k=1;
        while(k<=c)
        {
            t++;
            v[t]=a*k;//t就是存数组的下标 
            w[t]=b*k;//k是二进制分堆 
            c-=k;
            k*=2;
        }
        if(c>0)
        {
            t++;
            v[t]=a*c;
            w[t]=b*c;
        }
    } 
    n=t;
    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<endl;
    return 0;
}

在这里我想放个题，没啥为什么，就是心血来潮：

题目描述
有一家奇怪的银行，每次只允许顾客存一定量的钱，具体规定如下：
1.存1元
2.存6元，36元，216元...6^k元
3.存9元，81元，729元...9^k元
现在假设你有A元想存入银行，至少要存几次呢？
输入
一个数 A
输出
一个数，最少要存的次数
样例输入 Copy
127
样例输出 Copy
4
提示
A<=100000
样例解释：
4次分别为：1，9，36，81元

这个我把数据存到数组里，强硬的想转化成01背包来写，不对的，因为某一个数可以被使用很多次，应该用无限次，应该用完全背包，但试了试还是不对...

然后就用dp来写，不过循环的条件我没设置好，感谢某位陈大佬的修改！！嘻嘻

#include
#include
using namespace std;
const int N=1e5;
int dp[N];
int main(){
    int n;
     cin>>n;
     dp[0]=0;
     dp[1]=1;
     for(int i=2;i<=n;i++)
     {
          dp[i]=dp[i-1]+1;
          for(int x=6;x<=i;x=x*6)
              dp[i]=min(dp[i], dp[i-x]+1);
          for(int x=9;x<=i;x=x*9)
              dp[i]=min(dp[i], dp[i-x]+1);
     }
     cout<endl;
}
/* 127可以由126得到，可以由某个数加上9^k得到，可以由某个数加上6^k得到
 令dp[i]是最少的次数
 dp[i]=dp[i-1]+1;
 dp[i]=min(dp[i],dp[i-6^k]+1);
 dp[i]=min(dp[i],dp[i-9^k]+1);
*/

接下来就是完全背包了，这个虽然代码就是一个顺序，一个逆序，其他都没变，可是本质却差太多了，这个y总是用公式严格的推导出来的，在之前的博客也有写到，这里就不重复啦

#include
using namespace std;
const int N=1010;
int f[N],v[N],w[N];
int main(){
    int n,m;
    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<endl;
    return 0; 
} 

这些是我现在学的全部的背包问题了，如果以后再有拓展再来补充，咕噜咕噜

**************************************我是分割线，嘻嘻。

明天就开线性DP咯，开森呢！！数据结构两天没碰了...明天继续！加油！