阿阿阿顺Yaya

阿阿阿顺Yaya

关注
发信
关注(28)粉丝(399)

【C++刷题】优选算法——动态规划第六辑

  1. 【模板】01背包
状态表示:
	dp1[i][j]: 表示从前i个物品中挑选总体积不超过j的物品，在所有的选法中，能挑选出的最大价值
	dp2[i][j]: 表示从前i个物品中挑选总体积正好等于j的物品，在所有的选法中，能挑选出的最大价值
优化:
	利用滚动数组做空间上的优化

int main()
{
    int n, V; // n 物品个数 V 背包体积
    cin >> n >> V;
    int v, w; // v 物品体积 w物品价值
    vector<pair<int, int>> goods(1);
    while(cin >> v >> w) goods.push_back(make_pair(v, w));
    
    // 1.dp数组
    vector<vector<int>> dp1(n + 1, vector<int>(V + 1));
    vector<vector<int>> dp2(n + 1, vector<int>(V + 1));

    // 2.初始化

    for(int j = 1; j < dp2[0].size(); ++j) dp2[0][j] = -1;

    // 3.状态转移方程
    for(int i = 1; i < dp1.size(); ++i)
    {
        for(int j = 1; j < dp1[0].size(); ++j)
        {
            if(j - goods[i].first >= 0)
                dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-goods[i].first] + goods[i].second);
            else
                dp1[i][j] = dp1[i-1][j];
        }
    }

    for(int i = 1; i < dp2.size(); ++i)
    {
        for(int j = 1; j < dp2[0].size(); ++j)
        {
            if(j - goods[i].first >= 0 && dp2[i-1][j-goods[i].first] != -1)
                dp2[i][j] = max(dp2[i-1][j], goods[i].second + dp2[i-1][j-goods[i].first]);
            else
                dp2[i][j] = dp2[i-1][j];
        }
    }

    // 4.返回值
    cout << dp1.back().back() << endl;
    cout << (dp2.back().back() == -1 ? 0 : dp2.back().back()) << endl;
    return 0;
}

// 优化版
int main()
{
    int n, V; // n 物品个数 V 背包体积
    cin >> n >> V;
    int v, w; // v 物品体积 w物品价值
    vector<pair<int, int>> goods(1);
    while(cin >> v >> w) goods.push_back(make_pair(v, w));
    
    // 1.dp数组
    vector<int> dp1(V + 1);
    vector<int> dp2(V + 1);

    // 2.初始化

    for(int j = 1; j < dp2.size(); ++j) dp2[j] = -1;

    // 3.状态转移方程
    for(int i = 1; i <= n; ++i)
    {
        for(int j = dp1.size() - 1; j - goods[i].first >= 0; --j)
        {
            dp1[j] = max(dp1[j], dp1[j-goods[i].first] + goods[i].second);
        }
    }

    for(int i = 1; i <= n; ++i)
    {
        for(int j = dp2.size() - 1; j - goods[i].first >= 0; --j)
        {
            if(dp2[j-goods[i].first] != -1)
                dp2[j] = max(dp2[j], goods[i].second + dp2[j-goods[i].first]);
        }
    }

    // 4.返回值
    cout << dp1.back() << endl;
    cout << (dp2.back() == -1 ? 0 : dp2.back()) << endl;
    return 0;
}
  1. 分割等和子集
问题转化:
	是否能在在数组中选择一些和为num/2的数出来
状态表示:
	dp[i][j]: 表示从前i个数中能否选出一组数，使它的和为j

bool canPartition(vector<int>& nums)
{
    // 0.预处理
    int sum = 0;
    for(int e : nums) sum += e;
    if(sum % 2) return false;
    sum /= 2;

    // 1.dp数组
    vector<vector<bool>> dp(nums.size() + 1, vector<bool>(sum + 1));

    // 2.初始化
    for(int i = 0; i < dp.size(); ++i) dp[i][0] = true;

    // 3.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 0; j < dp[0].size(); ++j)
        {
            if(j - nums[i-1] >= 0)
                dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
            else
                dp[i][j] = dp[i-1][j];
        }
    }

    // 4.返回值
    return dp.back().back();
}

