0 1背包、完全背包
0-1背包
0-1背包：有n个物品，第i个物品的体积为w[i],价值为v[i] 每个物品至多选一个，求体积和不超过capacity时的最大价值和
深度优先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private int[] v;
private int[] w;
public int zeroOnePacket(int[] v,int[] w,int capacity){
this.v = v;
this.w = w;
return dfs(v.length-1,capacity);
}
/**
*
* @param i 所有能选的物品的下标最大值，也是当前要选择拿或不拿的物品
* @param c 背包剩余c容量
* @return 在选到第i个物品，且背包使用容量不超过c时，最多能获得多少钱
*/
public int dfs(int i,int c){
if(i<0) return 0;//没东西可选
if(c<w[i]) return dfs(i-1,c);//剩余容量太小，选不了i
return Math.max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]);//在拿和不拿中选赚最多的
}
}
记忆化
无法提高dfs的时间复杂度，但是可以减少时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Arrays;
class Solution {
private int[] v;
private int[] w;
private int[][] cache;
public int zeroOnePacket(int[] v,int[] w,int capacity){
this.v = v;
this.w = w;
this.cache = new int[v.length][capacity];
for (int[] ints : cache) {
Arrays.fill(ints, -1);
}
return dfs(v.length-1,capacity);
}
/**
*
* @param i 所有能选的物品的下标最大值，也是当前要选择拿或不拿的物品
* @param c 背包剩余c容量
* @return 在选到第i个物品，且背包使用容量不超过c时，最多能获得多少钱
*/
public int dfs(int i,int c){
if(i<0) return 0;//没东西可选
if(cache[i][c]!=-1) return cache[i][c];//cache有所需要的数据
if(c<w[i]){
cache[i][c] =dfs(i-1,c);//剩余容量太小，选不了i
return cache[i][c];
}
cache[i][c] = Math.max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]);//在拿和不拿中选赚最多的
return cache[i][c];
}
}
动态规划
所有记忆化的dfs，都可以改写成dp，但是我懒得写了
//TODO
494. 目标和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
private int[] nums;
public int findTargetSumWays(int[] nums, int target) {
/*
p:正数和
s:所有数的和
n:负数和
p - n = s
p + n = t
2p = s+t
p = (s+t)/2
*/
this.nums = nums;
int sum = Arrays.stream(nums).sum();
if((sum+target)%2==1 || sum+target<0) return 0;
return dfs(nums.length-1,(sum+target)/2);
}
private int dfs(int i,int num){
if(i<0) return num==0?1:0;
if(num<nums[i]) return dfs(i-1,num);
return dfs(i-1,num) + dfs(i-1,num-nums[i]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int findTargetSumWays(int[] nums, int target) {
//p
//s-p
//p-(s-p)==t
//p == (s+t)/2
target += Arrays.stream(nums).sum();
if(target<0 || (target&1)==1) return 0;
target/=2;
int[][] dp = new int[nums.length+1][target+1];
dp[0][0] = 1;
for(int i=1;i<dp.length;i++){
//i是当前选的数字
int num = nums[i-1];
for(int j=0;j<dp[0].length;j++){
//j是当前的target
dp[i][j] = dp[i-1][j];//没选这个数字
if(num <= j){
dp[i][j] += dp[i-1][j-num];//选了这个数字
}
}
}
return dp[dp.length-1][dp[0].length-1];
}
}
完全背包
完全背包：有n种物品，第i种物品的体积为w[i]，价值为v[i] 每种物品无限次重复选，求体积和不超过capacity时的最大价值和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private int[] v;
private int[] w;
public int zeroOnePacket(int[] v,int[] w,int capacity){
this.v = v;
this.w = w;
return dfs(v.length-1,capacity);
}
/**
*
* @param i 所有能选的物品的下标最大值，也是当前要选择拿或不拿的物品
* @param c 背包剩余c容量
* @return 在选到第i个物品，且背包使用容量不超过c时，最多能获得多少钱
*/
public int dfs(int i,int c){
if(i<0) return 0;//没东西可选
if(c<w[i]) return dfs(i-1,c);//剩余容量太小，选不了i
return Math.max(dfs(i-1,c),dfs(i,c-w[i])+v[i]);//在拿和不拿中选赚最多的，在这里和0-1背包有唯一的区别
}
}
322.零钱兑换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
private int[] coins;
private int[][] cache;
public int coinChange(int[] coins, int amount) {
this.coins = coins;
int[][] cache = new int[coins.length+1][amount+1];
this.cache = cache;
for(int i =0;i<cache.length;i++){
Arrays.fill(cache[i],-1);
}
int res = dfs(coins.length-1,amount);
if(res>1e4) return -1;
return res;
}
private int dfs(int i,int amount){
if(i<0) return amount==0?0:Integer.MAX_VALUE/2;
if(cache[i][amount]!=-1) return cache[i][amount];
if(amount < coins[i]) {
cache[i][amount] = dfs(i - 1, amount);
return cache[i][amount];
}
cache[i][amount] = Math.min(dfs(i-1,amount),dfs(i,amount-coins[i])+1);
return cache[i][amount];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int coinChange(int[] coins, int amount) {
//this.coins = coins;
int[][] cache = new int[coins.length+1][amount+1];
// this.cache = cache;
// for(int i =0;i<cache.length;i++){
// Arrays.fill(cache[i],-1);
// }
// int res = dfs(coins.length-1,amount);
// if(res>1e4) return -1;
// return res;
Arrays.fill(cache[0], Integer.MAX_VALUE / 2);
cache[0][0] = 0;
for(int i=1;i<cache.length;i++){
int num = coins[i-1];
for(int c=0;c<cache[0].length;c++){
if(c<coins[i-1]){
cache[i][c] = cache[i-1][c];
}else{
cache[i][c] = Math.min(cache[i-1][c],cache[i][c-num]+1);
}
}
}
return cache[cache.length-1][cache[0].length-1]>1e4?-1:cache[cache.length-1][cache[0].length-1];
}
}
本文由作者按照 CC BY 4.0 进行授权