动态规划是算法中一门很重要的思想，其通过对每一步的假设规划，不停的寻找最优最有利的解决方案，然后一步一步求解出来。

而01背包是其中最基本的一种dp思想，其题目一般为给定一个容量为V的背包，然后有n件物品，其价值为value[i]，每件物品只能最多选择一次或者不选择，问如何才能得到的物品价值最大。

一般dp问题的核心就是一个 状态转移方程 。状态转移方程一出来题目基本上就木得问题了。

通常来说，状态转移方程的代码思想一般如下

for(int i=0; i
     
      =v[i])            dp[i+1][j] = max(dp[i][j], dp[i][j-v[i]]+val[i]);        else            dp[i+1][j] = dp[i][j];    }} 来看看这段代码，将第i件物品放在容量为j的背包中，使得dp[i][j]最大，对于第i件物品来说，有两种选择： 第一，不放这件物品。如果不放这件物品，则dp[i+1][j]=dp[i][j]。 第二，放这件物品。那么首先考虑是否放的下，就是剩下的空间j是否比这件物品的体积v[i]大。 如果大，则在j中腾出v[i]的空间给第i个物品，然后加上其价值与dp[i][j]比较一下就好了，取其中的最大值。 如果j小于v[i]，那么这个物品就不要考虑了，直接丢掉就行了。
     

 

先看看基础的题目。

 

1.

这道题目就是一道裸的不能再裸的01背包，给定的容量V，n件物品，每件价值给定，然后只能选一次。

首先学习到了有两种方法解决这道题，第一种是用二维数组，将每次的中间过程都存储下来，状态转移方程又有两种写法。

1 dp[i+1][j]=max(dp[i][j],dp[i][j-v[i]]+val[i]);2 3 注意这个是数组从0开始进行for循环4 5 dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+val[i]);6 7 这个是数组从1开始进行for循环8 9 其中v代表体积，val代表价值

以下是二维数组ac代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define ll long long int #define inf 1000000007using namespace std;int main(){    int t;    int val[1010],v[1010];    int dp[1010][1010];    cin>>t;    while(t--)    {        int n,V;        cin>>n>>V;        for(int i=0;i
         
          >val[i];        for(int i=0;i
          
           >v[i]; for(int i=0;i
           
            =v[i]) dp[i+1][j]=max(dp[i][j],dp[i][j-v[i]]+val[i]); else dp[i+1][j]=dp[i][j]; } } cout<
            
             <
            
           
          
         
        
       
      
     

 还有另一种的一维数组的代码，一维数组其实就是对上面二维数组的空间优化，具体好像是对空间的一种优化，对于二维数组来说，中间的每一次循环还记录着，而这些数据都是冗余的，可以不用，所以可以用一维数组进行dp。

状态转移方程如下：

for(int i=0; i
     
      =v[i]; j--)    {        dp[j] = max(dp[j], dp[j-v[i]]+val[i]);    }}
     

为什么要从V开始递减遍历？我举个例子，假设一个物品GG价值1000，体积为2，那么假设我们按【0…..v】这个顺序遍历，那么在j=2时，dp[2] = max(dp[2], dp[0]+1000)，那么dp[2] = 1000，当j=4时，dp[4]=max(dp[4], dp[2]+1000)， dp[4] = 2000，这时我们再思考一下，GG将被放进背包两次了！如果我们逆序遍历，就可以避免这种结果。

以下是一维数组ac代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int main(){    int value[1010],dp[1010],v[1010];    int t;    cin>>t;    while(t--)    {        memset(dp,0,sizeof(dp));        memset(value,0,sizeof(value));        memset(v,0,sizeof(v));        int n,V;        cin>>n>>V;        for(int i=0;i
         
          >value[i];        for(int i=0;i
          
           >v[i]; for(int i=0;i
           
            =v[i];j--) //j代表背包剩余的体积 { dp[j]=max(dp[j],dp[j-v[i]]+value[i]); } } cout<
            
             <
            
           
          
         
        
       
      
     

 

2.

 

Problem Description

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。

某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

 

Input

多组数据。对于每组数据：

第一行为正整数n，表示菜的数量。n<=1000。

第二行包括n个正整数，表示每种菜的价格。价格不超过50。

第三行包括一个正整数m，表示卡上的余额。m<=1000。

n=0表示数据结束。

 

 

Output

对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

 

 

Sample Input

1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0

 

Sample Output

-45 32

 题意大概就是饭卡的钱如果大于5，就能用，小于5就不能刷了，然后可以透支，如果大于5则可以减去一个数得到负值，问如何买使得剩下的钱最少。

题目思路一般就是先用sort把物品价值排个序，然后把最大的记录下来，然后用dp来使得剩余的钱尽可能的少并且大于5元。

ac代码如下：

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int main(){    int val[1010],dp[1010];    int n,m;    while(cin>>n&&n)    {        memset(dp,0,sizeof(dp));        memset(val,0,sizeof(val));        for(int i=0;i
          
           >val[i];        sort(val,val+n);        int maxn=val[n-1];        cin>>m;        if(m<5) cout<
           
            <
            
             =val[i];j--) { dp[j]=max(dp[j],dp[j-val[i]]+val[i]); } cout<
             
              <