// 优化版
bool canPartition(vector<int>& nums)
{
    // 0.预处理
    int sum = 0;
    for(int e : nums) sum += e;
    if(sum % 2) return false;
    sum /= 2;

    // 1.dp数组
    vector<bool> dp(sum + 1);

    // 2.初始化
    dp[0] = true;

    // 3.状态转移方程
    for(int i = 1; i <= nums.size(); ++i)
    {
        for(int j = dp.size() - 1; j - nums[i-1] >= 0; --j)
        {
            dp[j] = dp[j] || dp[j-nums[i-1]];
        }
    }

    // 4.返回值
    return dp.back();
}
  1. 目标和
问题转化:
	假如 nums 中正数的和为 a，负数的和取绝对值为 b，则由 a-b=target; a+b=sum; 得到 a=(target+sum)/2
	所以问题可以转化为: 在 nums 数组中挑选一些数出来，使它的和等于 a，问一共有多少种挑选的方法
状态表示:
	dp[i][j]: 在 nums 数组的前 i 个数中一共有多少种挑选方式，使挑选出来的数的和等于 j

int findTargetSumWays(vector<int>& nums, int target)
{
    // 0.预处理
    int sum = 0;
    for(int e : nums) sum += e;
    int aim = (target + sum) / 2;
    if(aim < 0 || (target + sum) % 2) return 0;

    // 1.dp数组
    vector<vector<int>> dp(nums.size() + 1, vector<int>(aim + 1));

    // 2.初始化
    dp[0][0] = 1;

    // 3.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 0; j < dp[0].size(); ++j)
        {
            if(j - nums[i-1] >= 0)
            {
                dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]];
            }
            else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // 4.返回值
    return dp.back().back();
}

// 优化版
int findTargetSumWays(vector<int>& nums, int target)
{
    // 0.预处理
    int sum = 0;
    for(int e : nums) sum += e;
    int aim = (target + sum) / 2;
    if(aim < 0 || (target + sum) % 2) return 0;

    // 1.dp数组
    vector<int> dp(aim + 1);

    // 2.初始化
    dp[0] = 1;

    // 3.状态转移方程
    for(int i = 1; i <= nums.size(); ++i)
    {
        for(int j = dp.size() - 1; j - nums[i-1] >= 0; --j)
        {
            dp[j] += dp[j - nums[i-1]];
        }
    }

    // 4.返回值
    return dp.back();
}
  1. 最后一块石头的重量 II
问题转化:
	在数组中选一些数出来，使这些数的和尽可能地接近 sum/2
状态表示:
	dp[i][j]: 表示从数组的前 i 个元素中选一些数出来，其总和不大于 j 的最大和

int lastStoneWeightII(vector<int>& stones)
{
    // 0.预处理
    int sum = 0;
    for(int e : stones) sum += e;
    int aim = sum / 2;

    // 1.dp数组
    vector<vector<int>> dp(stones.size() + 1, vector<int>(aim + 1));

    // 2.初始化

    // 4.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 0; j < dp[0].size(); ++j)
        {
            if(j - stones[i-1] >= 0)
            {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - stones[i-1]] + stones[i-1]);
            }
            else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // 4.返回值
    return sum - 2*dp.back().back();
}

// 优化版
int lastStoneWeightII(vector<int>& stones)
{
    // 0.预处理
    int sum = 0;
    for(int e : stones) sum += e;
    int aim = sum / 2;

    // 1.dp数组
    vector<int> dp(aim + 1);

    // 2.初始化

    // 4.状态转移方程
    for(int i = 1; i <= stones.size(); ++i)
    {
        for(int j = dp.size() - 1; j - stones[i-1] >= 0; --j)
        {
            dp[j] = max(dp[j], dp[j - stones[i-1]] + stones[i-1]);
        }
    }

    // 4.返回值
    return sum - 2*dp.back();
}
  1. 【模板】完全背包
状态表示:
	dp1[i][j]: 表示从前 i 个物品中，所选出的物品，体积不大于 j 的最大价值
	dp2[i][j]: 表示从前 i 个物品中，所选出的物品，体积正好等于 j 的最大价值

