動態規劃（1）

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

#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[cnt] = 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;
}

posted @ 2023-04-30 16:22 尊滴菜閱讀(23) 評論(0) 收藏舉報

刷新頁面返回頂部

閑時記錄

——歲月無從貸款

動態規劃（1）

公告