关于初级动态规划（dp的背包问题）的理解和题目加解析~~（我要成为一个dp选手.jpg）

          动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

                                                                                                                                                                     -----百度百科；

DP全称是dynamic programming，这里programming不是编程，是一个表格保存之前的结果。

DP 是一种编程思想，主要用于解决最优解类型的问题。

其思路是为了求解当前的问题的最优解，使用子问题的最优解，然后综合处理，最终得到原问题的最优解。

要注意dp的两个原理：

（1）动态规划的最优化原理：

        作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，而非最优解对问题的求解没有影响。

（2）动态规划的无后效性原则：

        所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响过程未来的演变。

        即：一个问题被划分成各个阶段之后，阶段K中的状态只能由阶段K+1中的状态通过状态转移方程得来，与其它状态没有关系，特别是与未发生的状态没有关系。

简而言之dp是一种没有固定形式，只有固定思路想法的，就想A*算法一样，需要根据现实问题而变化。

这样我们来根据题目来学习下。

（1）sdnu 1033

100 5
77 92
22 22
29 87
50 46
99 90

133

这就是一道摸板题~正好用来梳理一下我们的思路~这里我们可以用数组ma[k]来表示在时间使用量为k时，此时我们能够取得的最大利益是多少~这样的话对于另一种方向上来看，我们如果要拿第s个物品~那么对于任意的ma[k]如果存在ma[k-we[s]]+v[s]>ma[k]的情况 ~~即在此刻，拿这个物品并使此时总使用时间为k时的利益，是比之前我们找到的最大利益要大的~~那么此时我们就更新此时的ma[k]的值就好~~。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ma[1005];
int tim[105],v[105];
int main()
{
    memset(ma,0,sizeof(ma));
    int m,n;
    cin>>m>>n;
    for(int s=1;s<=n;s++)
    {
        cin>>tim[s]>>v[s];
    }
    for(int s=1;s<=n;s++)
    {
        for(int ti=m;ti>=tim[s];ti--)
        {
            if(ma[ti]<ma[ti-tim[s]]+v[s])
            {
                ma[ti]=ma[ti-tim[s]]+v[s];
            }
        }
    }
    cout<<ma[m]<<endl;
    return 0;
}

有人问道为什么这个时候ti要从m到tim[s]进行~~反向不好吗？这个时候你想想，假设在第一个时刻你加了这件物品，然后往后推得时候，你可能会再次用到拿没拿这件物品而产生的结果~~进而这就不是每个物品只有一个了~而是在使用范围内有不限制数量个，才能从前往后推~来让后面的处理考虑的之前的拿n个而产生的情况。

（2）1043

100 5
77 92
33 50
34 60
50 46
99 161

161

这道题就是之前说的~~多件物品怎么处理。发核心代码

    for(int s=1;s<=n;s++)
    {
        for(int ti=tim[s];ti<=m;ti++)
        {
            if(ma[ti]<ma[ti-tim[s]]+v[s])
            {
                ma[ti]=ma[ti-tim[s]]+v[s];
            }
        }
    }

（3）sdnu1061

100 100 5
50 60 100
60 50 120
50 50 115
40 60 21
40 50 5

125

    这是一个有两个限制条件的dp，这样的话我们ma[a][b]来表示重量为a,体积为b时的最大利益是多少~这样的话一化简就好了~就相当于把第一个方程加了重循环。（mw，mv分别表示背包最大承受重量和容量）

    for(int s=1;s<=n;s++)
    {
        for(int a=mw;a>=we[s];a--)
        {
            for(int b=mv;b>=vol[s];b--)
            {
                if(ma[a][b]<ma[a-we[s]][b-vol[s]]+v[s])
                {
                    ma[a][b]=ma[a-we[s]][b-vol[s]]+v[s];
                }
            }
        }
    }

    （4）sdnu1077

100 5
55 40 59 44 2

1

           这道题他奇怪的地方是~他要求的不是最大利益，而是最小的空间剩余度，那么我们用ma[k]来表示能否用物品凑齐容量为k的空间。这样的话状态转移方程为     if(ma[w]&& !ma[w+we[s]]) ma[w+we[s]]=1;

这样的话我们在处理完之后从最大的m到0开始看，最先ma值为1的就是答案~

    for(int s=1;s<=n;s++)
    {
        for(int w=m-we[s];w>=0;w--)
        {
            if(ma[w]&&!ma[w+we[s]])
            {
                ma[w+we[s]]=1;
            }
        }
    }
    for(int s=m;s>=0;s--)
    {
        if(ma[s])
        {
            cout<<m-s<<endl;
            return 0;
        }
    }

（5）sdnu1520

18 22 100 44 100 2

400

         这道题其实跟第一题一样的~有n个同一个物体~跟有n个属性一样的物体~这两个表达有什么区别~~加一个循环就行了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ma[1005];
int we[105],vi[105],sum[105];
int main()
{
    int te;
    cin>>te;
    while(te--)
    {
        memset(ma,0,sizeof(ma));
        int m,n;
        cin>>m>>n;
        for(int s=1;s<=n;s++)
        {
            cin>>we[s]>>vi[s]>>sum[s];
        }
        for(int s=1;s<=n;s++)
        {
            for(int k=0;k<sum[s];k++)
            {
                for(int w=m;w>=we[s];w--)
                {
                    if(ma[w]<ma[w-we[s]]+vi[s])
                    {
                         ma[w]=ma[w-we[s]]+vi[s];
                    }
                }
            }
        }
        cout<<ma[m]<<endl;
    }
    return 0;
}