int main()
{
    // 0.预处理
    int n, V; // n 物品个数 V 背包体积
    cin >> n >> V;
    vector<pair<int, int>> goods(1);
    int v, w; // v 物品的体积 w 物品的价值
    while(cin >> v >> w) goods.push_back(make_pair(v, w));

    // 1.dp数组
    vector<vector<int>> dp(n + 1, vector<int>(V + 1));
    vector<vector<int>> dp2(n + 1, vector<int>(V + 1, -1));

    // 2.初始化
    dp2[0][0] = 0;

    // 3.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 0; j < dp[0].size(); ++j)
        {
            dp[i][j] = dp[i-1][j];
            if(j - goods[i].first >= 0)
            {
                dp[i][j] = max(dp[i][j], dp[i][j - goods[i].first] + goods[i].second);
            }
            // int k = 1;
            // while(true)
            // {
            //     if(j - k * goods[i].first >= 0)
            //     {
            //         dp[i][j] = max(dp[i][j], dp[i-1][j - k * goods[i].first] + k * goods[i].second);
            //         ++k;
            //     }
            //     else
            //     {
            //         break;
            //     }
            // }
        }
    }

    for(int i = 1; i < dp2.size(); ++i)
    {
        for(int j = 0; j < dp2[0].size(); ++j)
        {
            dp2[i][j] = dp2[i-1][j];
            if(j - goods[i].first >= 0 && dp2[i][j - goods[i].first] != -1)
            {
                dp2[i][j] = max(dp2[i][j], dp2[i][j - goods[i].first] + goods[i].second);
            }
            // int k = 1;
            // while(true)
            // {
            //     if(j - k * goods[i].first >= 0)
            //     {
            //         if(dp2[i-1][j - k * goods[i].first] != -1)
            //         {
            //             dp2[i][j] = max(dp2[i][j], dp2[i-1][j - k * goods[i].first] + k * goods[i].second);
            //         }
            //         ++k;
            //     }
            //     else
            //     {
            //         break;
            //     }
            // }
        }
    }

    // 4.返回值
    cout << dp.back().back() << endl;
    cout << (dp2.back().back() == -1 ? 0 : dp2.back().back())  << endl;
    return 0;
}

// 优化版
int main()
{
    // 0.预处理
    int n, V; // n 物品个数 V 背包体积
    cin >> n >> V;
    vector<pair<int, int>> goods(1);
    int v, w; // v 物品的体积 w 物品的价值
    while(cin >> v >> w) goods.push_back(make_pair(v, w));

    // 1.dp数组
    vector<int> dp(V + 1);
    vector<int> dp2(V + 1, -1);

    // 2.初始化
    dp2[0] = 0;

    // 3.状态转移方程
    for(int i = 1; i < goods.size(); ++i)
    {
        for(int j = goods[i].first; j < dp.size(); ++j)
        {
            dp[j] = max(dp[j], dp[j - goods[i].first] + goods[i].second);
        }
        // for(int j = 0; j < dp.size(); ++j)
        // {
        //     if(j - goods[i].first >= 0)
        //     {
        //         dp[j] = max(dp[j], dp[j - goods[i].first] + goods[i].second);
        //     }
        // }
    }

    for(int i = 1; i < goods.size(); ++i)
    {
    	for(int j = goods[i].first; j < dp2.size(); ++j)
        {
            if(dp2[j - goods[i].first] != -1)
            {
                dp2[j] = max(dp2[j], dp2[j - goods[i].first] + goods[i].second);
            }
        }
        // for(int j = 0; j < dp2.size(); ++j)
        // {
        //     if(j - goods[i].first >= 0 && dp2[j - goods[i].first] != -1)
        //     {
        //         dp2[j] = max(dp2[j], dp2[j - goods[i].first] + goods[i].second);
        //     }
        // }
    }

    // 4.返回值
    cout << dp.back() << endl;
    cout << (dp2.back() == -1 ? 0 : dp2.back())  << endl;
    return 0;
}
  1. 零钱兑换
状态表示:
	dp[i][j]: 表示从前 i 种硬币中，在所有取出的硬币总额等于 j 的方式中，所取出的最少硬币数

