ACM之近期学习总结

1. 背包问题

一.01 背包问题

题目：
有 N件物品和一个容量为 V的背包。第 i 件物品的重量是 c[i] ，价值是 w[i] 。求解将哪些物品装入背包可使价值总和最大

基本思路：
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态： 即 f[i][v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i][v],f[i-1][v-c[i]]+w[i]}

for(int i=0;i<n;i++)
{
    for(int j=W;j>=w[i];j--)
    {
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
    }
}

 初始化的细节问题
我们看到的求最优解的背包问题题目中， 事实上有两种不太相同的问法。 有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。
一种区别：这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法， 要求恰好装满背包，那么在初始化时除了 f[0] 为 0 其它f[1..V] 均设为 - ∞，这样就可以保证最终得到的 f[N] 是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V] 全部设0。                                                                

二. 完全背包问题

题目：
有 N种物品和一个容量为 V的背包，每种物品都有无限件可用。 第 i 种物品的费
用是 c[i] ，价值是 w[i] 。求解将哪些物品装入背包可使这些物品的费用总和不
超过背包容量，且价值总和最大。

 基本思路：
这个问题非常类似于 01 背包问题 ，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1件、取 2 件,, 等很多种。 

for(int i=0;i<n;i++)
{
    for(int j=w[i];j<=W;j++)
    {
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}

 三. 多重背包问题

题目：
有 N种物品和一个容量为 V的背包。第 i 种物品最多有 n[i] 件可用，每件费用是 c[i] ，价值是 w[i] 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

基本算法：
这题目和完全背包问题很类似。 基本的方程只需将完全背包问题的方程略微一改即可，因为对于第 i 种物品有 n[i]+1 种策略：取 0 件，取 1 件,, 取 n[i] 件。令 f[i][v] 表示前 i 种物品恰放入一个容量为 v 的背包的最大权值，  

for(int i=0;i<n;i++)
{
    int num=n[i];
    for(int k=0;k<=num[i];k++)
    {
        for(int j=W;j>=w[i];j--)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
}

多重背包例题：庆功会
Problem Description

为了庆贺班级在校运动会上取得全校第一名成绩,班主任决定开一场庆功会,为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品,可以补充他们的精力和体力。
 

Input
第1行两个数其中n代表希望购买的奖品的种数,m表示拨款金额。接下来n行,每行3个数, v,w,s分别表示第i种奖品的价格、价值(价格与价值是不同的概念)和能购买的最大数量(买0件到s件均可,其中v<=100,w<=1000,s<=10
 

Output
一个数,表示此次购买能获得的最大的价值(注意!不是价格)。
 

Sample Input

5 1000

80 20 4

40 50 9

30 50 7

40 30 6

20 60 1

  Smple Output

1040

代码：

#include<cstdio>
int v[10001], w[10001];
int f[6001];
int n,m,nl;
int max(int a,int b)
{
   return a>b?a:b
}
int main()
  scanf("%d%d",&n,&m);
  for(int i=1; i<=n; i++)
  {
    int x,y,s,t=1
    scanf("%d%d%d",&x,&y,&s);
    while(s>=t)
    {
      v[++n1]=x*t;//相当于n1++,v[n1]=x*t
      w[n1]=y*t;
      s-=t;
      t*=2;
    }
    v[++nl]=x*s;//把s以2的指数分堆：1,2,4...
  }
  for(int i=l;i<=nl;i++)
    for(intj=m;j>=v[i];j--)
    f[j]=max([f[j],f[j-v[i]]+w[i]);
  printf("%d\n",f[m]);
  getchar();//起暂停作用,便于观察输出结果
return 0;
}

四：混合三种背包问题

问题:
如果将01背包完全背包、多重背包混合起来。也就是说,有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限 (多重背包）

混合三种背包例题

Problem Description

一个旅行者有一个最多能装V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,....Wn,它们的价值分别为C1,C2…Cn。有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。求解将哪些
物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
Input
第1行:两个整数,M(背包容量,M<=200,N(物品数量,N<=30);
第2至N+1行:每行三个整数W,C,P,前两个整数分别表示每个物品的重量,价值,第个整数若为0,则说明此物品可以购买无数件;若为其他数字,则为此物品可购买的最多件数(Pi)
Output
仅一行,一个数,表示最大总价值。
Sample Input

10  3
2 1 0
3 3 1
4 5 4

Smple Output

11

 代码：

#include<cstdio>
using namespace std;
int m,n;
int w[31],c[31],p[31];
int f[201];
int max(int x,int y)
{
   if(x<y) return y;
   else returnx;
}
int main
{
   scanf("%d%d",&m,&n);
   for(int i=l;i<=n;i++)
     scanf(n%d%d%d",&w[i],&c[i],&p[i]);
   for(int i=l;i<=n;i++)
     if (p[i]==0)//完全背包
     {
        for(int j=w[i];j<=m;j++)
         f[j]=max(f[j],f[j-w[i]]+c[i]);
     }
   else
   {
       for(int j=1;j<=p[i];j++)//背包和多重背包
          for(int k=m;k>=w[i];k--)
             f[k]=max(f[k],f[k-w[i]]+c[i]);
   }
   printf("%d",f[m]);
   return 0;
}

五.二维费用的背包问题

题目:
二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a和b订。两种代价可付出的最大值(两种背包容量)分别为V和U。物品的价值为c[i]。

思路：

费用加了一维,只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。

状态转移方程就是f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+c[i]}。如前述方法,可以只使用二维的数组:当每件物品只可以取一次时变量v和u采用逆序的循环,当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。

物品总个数的限制
有时,“二维费用”的条件是以这样一种隐含的方式给出的:最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用,每个物品的件数费用均为1,可以付出的最大件数费用为M。换句话说,设发f[v][m]表示付出费用v,最多选m件时可得到的最大价值,则根据物品的类型(01、完全、多重)用不同的方法循环更新,最后在f[0..V][0..M]范围内寻找答案.另外，如果要求“恰取M件物品”，则在发f[0...V][M]范围内寻找答案。

二.区间dp

定义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

思路：

既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。

 for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }