动态规划：背包问题

背包问题属于组合优化范畴中的一种NP完全问题。在该问题中，存在N个物品以及容量为W的背包，每个物品均具有特定的体积w与价值v，目标是选择适当的物品组合，使得装入背包的物品总价值达到最大值。当规定每种物品仅能选取0个或1个时，此类问题被定义为0-1背包问题；而若不设限物品选取数量，则该问题被称为“无界背包”或“完全背包”问题。

一、0-1背包问题

针对背包问题，动态规划是一种有效的解决方法。以0-1背包为例，可以构建一个二维数组dp用于记录最大价值，其中dp[i][j]表示在前i个物品中，当背包容量不超过j时所能获得的最大价值。若将第i件物品放入背包，设其体积为w，价值为v，则此时dp[i][j]可由dp[i - 1][j - w] + v得出。在计算过程中，只需比较两种情况下的结果并取较大值即可。该方法的时间和空间复杂度均为O(NW)。

 int knapsack(vector<int> weights, vector<int> values, int N, int W) {

    
     vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    
     for (int i = 1; i <= N; i++) {
    
     int w = weights[i - 1], v =