题解 | #01背包#
01背包
https://www.nowcoder.com/practice/2820ea076d144b30806e72de5e5d4bbf
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 计算01背包问题的结果 * @param V int整型 背包的体积 * @param n int整型 物品的个数 * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi * @param vwRowLen int vw数组行数 * @param vwColLen int* vw数组列数 * @return int整型 */ int knapsack(int V, int n, int** vw, int vwRowLen, int* vwColLen ) { // write code here //(*returnColumnSizes)[count]=3; int **dp=(int **)malloc((n+1)*sizeof(int*)); vwRowLen=n; (*vwColLen)=2; for(int i=0;i<=n;i++){ dp[i]=(int *)calloc(V+1,sizeof(int)); } for(int i=1;i<=n;i++){ for(int j=1;j<=V;j++){ if(j<vw[i-1][0]){ dp[i][j]=dp[i-1][j]; } else{ dp[i][j]=(dp[i-1][j-vw[i-1][0]]+vw[i-1][1])>dp[i-1][j]?(dp[i-1][j-vw[i-1][0]]+vw[i-1][1]):dp[i-1][j]; } } } return dp[n][V]; }