HDU 1059 Dividing（多重背包）

Dividing

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13321 Accepted Submission(s): 3739

Problem DescriptionInputOutputSample InputSample Outputimport java.io.*;import java.util.*;/* * * author : denghuilong * Date : 2013-8-30 **/public class Main {int n = 6;int dp[] = new int[2000000];int sum;public static void main(String[] args) {new Main().work();}void work() {Scanner sc = new Scanner(new BufferedInputStream(System.in));int Case = 1;while (sc.hasNext()) {Node node = new Node();Arrays.fill(dp, 0);sum = 0;for (int i = 1; i <= n; i++) {node.num[i] = sc.nextInt();//弹珠的数量node.val[i] = i;//弹珠的价值sum += (node.num[i] * node.val[i]);//总价值}if (sum == 0)break;if ((sum & 1) != 0) {//等价于 sum%2 是否等于0，如果不等于0，说明他们不可以平分System.out.println("Collection #" + Case++ + ":");System.out.println("Can't be divided.");System.out.println();} else {sum >>= 1;//右一位，表示除以2， 要求平分即：总价值/2；for (int i = 1; i <= n; i++) {multiplePack(node.val[i], node.val[i], node.num[i]);}System.out.println("Collection #" + Case++ + ":");if (dp[sum] != sum)System.out.println("Can't be divided.");elseSystem.out.println("Can be divided.");System.out.println();}}}//多重背包void multiplePack(int cost, int weight, int amount) {if (cost * amount >= sum) {// 如果大于一半，数量是无限的，按完全背包处理completePack(cost, weight);} else {//小于一半按01背包处理int k = 1;while (k < amount) {ZeroOnePack(k * cost, k * weight);amount -= k;k <<= 1;}ZeroOnePack(amount * cost, amount * weight);}}//01背包void ZeroOnePack(int cost, int weight) {for (int i = sum; i >= cost; i--) {dp[i] = Math.max(dp[i], dp[i - cost] + weight);}}// 完全背包void completePack(int cost, int weight) {for (int i = cost; i <= sum; i++) {dp[i] = Math.max(dp[i], dp[i - cost] + weight);}}class Node {int num[] = new int[n + 1];int val[] = new int[n + 1];}}