题解 | #称砝码#动态规划
称砝码
http://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c
称砝码（好题）
动态规划
# 输入
3
10 20 15
2 2 3
# 输出
20
使用动态规划求解。结合上面测试用例，对求解步骤进行说明
- 将所有砝码插入到一个数组
list中，如[10,10,20,20,15,15,15] - 记砝码总重量为
weightSum - 创建二维数组
dp[list.size()+1][weightSum+1]，其中dp[i][j]表示使用前i个砝码，是否可以称出重量j - 边界条件
dp[i][0] = true;，表示对所有的砝码都不适用，肯定是能称出重量 0dp[0][j] = true; (j != 0)，表示若不使用砝码，肯定不能称出大于 0 的重量
- 动态转移方程为
dp[i][j] = dp[i][j] || dp[i-1][j-weight] || dp[i-1][j]，推导过程如下
a. 记第 i 个砝码的重量为 weight = list.get(i)
b. 若 dp[i-1][j-weight] 为 true，则可通过使用第 i 个砝码，使 dp[i][j] 为 true
c. 若 dp[i-1][j] 为 true，则不使用第 i 个砝码，也可以使 dp[i][j] 为 true
- 在动态规划过程中，使用一个 Set 结构记录称出的重量，即若
dp[i][j] == true，将重量j放入到 Set 中 - 最后，计算出 set 中元素的个数，就是称出的重量的种类
代码实现如下。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int[] weightArr = new int[n];
int[] countArr = new int[n];
for(int i=0;i<n;i++){
weightArr[i] = in.nextInt();
}
for(int i=0;i<n;i++){
countArr[i] = in.nextInt();
}
//总总量
int weightSum = 0;
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<n;i++){
int weight = weightArr[i];
int count = countArr[i];
while(count > 0){
list.add(weight);
weightSum += weight;
count--;
}
}
//dp[i][j] 表示用list中前i个砝码，是否可以称出重量j
boolean[][] dp = new boolean[list.size() + 1][weightSum+1];
//边界条件 1
for(int i=0;i<=list.size();i++){
dp[i][0] = true;
}
//边界条件 2 dp[0][j] = false; dp[0][0] = true
//set 去重记录重量
Set<Integer> set = new HashSet<>();
set.add(0);
for(int i=1;i<=list.size();i++){
int weight = list.get(i-1);
for(int j=0;j<=weightSum;j++){
if(j - weight >=0){
// dp[i][j] = dp[i][j] || dp[i-1][j-weight] || dp[i-1][j];
dp[i][j] = dp[i][j] || dp[i-1][j-weight];
}
dp[i][j] = dp[i][j] || dp[i-1][j];
if(dp[i][j]){
set.add(j);
}
}
}
System.out.println(set.size());
}
}
}
此处有一个容易出错的点，因为动态转移方程为 dp[i][j] = dp[i][j] || dp[i-1][j-weight] || dp[i-1][j]，所以直接采用如下代码实现。
if(j - weight >=0){
dp[i][j] = dp[i][j] || dp[i-1][j-weight] || dp[i-1][j];
}
这种代码实现时错误的，因为 j - weight >=0 条件只针对 dp[i-1][j-weight]，对 dp[i-1][j] 并无此条件限制。正确的代码实现如下。
if(j - weight >=0){
dp[i][j] = dp[i][j] || dp[i-1][j-weight];
}
dp[i][j] = dp[i][j] || dp[i-1][j];
Set去重
- 首先根据输入顺序，将砝码用数字序列表示，例如 2个 1g 和 1个 2g，就用
1 1 2的序列表示 - 使用 Set 表示加入当前砝码之前能产生的重量种类
- set 初始化为
{0}； - 当第一个 1g 砝码放入时，则 set 中需要插入原先 set 中的所有元素 +1g后的结果，即
{0, 0+1} - 当第二个 1g 加入时，则 set 会插入
{0+1, 1+1}，所以 set 最终变为{0, 1, 2} - 重复上述步骤加入所有砝码
- 最后 set 的大小即为能产生的重量种类
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int[] weightArr = new int[n];
int[] countArr = new int[n];
for(int i=0;i<n;i++){
weightArr[i] = in.nextInt();
}
for(int i=0;i<n;i++){
countArr[i] = in.nextInt();
}
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<n;i++){
int weight = weightArr[i];
int count = countArr[i];
while(count > 0){
list.add(weight);
count--;
}
}
Set<Integer> set = new HashSet<>();
set.add(0);
for(int i=0;i<list.size();i++){
// for(Integer val:set){
// int newVal = val + list.get(i);
// set.add(newVal);
// }
//注意
//这里不要在遍历过程中向set插入异常
//否则会有 ConcurrentModificationException 异常
List<Integer> tempList = new ArrayList<Integer>();
for(Integer val:set){
tempList.add(val + list.get(i));
}
for(Integer weight: tempList){
set.add(weight);
}
tempList.clear();
}
System.out.println(set.size());
}
}
}
