【0,1背包问题】
容量限制，代码一：
/**
*
* @param value 物品价值
* @param volume 物品体积
* @param max 背包最大容量
* @return 背包所装物品的最大价值
*/
public int findMaxValue(int[]value,int[]volume,int max) {
int l=value.length;
int[][]dp=new int[l+1][max+1];
for(int i=1;i<=l;i++){
//枚举所有可能出现的背包已用容量
for(int j=0;j<=max;j++){
if(j-volume[i]>=0){
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-volume[j]]+value[i]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[l][max];
}
容量和重量限制 代码2：
/**
*
* @param value 物品价值
* @param volume 物品体积
* @param weight 物品体积
* @param max_v 背包最大容量
* @param max_w 背包最大重量
* @return 背包所装物品的最大价值
*/
public int findMaxValue(int[]value,int[]volume,int[]weight,int max_v,int max_w) {
int l=value.length;
int[][][]dp=new int[l+1][max_v+1][max_w+1];
for(int i=1;i<=l;i++){
//枚举所有可能出现的背包已用容量
for(int j=0;j<=max_v;j++){
for(int k=0;k<max_w;k++){
if(j-volume[i]>=0&&k-weight[i]>=0){
dp[i][j][k]=Math.max(dp[i-1][j][k],dp[i-1][j-volume[j]][k-weight[i]]+value[i]);
}else {
dp[i][j] = dp[i - 1][j];
}
}
}
}
return dp[l][max_v][max_w];
}
分割等和子集（分为2个子集）
0/1背包问题，仔细思考状态转移方程
// 01背包的板子题
class Solution {
// 1、确定边界
// 2、状态转移方程
public boolean canPartition(int[] nums) {
// 极限情况
if (nums.length==1){
return false;
}
int max_volume=0;
for(int num:nums){
max_volume+=num;
}
if(max_volume%2==1){
return false;
}
boolean[][]dp = new boolean[nums.length][max_volume/2+1];
// 边界情况
// Arrays.fill(dp,false);
for(int i=0;i<nums.length;i++){
dp[i][0]=true;
}
if(nums[0]<=max_volume/2){
dp[0][nums[0]]=true;
}else{
return false;
}
for(int i=1;i<nums.length;i++){
for(int j=1;j<=max_volume/2;j++){
if(j>=nums[i]){
// dp[i][j] = dp[i][j-nums[i]] | dp[i-1][j];
// 注意这个状态一定是从dp[i-1]
dp[i][j] = dp[i-1][j-nums[i]] | dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[nums.length-1][max_volume/2];
}
}
698. 划分为k个相等的子集
