蓝桥杯每日一题------背包问题（三）

前言

之前求的是在特点情况下选择一些物品让其价值最大，这里求的是方案数以及具体的方案。

背包问题求方案数

在这里插入图片描述
既然要求方案数，那么就需要一个新的数组来记录方案数。动态规划步骤如下，
定义dp数组
第一步：缩小规模。考虑n个物品，那我就先考虑1个物品，在考虑2个物品…，需要一个维度表示当前考虑的物品个数。
第二步：限制。所选物品个数不能超过物品容量，那么需要一个维度记录当前背包的容量。
第三步：写出dp数组。f[i][j]表示当前考虑了前i个物品，背包容量为j价值最大时的方案数。
第四步：推状态转移方程。f[i][j]应该从哪里转移过来呢，必然是从前i-1个物品转移，我要考虑两种情况，对于第i个物品，可以选择要它，也可以不要它。
（1）如果要第i个物品，f[i][j]=f[i-1][j-v[i]]。
（2）如果不要第i个物品，f[i][j]=f[i-1][j]。
（3）如果要和不要都可以获得最大价值，f[i][j]=f[i-1][j-v[i]]+f[i-1][j]。
那么在原先的dp数组进行转移的时候，我们要记录他到底是从哪个状态转移过来的，不能只单纯取一个最大值。代码如下。

int l = dp[j];int r = dp[j-v[i]] + w[i];dp[j] = Math.max(l, r);if(l > r) {f[j] = f[j];}else if (l < r) {f[j] = f[j-v[i]];}else{f[j] = f[j] + f[j-v[i]];}

同时要注意f数组的初始化，当考虑前0个物品时，方案是啥也不选，所以方案数是1，初始化代码如下，

for(int i = 0;i < k+1;i++){f[i] = 1;}

完整代码如下，

import java.util.Scanner;
public class Main {
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int k = scanner.nextInt();int v[] = new int[n+1];int w[] = new int[n+1];int dp[] = new int[k+1];int f[] = new int[k+1];for (int i = 1; i < n+1; i++) {v[i] = scanner.nextInt();w[i] = scanner.nextInt();}for(int i = 0;i < k+1;i++) f[i] = 1;int mod = 1000000007;for (int i = 1; i < n+1; i++) {for (int j = k; j >= v[i]; j--) {int l = dp[j];int r = dp[j-v[i]] + w[i];dp[j] = Math.max(l, r);if(l > r) {f[j] = f[j];}else if (l < r) {f[j] = f[j-v[i]];}else{f[j] = f[j] + f[j-v[i]];}f[j] %= mod;}}System.out.println(f[k]);
}
}

背包问题求具体方案

在这里插入图片描述
正常求dp数组，求完后逆序推回去就行，对于dp[n][m]，如果dp[n][m]=dp[n][m-v[i]]+w[i]，那么第i个物品被选择，然后再接着往后求dp[n][m-v[i]]。
那么如何保证字典序最小？回顾一下求dp数组的过程，我们是优先考虑的字典序小的物品，但是最后求的时候我们是倒序推导，这样反而字典序大的物品会优先被输出，所以更改一下字典序小的物品放在后面求。
全部代码如下，

import java.util.Scanner;
public class Main {
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int V = scanner.nextInt();int[] v = new int[n+1];int[] w = new int[n+1];for (int i = 1; i < w.length; i++) {v[i] = scanner.nextInt();w[i] = scanner.nextInt();}int[][] dp = new int[n+2][V+1];for (int i = n; i > 0; i--) {for (int j = 0; j < V+1; j++) {dp[i][j] = dp[i+1][j];if(v[i] <= j) {dp[i][j] = Math.max(dp[i][j], dp[i+1][j-v[i]] + w[i]);}}}int vv = V;for (int i = 1; i < n+1&&vv>0; i++) {if(vv >= v[i] && dp[i][vv] == dp[i+1][vv-v[i]] + w[i]) {System.out.print(i + " ");vv -= v[i];}}
}
}