本周因为备考，学习时间主要挤在周末，所以题大多是囫囵吞枣式看的，看了大概20多道，这些DP题大多都比较复杂，需要理清自己的做题思路，并详细的思考前后关系，再得出状态转移方程。这也表示了普遍dp问题的一个重要的点：思路是关乎题目难度的重要标尺。

这两周的主要学习内容是关于背包内容的，以前我只知道有01背包问题，现在接触后才知道，还有完全背包，多重背包和分组问题的背包等等。这里面的01背包和完全背包思路其实是有相似处的，但主要差别点就是在状态转移方程上。

01背包的状态转移方程为：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}，

完全背包的状态转移方程为：

f[v]=max{f[v],f[v-c[i]]+w[i]}

两者的状态转移方程主要的差异点在于循环的起始位置和变化不同，这要具体在题上体现。

而对于多重背包，我认为就是一种复杂化的01背包问题。因为多重背包可以转化成01背包问题求解。解多重背包的思路比较直接：比如第i件物品有s个,我可以把同种的物品的进行合并,比如我拿出若干件合并出一个新的物品，重新参与背包问题，无论是2个，3个乃至若干个都可以。然后基于这种思想,把第i件的s个物品转换为s种体积各不相同的物品,然后在用01背包的思想,就可以求出最优解!

当然，多重背包问题也可以进行优化，根据学到的知识和看过的一些博客，了解到的有这么些方法：二进制优化，单调队列优化等，不过这个东西我的理解都是按照标准的解释来的，就不再罗列解释了。

对于分组的背包问题，其实也是可以理解为对01背包问题的升级，所以我们可以尝试用01背包的方法去思考：设f[i][j]为当前考虑的第i组物品，剩余容里为j的背包能装物品的最大价值，然后我们需要去枚举第i组物品，再考虑选哪一个物品时最优的(或者不选)，状态转移方程就是

if (j>=v[i][k])
   f[i][j] = max ( f[i][j] , f[i−1] [j−v [i][k]] + w [i][k] ) 
if(j>=v[i][k])
   f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k])
if(j>=v[i][k])
   f[i][j]=max(f[i][j],f[i−1][j−v[i][k]]+w[i][k])。

接下来，用几道题去阐述一下做题的思路：

HDU - 1114 Piggy-Bank

这是一道关于完全背包的题，就是用很基础的方式，就是保证挑选最大的最优值，代码很简洁。其实完全背包实际上就是对于挑选物品的另一种逻辑，保证先选一个满足空间条件的最优解，然后依次递推即可。

#include
using namespace std;
#define INF 0x3f3f3f3f
#define N 50010

int p[N],w[N];
int dp[N];
int main()
{
   int T,t,n,m,i,j;
   cin>>T;
   while(T--)
   {
      cin>>n>>m;
      int sum=m-n;
      for(i=1;i<=sum;i++)
          dp[i]=INF;
      cin>>t;
      for(i=0;i>p[i]>>w[i];
      for(i=0;i 
POJ 1384 
这个也是一个完全背包问题（主要是其他看到的不多），这个比较考验思路，因为是求装满情况下的最小值，所以只要在考虑选择第i件物品时要挑选最小的情况，改变一下条件即可。
 
#include
using namespace std;
 
#define inf 0x3f3f3f3f
 
int n,m;
int dp[1000000];
int w[510],v[510];
 
int main()
{
    int T;
   cin>>T;
    while(T--){
        memset(dp,inf,sizeof(dp));
        cin>>n>>m;
        m = m - n;
        cin>>n;
        dp[0] = 0;
        for(int i = 0;i < n; i++)
            cin>>v[i]>>w[i];
        for(int i = 0;i < n; i++){
            for(int j = w[i];j <= m; j++){
                dp[j] = min(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        if(dp[m] != inf)
            cout< 
小总结： 
这应该是本学期最后一篇博客了，对于本周的学习强度，确实是没有前几周强度高，不过考试周，也确实没办法。不过，对于dp的学习和背包的一些理解不能拉下，在考完试结束后，大概也会好好复习一下。对于本学期的学习还有一些话想说的，就放在最后的5000字里吧。