动态规划实现最长递增子序列及0-1背包问题

好的，我可以为您介绍一下C++中动态规划实现最长递增子序列和0-1背包问题的方法。

首先，最长递增子序列问题是指在一个给定的序列中，找到一个子序列，使得这个子序列中的元素是递增的，并且这个子序列的长度最长。动态规划是解决这个问题的一种常用方法。

以下是C++中实现最长递增子序列的代码：

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

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    int res = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    return res;
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lengthOfLIS(nums) << endl; // 输出4
    return 0;
}

接下来，0-1背包问题是指在一个给定的背包容量下，选择一些物品放入背包中，使得这些物品的总价值最大，但是这些物品的总重量不能超过背包的容量。同样，动态规划也是解决这个问题的一种常用方法。

以下是C++中实现0-1背包问题的代码：

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

int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (wt[i - 1] <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt[i - 1]] + val[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][W];
}

int main() {
    vector<int> wt = {10, 20, 30};
    vector<int> val = {60, 100, 120};
    int W = 50;
    int n = wt.size();
    cout << knapsack(W, wt, val, n) << endl; // 输出220
    return 0;
}

希望这些代码可以帮助您理解动态规划实现最长递增子序列和0-1背包问题的方法。