题解 | #01背包#

#define max(a, b) ((a) > (b) ? (a) : (b))
int knapsack(int V, int n, int** vw, int vwRowLen, int* vwColLen ) {
    int dp[V + 1], v, m;
    for (int i = 0; i <= V; i++){    //表示容量为dp[i]时可装下的物品重量
        dp[i] = 0;  //下标为0~V的元素初始为0
    }
    for (int i = 0; i < n; i++){  //对n个物品的体积和重量进行检查
        v = vw[i][0];   //为了清楚一点，记下当前物品的体积
        m = vw[i][1];   //记下当前物品的重量
        for (int j = V; j >= v; j--){   //当前最大可用容量比当前物品体积大时，判断是否装入
            dp[j] = max(dp[j - v] + m, dp[j]);  //装入该物品后的重量与不装的重量对比
        }
    }
    return dp[V];
}