动态规划（1）

背包问题

（1）0 1 背包  —— 每件物品最多使用一次

有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3+10 ; 
int n,m ; 
int v[N], w[N] ; // 体积 价值 
int f[N][N] ;  // 前 i 个物品的体积不超过 j 的情况下的价值 

int main(){
    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 = 0;  j<=m ; j++ )
        {
            f[i][j] = f[i-1][j] ; // 坐标这种情况一定存在
            if( j >= v[i] ) // 体积小于j
                f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]) ; 
        } 
　　 cout<<f[n][m] ; 
    return 0;
} 

优化成一维的

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+10 ; 
int n,m ; 
int v[N], w[N] ; // 体积 价值 
int f[N] ;  // 前 i 个物品的体积不超过 j 的情况下的价值 
int main(){
    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<<f[m]<<endl ; 
    return 0;
} 

（2）完全背包 —— 每件物品有无限个

和0 1背包的代码的区别只在第二个for循环的判断顺序

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3+10 ; 

int n,m ; 
int v[N], w[N] ; // 体积 价值 
int f[N][N] ;  //  


int main(){
     
    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=0; j<=m ; j++ )
            for( int k = 0 ; k*v[i] <= j ; k++ )
                f[i][j] = max(f[i][j], f[i-1][j-v[i]*k] + w[i]*k );
    
    cout<<f[n][m]<<endl ;     
    return 0;
}     

优化为二维

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3+10 ; 
int n,m ; 
int v[N], w[N] ; // 体积 价值 
int f[N][N] ;  //  
int main(){
    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=0; j<=m ; j++ )
        {
            f[i][j] = f[i-1][j] ; 
            if( j>=v[i] ) 
                f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i] ) ; 
        }

    cout<<f[n][m]<<endl ;     
    return 0;
}     

优化为一维

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

（3）多重背包 —— 每个物品有 S[ i ] 个

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3+10 ; 
int n,m ; 
int v[N], w[N],s[N] ; // 体积 价值 数量 
int f[N][N] ;  //  
int main(){
     
    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] + k*w[i] ) ; 
                        
    cout<<f[n][m]<<endl ;
    return 0;
}     

优化，采用二进制方法，先转为二进制存储，再采用01背包方法解

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3e4+10, M = 3000 ; 
int n,m ; 
int v[N], w[N] ; // 体积 价值 数量 
int f[N] ;  
int main(){
     
    cin>> n>> m ; 
    int cnt = 0 ;
    for(int i= 1; i<= n; i++ ){
        int a,b,s ; 
        cin>>a>>b>>s ;     // 设 s = 50 
        int k = 1; 
        while(k<s)    //二进制 1 + 2 + 4 + 8 + ... < s 
        {
            cnt++ ; 
            v[cnt] = a*k ;
            w[vnt] = b*k ;
            s -= k ;
            k *= 2 ;
        }
        if(s>0) // 31 + 19 = 50 
        {
            cnt++ ;
            v[cnt] = a*s ; 
            w[cnt] = b*s ;
        }    
    } 
    
    n = cnt++ ; 
    
    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<<f[m]<<endl ;     
    return 0;
}     

（4）分组背包 —— 每一组里面有若干个，组里面只能选一个

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3e3+10, M = 3000 ; 
int n,m ; 
int v[N][N], w[N][N], s[N]; // 体积 价值 数量 
int f[N] ; 
 
int main(){
     
    cin>> n>> m ; 
    
    for(int i= 1; i<= n; i++ )
    {
        cin>>s[i] ; 
        for(int j=0; j<s[i] ; j++) 
        {
            cin>>v[i][j]>>w[i][j];
        }
    } 
    
    for(int i=1 ; i<=n ; i++ )
        for(int j=m; j>=0 ; j-- )    // 转 0 1背包 
            for(int k=0; k<s[i]; k++)    // 寻找每个组 
                if(v[i][k] <= j)    // 第i组的第k件物品 
                    f[j] = max(f[j], f[j-v[i][k]] + w[i][k] ) ; 
                        
    cout<<f[m]<<endl ;     
    return 0;
}