动态规划解决背包问题

目录

动态规划步骤：

1.01背包问题

2.完全背包问题

动态规划步骤：

 step1.分析问题，定义dp数组（下标含义）

step2.初始化dp数组（边界）

step3.写dp状态转换方程（明确dp数组遍历顺序）

1.01背包问题

        即物品均只能取1次

46. 携带研究材料（第六期模拟笔试） (kamacoder.com)https://kamacoder.com/problempage.php?pid=1046

#include <iostream>
#include <vector>
using namespace std;

void debug_input(vector<int>& vec){
    for(auto it=vec.begin(); it!=vec.end(); it++){
        cout<<*it<<" ";
    }
    cout<<endl;
}

class solution
{
public:
    int max_value(vector<int>& space, vector<int>& value, int M, int N){
        // 定义dp[i][j]
        vector<vector<int>> dp(M+1, vector<int> (N+1, 0));
        //初始化
        for(int j=space[0]; j<=N; j++)
            dp[0][j] = value[0];
        //状态转换
        for(int i=1; i<M; i++){
            for(int j=1; j<=N; j++){
                if(j < space[i]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = max( dp[i-1][j], dp[i-1][j-space[i]] + value[i]); 
            }
        }
        return dp[M-1][N];
    }
};

int main(){
    // input
    int M,N,input;
    cin>>M>>N;
    vector<int> space(M,0);
    vector<int> value(M,0);
    for(int i=0; i<M; i++){
        cin>>input;
        space[i] = input;
    }
    for(int i=0; i<M; i++){
        cin>>input;
        value[i] = input;
    }
    // // debug input
    // debug_input(space);
    // debug_input(value);
    
    //solve
    solution mysolve;
    cout<<mysolve.max_value(space, value, M, N);
    
    return 0;
}

2.完全背包问题

        即满足条件下，每个物品可取无数次。 

52. 携带研究材料（第七期模拟笔试） (kamacoder.com)https://kamacoder.com/problempage.php?pid=1052 

#include <iostream>
#include <vector>
using namespace std;

void debug_input(vector<int>& vec){
    for(auto it=vec.begin(); it!=vec.end(); it++){
        cout<<*it<<" ";
    }
    cout<<endl;
}

class solution
{
public:
    int max_value(vector<int>& space, vector<int>& value, int total_num, int total_space){
        // 定义dp[i][j]
        vector<vector<int>> dp(total_num, vector<int> (total_space+1, 0));
        //初始化
        for(int j=space[0]; j<=total_space; j++){
            dp[0][j] = dp[0][j-space[0]] + value[0];
        }
        //状态转换
        for(int i=1; i<total_num; i++){
            for(int j=1; j<=total_space; j++){
                if(j < space[i]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = max( dp[i-1][j], dp[i][j-space[i]]+value[i]);
            }
        }
        return dp[total_num-1][total_space];
    }
};

int main(){
    //input
    int total_num, total_space;
    cin>>total_num>>total_space;
    vector<int> space(total_num,0);
    vector<int> value(total_num,0);
    int s, v;
    for(int i=0; i<total_num; i++){
        cin>>s>>v;
        space[i] = s;
        value[i] = v;
    }
    // debug_input(space);
    // debug_input(value);
    
    //solve
    solution mysolve;
    cout<<mysolve.max_value(space, value, total_num, total_space);
    return 0;
}