1.求背包问题的方案数
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示 方案数 模 109+7 的结果。
数据范围
0<N,V≤1000
0<vi,wi≤1000
来源acwing
在01背包的基础上新增加一个数组plan用来存储体积为j时候，能有几种装物品的方法，这个plan必须要根据价值是不是最大来判断是否更新。具体解释在代码里面。
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| import java.util.*;
public class Main {
public static final int mod = 1000000007;
public static int solve (int[] v,int[] w,int N,int V){
int[] dp = new int[V + 1];
int[] plan = new int[V + 1];
plan[0] = 1;
Arrays.fill(dp,1,dp.length,-100000);
for (int i = 0; i < N; i++) {
for (int j = V; j >= v[i]; j--) {
int t = Math.max(dp[j], dp[j - v[i]] + w[i]);
int s = 0;
if (t == dp[j]) s += (plan[j] % mod);
if (t == (dp[j - v[i]] + w[i])) s += (plan[j - v[i]] % mod);
s %= mod;
dp[j] = t;
plan[j] = s;
}
}
int maxw = 0;
for (int i = 0; i < dp.length; i ++) {
maxw = Math.max(dp[i],maxw);
}
int ans = 0;
for (int i = 0; i < dp.length; i ++) {
if (dp[i] == maxw) {
ans += (plan[i] % mod);
}
}
return ans;
}
public static void show(int[] arr) {
for (int j = 0; j <arr.length; j++) {
System.out.print(arr[j]+" ");
}
System.out.println();
System.out.println("*");
}
public static void main (String[] args) {
Scanner sc=new Scanner (System.in);
int N,V;
N = sc.nextInt();
V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(solve(v,w,N,V));
}
}
|
2.求背包的具体方案
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
物品编号范围是 1…N。
数据范围
0<N,V≤1000
0<vi,wi≤1000
来源acwing
这次要选字典序小的，同时价值也得大。对于原来的方案，从最后一行遍历输出的话肯定是序号最大的，所以需要在一开始就要改变方法。采用贪心的策略，能选小的必须选小的。
转自dd大牛背包九讲：
一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略。首先，子问题的定义要略改一些。我们注意到，如果存在一个选了物品1的最优方案，那么答案一定包含物品1，原问题转化为一个背包容量为v-c[1]，物品为2..N的子问题。反之，如果答案不包含物品1，则转化成背包容量仍为V，物品为2..N的子问题。不管答案怎样，子问题的物品都是以i..N而非前所述的1..i的形式来定义的，所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下，以下按物品已被逆序排列来叙述。
在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从N到1输入时，如果f[i][v]==f[i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同时成立，应该按照后者（即选择了物品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
| public static void solve (int[] v,int[] w,int N,int V){
int[][] dp = new int[N + 2][V + 1];
for (int i = N; i >= 1; i--) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i + 1][j];
if (j >= v[i])
dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j - v[i]] + w[i]);
}
}
int volume = V;
for (int i = 1; i <= N; i ++) {
if (volume >= v[i]) {
if (dp[i][volume] == dp[i + 1][volume - v[i]] + w[i]) {
if (i != N) {
System.out.print(i + " ");
} else {
System.out.print(i);
}
volume -= v[i];
}
}
}
}
|
背包问题完