华为OJ之称砝码

1.题目描述

2.基本思路

这道题目需要使用动态规划来做，可以这么来想，要看能否称出某中质量X，在已知能称出质量Y，且如果存在某种重量a的砝码有k个，且X=Y+a*n(0<=n<=k)满足，那么则可以称出质量Y。这样我们就可以从最大质量（所有砝码之和）W开始，根据上述思路看W-1，W-2，……，1，0是否可以称出。

3.实现代码

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int kinds=sc.nextInt(); int[] weight=new int[kinds]; int[] amount=new int[kinds]; for(int i=0;i 0;j--){ for(int k=1;k<=amount[i];k++){ int index=j-weight[i]*k; if(index>=0&&record[index]==1){ record[j]=1; } } } } int count=0; for(int i=0;i 输入：2 1 2 2 1 输出：5