动态规划 - 背包问题

背包问题
《背包九讲》:
1.0-1背包问题
2.完全背包问题
3.多重背包问题
4.混合三种背包问题
5.二维费用的背包问题
6.分组的背包问题
7.有依赖的背包问题
8.泛化物品
9.背包问题问法的变化

输出方案
方案总数
最优方案总数

https://www.acwing.com/problem/

0-1背包问题

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
i的理解：前 i 件物品可选择
v的理解1：总空间大小[可能没装满]
ans=f[n][v]

int[] v = new int[N+1];
int[] w = new int[N+1];
       
//第0行 为初始值
//第0列 为初值列
int[][] f = new int[N+1][V+1];
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= V; j++) {
        if (v[i] > j) f[i][j] = f[i-1][j];
        else {
            f[i][j] = Math.max(f[i-1][j], f[i-1][j-v[i]]+w[i]);
        }
    }
 }
System.out.println(f[N][V]);

优化空间复杂度[一维数组，为了不破坏上层数据，每层逆序循环]

int[] f = new int[V+1];
for (int i = 1; i <= N; i++) {
    for (int j = V; j >=1; j--) {
        if (v[i] <= j) {
            f[j] = Math.max(f[j], f[j-v[i]]+w[i]);
        }
    }
}
System.out.println(f[V]);

v的理解2：所占用的空间/恰好装满
ans=max{f[n][i], i =0,1,2,...,v}
-∞+w[i] = -∞、Integer.minValue

int[] dp = new int[V+1];
    for (int i = 1; i <= V; i++) dp[i] = Integer.MIN_VALUE;
    for (int i =1; i <= N; i++) {
        for (int j = V; j >= 1; j--) {
            if (v[i] <= j) dp[j] = Math.max(dp[j], dp[j-v[i]]+w[i]);
        }
    }

int ans = 0;
for (int i = 1; i <= V; i++) {
    if(dp[i] > ans) ans = dp[i];
}
System.out.println(ans);

2. 完全背包问题

int[][] f = new int[N+1][V+1];
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= V; j++) {
        f[i][j] = f[i-1][j];
        for(int k = 1; k*v[i] <= j; k++) {
            int temp = f[i-1][j-k*v[i]]+k*w[i];
            if (temp > f[i][j]) f[i][j] = temp;
        }
     }
}
System.out.println(f[N][V]);

3. 应用

1所用硬币数最少
找零

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int num = 1024 - N;
int[] dp = new int[num+1];
// 初始化dp数组，因为要找最小值，这里给每个位置赋最大值，
/*
for (int i = 1; i < dp.length; i++) {
     dp[i] = Integer.MAX_VALUE-num;
}
*/
// 由1元组成时所用硬币数
for (int i = 1; i < dp.length; i++) {
        dp[i] = i;
}
int[] money = {1, 4, 16, 64};
//int i = 0;
for (int i = 0; i < money.length; i++) {
    //逆序
    for (int j = num; j >= 1; j--) {
        for (int k = 0; k*money[i] <= j; k++) {
            int temp = dp[j-k*money[i]]+k;
            if (temp < dp[j]) dp[j] = temp;
        }
    }
}
System.out.println(dp[num]);

2几种表示法-无序
硬币

int[] dp = new int[n+1];
int[] coins = {1, 5, 10, 25};
for (int i = 1; i < dp.length; i++) {
    dp[i] = 1;
}
//int j = 1;
for (int j = 1; j < coins.length; j++) {
    //正序
    for (int k = 1; k <= n; k++) {
        if (k >= coins[j]) {
            dp[k] = dp[k] + dp[k-coins[j]];
        }
    }
}
System.out.println(dp[n]);

3几种表示法-有序

最后编辑于：2020.12.01 09:49:24