01背包的变形 题目描述：
一个天平，有n个钩子分布在天平的量端[钩子距离天平中间距离不等]，g个砝码[重量不同]
要求你把砝码全部放到钩子上，使天平平衡。求方案数
import java.util.Scanner; import java.util.concurrent.locks.Condition; import java.util.concurrent.locks.ReentrantLock; /** * Created by hms on 2017/3/28. */ public class Main { public static void main(String[] args) { int C, G; int c[] = new int[20 + 5]; //存储钩子的位置 int g[] = new int[20 + 5]; //存储砝码的重量 Scanner scanner = new Scanner(System.in); C = scanner.nextInt(); //输入钩子的个数 G = scanner.nextInt(); //输入砝码的个数 //输入钩子的位置 for(int i = 1;i <= C; ++i) c[i] = scanner.nextInt(); //输入砝码的重量 for(int i = 1; i <= G; ++i) g[i] = scanner.nextInt(); int dp[][] = new int[25][20000]; // dp[i][j]： 使用前i个砝码，在j处达到平衡的方案数 dp[0][7500] = 1; for(int i = 1; i <= G; ++i) { for(int j = 15000; j >= 0; --j) { for(int k = 1; k <= C; ++k) { if(j - c[k] * g[i] >= 0){ dp[i][j] += dp[i-1][j-c[k]*g[i]]; // dp[i][j] = dp[i][j] + dp[i-1][j-c[k]*g[i]]; } } } } System.out.println(dp[G][7500]); } }