AcWing 1047. 糖果(Java)
原题链接
简单
作者:
Limited
,
2021-02-12 21:27:29
,
所有人可见
,
阅读 411
思路
显然01背包,背包容量为$K$(如果用糖果总数,数据范围会很大,最多$100$件产品,每件最多$10^6$个糖果,总数最大值为$10^8$),产品个数为$N$,每个产品的价值为对应的糖果数量
- $f(i,j)$:只考虑前$i$件产品且糖果总数对$K$取模恰好为$j$的选法集合
属性:$Max$
- 状态计算:选和不选
- 不选第$i$件物品,状态从上层转移,即$f(i,j) = f(i-1,j)$
- 选择第$i$件物品,记$a_x$为第$x$件产品的糖果数
- 当前状态应为“考虑前$i-1$件产品且总数对$K$取模为j的情况”+“当前产品糖果数量”,后者已知,问题在于怎么获得前者状态的糖果数
- 则根据定义有$j = (a_1+a_2+\cdots+a_{i-1}+a_i)\ mod\ K = ((a_1+a_2+\cdots+a_{i-1})\ mod\ K\ + a_i)\ mod\ K$(其中前i个商品不是一定有的),那么上一个状态应为$j^\*=(a_1+a_2+\cdots+a_{i-1})\ mod\ K$,显然$j = (j^\*+a_i)\ mod\ K \Rightarrow j + K * t_1 = j^\* + a_i + K * t_2,(t \in Z) \Rightarrow j^\* = j - a_i + K * (t_1-t_2)$,因为$0 \leq j,j^\* < K$而$(j-a_i)$可能小于0,所以等号两边对$K$取模有$j^\*\ mod\ K = (j - a_i + K * (t_1-t_2))\ mod\ K \Longrightarrow j^\* = ((j - a_i)\ mod\ K + K)\ mod\ K \Longrightarrow j^\*=((j-a_i\ mod\ K) + K)\ mod\ K$
- 所以选择第$i$件物品的状态应为$f(i,j) = f(i-1, ((j-a_i\ mod\ K) + K)\ mod\ K) + a_i$
- 即$f(i,j) = max(f(i-1,j), f(i-1, ((j-a_i\ mod\ K) + K)\ mod\ K) + a_i)$
- 因为选和不选的状态都与上一层有关,且选择某物品时$j$与$j^\*$的关系不确定,优化到一维不论使用逆序还是正序都可能覆盖到上一层待使用的状态,不能进行等价改写,但可以考虑用一个
[2][k]
的数组进行回滚
代码 [n][k]
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int n, k;
static long[][] f = new long[110][110];
public static void main(String[] args) {
n = scanner.nextInt();
k = scanner.nextInt();
for (int i = 0; i <= n; i++) {
Arrays.fill(f[i], Integer.MIN_VALUE);
}
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
int w = scanner.nextInt();
for (int j = 0; j < k; j++) {
f[i][j] = Math.max(f[i - 1][j], f[i - 1][(j - w % k + k) % k] + w);
}
}
System.out.println(f[n][0]);
}
}
代码 [2][k]
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int n, k;
static long[][] f = new long[2][110];
public static void main(String[] args) {
n = scanner.nextInt();
k = scanner.nextInt();
Arrays.fill(f[0], Integer.MIN_VALUE);
Arrays.fill(f[1], Integer.MIN_VALUE);
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
int w = scanner.nextInt();
int idx = i % 2, idxPre = 1 - idx;
for (int j = 0; j < k; j++) {
f[idx][j] = Math.max(f[idxPre][j], f[idxPre][(j - w % k + k) % k] + w);
}
}
System.out.println(f[n % 2][0]);
}
}