题解 | #称砝码#动态规划

称砝码（好题）

• HJ41 称砝码 | 牛客网

动态规划

# 输入
3
10 20 15
2 2 3

# 输出
20

使用动态规划求解。结合上面测试用例，对求解步骤进行说明

1. 将所有砝码插入到一个数组 list 中，如 [10,10,20,20,15,15,15]
2. 记砝码总重量为 weightSum
3. 创建二维数组 dp[list.size()+1][weightSum+1]，其中 dp[i][j] 表示使用前 i 个砝码，是否可以称出重量 j
4. 边界条件
   • dp[i][0] = true;，表示对所有的砝码都不适用，肯定是能称出重量 0
   • dp[0][j] = true; (j != 0)，表示若不使用砝码，肯定不能称出大于 0 的重量
5. 动态转移方程为 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

6. 在动态规划过程中，使用一个 Set 结构记录称出的重量，即若 dp[i][j] == true，将重量 j 放入到 Set 中
7. 最后，计算出 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去重

1. 首先根据输入顺序，将砝码用数字序列表示，例如 2个 1g 和 1个 2g，就用 1 1 2 的序列表示
2. 使用 Set 表示加入当前砝码之前能产生的重量种类
3. set 初始化为 {0}；
4. 当第一个 1g 砝码放入时，则 set 中需要插入原先 set 中的所有元素 +1g后的结果，即 {0, 0+1}
5. 当第二个 1g 加入时，则 set 会插入 {0+1, 1+1}，所以 set 最终变为{0, 1, 2}
6. 重复上述步骤加入所有砝码
7. 最后 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());
        }
        
    }
}