Acwing算法提高课——背包问题求具体方案

系列文章目录

---

---

前言

背包问题的求最大价值对应着最短路径
而求具体方案对应着最短路的路径

---

一、01背包问题求具体方案

统一策略 且有字典序要求

正常来讲背包问题是先考虑第n个物品选还是不选
但是题目要求的是字典序 所以考虑倒序存入输出
然而这个v[i]和w[i]要先存入 要不边存入边遍历的话 只是下标有变化 并没有倒序存入输出
因为有倒序输出的所以这个题 不能用一维数组进行优化

import java.util.*;
public class Main{
    static int N = 1010;
    static int[][] f = new int[N][N];
    static int[] v = new int[N];
    static int[] w = new int[N];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int V = scan.nextInt();
        for(int i = 1 ; i <= n ; i++){
             v[i] = scan.nextInt();
             w[i] = scan.nextInt();
        }
        for(int i = n ;  i >= 1 ;i-- ){
            for(int j = 0 ; j <= V ; j ++){
                f[i][j] = f[i+1][j];
                if(j >= v[i] ) f[i][j] = Math.max(f[i][j],f[i+1][j-v[i]]+w[i]);
            }
        }
        int j = V ;
        //f[1][V] 是最大值
        for(int i = 1 ; i <= n ; i++ ){
            if(j >= v[i] && f[i][j] == f[i+1][j-v[i]]+w[i] ){
                System.out.print(i + " ");
                j -= v[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
29
30

二、完全背包问题求具体方案

1449. 数位成本和为目标值的最大数字

原题链接
给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：

• 给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
• 总成本必须恰好等于 target 。
• 添加的数位中没有数字 0 。
  由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 “0” 。

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出：“7772”
解释：添加数位 ‘7’ 的成本为 2 ，添加数位 ‘2’ 的成本为 3 。所以 “7772” 的代价为 2* 3+ 3*1 = 9 。 “977” 也是满足要求的数字，但 “7772” 是较大的数字。
数字 成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5

要求：
cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

题解

关于背包问题的初始化总结 参考大佬的这篇

class Solution {
    public String largestNumber(int[] cost, int target) {
        int n = 9;
        int[][] f = new int[10][5010];
        int[] v = new int[10];
        Arrays.fill(f[0],-0x3f3f3f3f);
        for(int i = 1;i <= n;i ++) v[i] = cost[i - 1];

        for(int i = 1;i <= n ;i ++)
        {
            for(int j = 1;j <= target;j ++)
            {
                f[i][j] = f[i - 1][j];
                if(j >= v[i])
                    f[i][j] = Math.max(f[i][j], f[i][j - v[i]] + 1);  
            }
        }

        if(f[9][target] < 0) return "0";

        String ans = "";
        for(int i = 9,j = target;i >= 1;i --)
        {
            while(j >= v[i] && f[i][j] == f[i][j - v[i]] + 1)
            {
                ans += i;
                j -= v[i];
            }
        }
        return ans;
    }
}
 
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

分组背包问题求方案数

1013.机器分配

import java.util.*;
public class Main{
    static int N = 100;
    static int[][] f = new int[N][N];
    static int[][] w = new int[N][N];
    static int [] s = new int[N];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();//设备总数
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= m ; j ++){
                w[i][j] = scan.nextInt();
            }
        }
        for(int i = 1 ; i <= n ; i++ ){//枚举物品
            for(int j = 0 ; j <= m ; j++){//枚举体积
                    f[i][j] = f[i-1][j];
                for(int k = 0 ; k <= j ; k ++){//枚举选择
                    f[i][j] = Math.max(f[i][j],f[i-1][j-k]+w[i][k]);
                }
            }
        }
        System.out.println(f[n][m]);
        int j = m ; 
        for(int i = n ; i >= 1 ;i --){
            for(int k = 0 ; k <= j ; k++){
                if(f[i][j] == f[i-1][j-k]+w[i][k]){
                    s[i] = k ;
                    j -= k ;
                    break;
                }
            }
        }
        for(int i = 1 ; i <= n ; i++){
            System.out.println(i + " " + s[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
29
30
31
32
33
34
35
36
37
38
39
40