java怎么做网站后台/专业网站快速

题目链接：01背包
题目描述
已知一个背包最多能容纳物体的体积为V
现有n个物品第i个物品的体积为$v_i$ , 第i个物品的重量为$w_i$

​求当前背包最多能装多大重量的物品

样例：

输入：
10,2,[[1,3],[10,4]]
输出：
4

思路：裸的01背包，回顾一下。

import java.util.*;
public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* 计算01背包问题的结果* @param V int整型 背包的体积* @param n int整型 物品的个数* @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi* @return int整型*/public int knapsack (int V, int n, int[][] vw) {int m=vw[0].length;int dp[][]=new int[n+1][V+1];//前i件物品装入容量为V的背包中的最大重量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];//不装第i件物品else dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-vw[i-1][0]]+vw[i-1][1]);//装和不装第i件物品的最大值}}return dp[n][V];}
}

滚动数组优化，注意倒序枚举容量。

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* 计算01背包问题的结果* @param V int整型 背包的体积* @param n int整型 物品的个数* @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi* @return int整型*/public int knapsack (int V, int n, int[][] vw) {int m=vw[0].length;int dp[]=new int[V+1];//前i件物品装入容量为V的背包中的最大重量for(int i=1;i<=n;i++){for(int j=V;j>=vw[i-1][0];j--){dp[j]=Math.max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1]);}}return dp[V];}
}