int coinChange(vector<int>& coins, int amount)
{
    // 1.dp数组
    vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, -1));

    // 2.初始化
    dp[0][0] = 0;

    // 3.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 0; j < dp[0].size(); ++j)
        {                
            dp[i][j] = dp[i-1][j];
            if(j - coins[i-1] >= 0 && dp[i][j - coins[i-1]] != -1)
            {
                if(dp[i][j] != -1) dp[i][j] = min(dp[i][j], dp[i][j - coins[i-1]] + 1);
                else dp[i][j] = dp[i][j - coins[i-1]] + 1;
            }
        }
    }
    
    // 4.返回值
    return dp.back().back();
}

// 优化版
int coinChange(vector<int>& coins, int amount)
{
    // 1.dp数组
    vector<int> dp(amount + 1, -1);

    // 2.初始化
    dp[0] = 0;

    // 3.状态转移方程
    for(int i = 1; i <= coins.size(); ++i)
    {
        for(int j = 0; j < dp.size(); ++j)
        {                
            if(j - coins[i-1] >= 0 && dp[j - coins[i-1]] != -1)
            {
                if(dp[j] != -1) dp[j] = min(dp[j], dp[j - coins[i-1]] + 1);
                else dp[j] = dp[j - coins[i-1]] + 1;
            }
        }
    }
    
    // 4.返回值
    return dp.back();
}
  1. 零钱兑换 II
状态表示:
	dp[i][j]: 表示从 i 种硬币中，可以挑选出总额等于 j 的不同挑选方式

int change(int amount, vector<int>& coins)
{
    // 1.dp数组
    vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1));

    // 2.初始化
    dp[0][0] = 1;

    // 3.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 0; j < dp[0].size(); ++j)
        {
            dp[i][j] = dp[i-1][j];
            if(j - coins[i-1] >= 0)
            {
                dp[i][j] += dp[i][j-coins[i-1]];
            }
        }
    }

    // 4.返回值
    return dp.back().back();
}

// 优化版
int change(int amount, vector<int>& coins)
{
    // 1.dp数组
    vector<int> dp(amount + 1);

    // 2.初始化
    dp[0] = 1;

    // 3.状态转移方程
    for(int i = 1; i <= coins.size(); ++i)
    {
        for(int j = coins[i-1]; j < dp.size(); ++j)
        {
            dp[j] += dp[j-coins[i-1]];
        }
    }

    // 4.返回值
    return dp.back();
}
  1. 完全平方数
状态表示:
	dp[i][j]: 表示从前 i 种完全平方数中，能挑选出总和等于 j 的所有方式中，挑选的完全平方数最少的个数

int numSquares(int n)
{
    // 0.预处理
    int m = sqrt(n);

    // 1.dp数组
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));

    // 2.初始化
    dp[0][0] = 0;

    // 3.状态转移方程
    for(int i = 1; i < dp.size(); ++i)
    {
        for(int j = 0; j < dp[0].size(); ++j)
        {
            dp[i][j] = dp[i-1][j];
            if(j - pow(i, 2) >= 0 && dp[i][j - pow(i, 2)] != -1)
            {
                if(dp[i][j] != -1)
                {
                    dp[i][j] = min(dp[i][j], dp[i][j - pow(i, 2)] + 1);
                }
                else
                {
                    dp[i][j] = dp[i][j - pow(i, 2)] + 1;
                }
            }
        }
    }

    // 4.返回值
    return dp.back().back();
}

// 优化版
int numSquares(int n)
{
    // 0.预处理
    int m = sqrt(n);

    // 1.dp数组
    vector<int> dp(n + 1, -1);

    // 2.初始化
    dp[0] = 0;

    // 3.状态转移方程
    for(int i = 1; i <= m; ++i)
    {
        for(int j = pow(i, 2); j < dp.size(); ++j)
        {
            if(dp[j - pow(i, 2)] != -1)
            {
                if(dp[j] != -1) dp[j] = min(dp[j], dp[j - pow(i, 2)] + 1);
                else dp[j] = dp[j - pow(i, 2)] + 1;
            }
        }
    }

    // 4.返回值
    return dp.back();
}
  1. 一和零
状态表示:
	dp[i][j][k]: 表示从前i个二进制字符串中，能选出的字符'0'的个数不大于j，字符'1'的个数不大于k的所有方式中，二进制字符串最多的个数

