01背包问题：求可承受重量下装载的最大价值
给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
-
public int maxValue(int W,int N,int[] weight,int[] val){
-
int[][] dp=new int[N+1][W+1];
-
for(int i=1;i<=N;i++){
-
for(int w=1;w<=W;w++){
-
if(w<weight[i-1]){
-
//当背包容量装不下时，只能选择不装入背包
-
dp[i][w]=dp[i-1][w];
-
}else{
-
//根据价值选择是否装入背包
-
dp[i][w]=(dp[i-1][w-weight[i-1]]+val[i-1],dp[i-1][w]);
-
}
-
}
-
}
-
return dp[N][W];
-
}
子集背包问题：求能否使用给定的元素将背包装满
思路：求出数组的总和sum，令sum/2为背包的可承载重量，将元素装入该背包中，判断是否能恰好将背包装满。
-
class Solution {
-
public boolean canPartition(int[] nums) {
-
int sum=0;
-
for(int num:nums) sum+=num;
-
if(sum%2!=0) return false;
-
sum/=2;
-
int n=nums.length;
-
boolean[][] dp=new boolean[n+1][sum+1];
-
for(int i=0;i<=n;i++){
-
dp[i][0]=true;
-
}
-
for(int i=1;i<=n;i++){
-
for(int j=1;j<=sum;j++){
-
if(j<nums[i-1]){
-
dp[i][j]=dp[i-1][j];
-
}else{
-
dp[i][j]=dp[i-1][j]|dp[i-1][j-nums[i-1]];
-
}
-
}
-
}
-
return dp[n][sum];
-
}
-
}
完全背包问题：求当元素可重复使用时，装满背包的组合个数
思路： 物品的数量是无限的，完全背包问题。
-
class Solution {
-
public int change(int amount, int[] coins) {
-
int n=coins.length;
-
int[][] dp=new int[n+1][amount+1];
-
for(int i=0;i<=n;i++){
-
dp[i][0]=1;
-
}
-
for(int i=1;i<=n;i++){
-
for(int j=1;j<=amount;j++){
-
if(j<coins[i-1]){
-
dp[i][j]=dp[i-1][j];
-
}else{
-
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];
-
}
-
}
-
}
-
return dp[n][amount];
-
}
-
}
多重背包问题：当元素可重复使用时，求可承受重量下装载的最大价值
题目
有N种物品和一个容量为V的背包。第i种物品最多有p [ i ]件可用，每件费用是w [ i ]，价值是v [ i ] 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
解法一：自上而下填表法，超时
-
public static void main(String[] args) {
-
int[] P={8,2,1,7,1,18,4}; //价值
-
int[] V={3,4,3,9,4,5,4}; //重量
-
int[] M={1,1,1,1,1,1,1}; //数量
-
int T = 6;
-
-
int[][] dp = new int[P.length + 1][T + 1];
-
-
for (int i = 0; i < P.length; i++){
-
for (int j = 0; j <= T; j++){
-
for (int k = 0; k <= M[i] && k * V[i] <= j; k++){
-
dp[i+1][j] = (dp[i+1][j], dp[i][j-k * V[i]] + k * P[i]);
-
}
-
}
-
}
-
(dp[P.length][T]);
-
}
解法二：优化位01背包问题
-
for (int i = 1; i <= n; i++) {
-
int num = min(p[i], V / w[i]);
-
for (int k = 1; num > 0; k <<= 1) {
-
if (k > num) k = num;
-
num -= k;
-
for (int j = V; j >= w[i] * k; j--)
-
f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
-
}
-
}