int findMaxForm(vector<string>& strs, int m, int n)
{
    // 1.dp数组
    vector<vector<vector<int>>> dp(strs.size() + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));

    // 2.初始化

    // 3.状态转移方程
    for(int i = 1; i <= strs.size(); ++i)
    {
        int c0 = 0, c1 = 0;
        for(char c : strs[i-1])
        {
            if(c == '0') ++c0;
            else ++c1;
        }
        for(int j = 0; j <= m; ++j)
        {
            for(int k = 0; k <= n; ++k)
            {
                dp[i][j][k] = dp[i-1][j][k];
                if(j - c0 >= 0 && k - c1 >= 0)
                {
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-c0][k-c1] + 1);
                }
            }
        }
    }

    // 4.返回值
    return dp[strs.size()][m][n];
}

// 优化版
int findMaxForm(vector<string>& strs, int m, int n)
{
    // 1.dp数组
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    // 2.初始化

    // 3.状态转移方程
    for(int i = 1; i <= strs.size(); ++i)
    {
        int c0 = 0, c1 = 0;
        for(char c : strs[i-1])
        {
            if(c == '0') ++c0;
            else ++c1;
        }
        for(int j = m; j - c0 >= 0; --j)
        {
            for(int k = n; k - c1 >= 0; --k)
            {
                dp[j][k] = max(dp[j][k], dp[j-c0][k-c1] + 1);
            }
        }
    }

    // 4.返回值
    return dp[m][n];
}
  1. 盈利计划
状态表示:
	dp[i][j][k]: 表示从前 i 个工作中挑选，总人数小于等于 j，总利润大于等于 k 的所有选择方式

int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit)
{
    const int MOD = 1e9+7;
    // 1.dp数组
    vector<vector<vector<int>>> dp(group.size() + 1, vector<vector<int>>(n+1, vector<int>(minProfit+1)));

    // 2.初始化
    for(int j = 0; j <= n; ++j)
    {
        dp[0][j][0] = 1;
    }

    // 3.状态转移方程
    for(int i = 1; i <= group.size(); ++i)
    {
        for(int j = 0; j <= n; ++j)
        {
            for(int k = 0; k <= minProfit; ++k)
            {
                dp[i][j][k] = dp[i-1][j][k];
                if(j - group[i-1] >= 0)
                {
                    dp[i][j][k] += dp[i-1][j-group[i-1]][max(0, k-profit[i-1])];
                }
                dp[i][j][k] %= MOD;
            }
        }
    }

    // 4.返回值
    return dp.back().back().back();
}

// 优化版
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit)
{
    const int MOD = 1e9+7;
    // 1.dp数组
    vector<vector<int>> dp(n+1, vector<int>(minProfit+1));

    // 2.初始化
    for(int j = 0; j <= n; ++j)
    {
        dp[j][0] = 1;
    }

    // 3.状态转移方程
    for(int i = 1; i <= group.size(); ++i)
    {
        for(int j = n; j - group[i-1] >= 0; --j)
        {
            for(int k = 0; k <= minProfit; ++k)
            {
                dp[j][k] += dp[j-group[i-1]][max(0, k-profit[i-1])];
                dp[j][k] %= MOD;
            }
        }
    }

    // 4.返回值
    return dp.back().back();
}
  1. 组合总和 Ⅳ
背包问题：有限制条件下的“组合”问题

根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示
状态表示:
	dp[i]: 表示凑成总和 i，一共有多少种排列数

int combinationSum4(vector<int>& nums, int target)
{
    // 1.dp数组
    vector<double> dp(target + 1);

    // 2.初始化
    dp[0] = 1;

    // 3.状态转移方程
    for(int i = 1; i <= target; ++i)
    {
        for(int num : nums)
        {
            if(i - num >= 0) dp[i] += dp[i-num];
        }
    }

    // 4.返回值
    return dp.back();
}
  1. 不同的二叉搜索树
根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示
状态表示:
	dp[i]: 表示节点个数为 i 的时候，一共有多少种二叉搜索树

int numTrees(int n)
{
    // 1.dp数组
    vector<int> dp(n + 1);

    // 2.初始化
    dp[0] = 1;

    // 3.状态转移方程
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= i; ++j)
        {
            dp[i] += dp[j-1] * dp[i-j];
        }
    }

    // 4.返回值
    return dp.back();
}
04-30 08:28
Powered by LMLPHP ©2024 阿阿阿顺Yaya 0.003921