背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题

问题一

问题描述
假设有N个物品，其中第i个物品的重量为W_i。 现在需要将这些物品分成两堆，使得在“第一堆物品的总重量与第二堆物品的总重量之差尽可能小”的前提下，第一堆物品的数量与第二堆物品的数量之差尽可能大。那么，两堆物品总重量之差最小是多少？在总重量之差最小的前提下，两堆物品的数量之差最大是多少？

输入
第一行包含一个整数N，2$\leq$N$\leq$100。
第二行包含N个空格隔开的整数W₁到W_N，1$\leq$W_i$\leq$100。

输出
输出两个空格隔开的整数，第一个整数表示两堆物品的总重量之差的最小值，第二个整数表示在总重量之差最小的提前下，两堆物品的数量之差的最大值。

样例输入

6

1 2 3 4 5 6

样例输出

1 2

解析
思路：
重量之差最小：可以理解为可以放N个物品重量一半的背包问题，在背包中放入的物体总量最大。
数量之差最大：若总重量为偶数，两个背包一样大。若总总量为奇数，一个背包比另外一个背包大1。在总重量小（或相等）的一个背包中放入数量尽可能少的物品，在另一个背包中放入数据尽可能多的物品。
以样例为例，背包重量空间为10，如果当前背包的重量小于放入前一个物品的（当前背包重量-当前物品重量）所对应的重量+当前物品重量则放入，表格中写入放入后背包的重量。（第一行表示背包重量剩余空间，表格中表示当前背包的重量和放入的数量）。记录放入背包的物品数，如果放入则+1。如果放入与不放重量一样，则判断放入数量+1与不放数量更小的表示新的记录。
按行更新，使不同背包空间放入尽可能重量多数量少的物品

物品\背包空间	10	9	8	7	6	5	4	3	2	1	0
1	1 1	1 1	1 1	1 1	1 1	1 1	1 1	1 1	1 1	1 1	0 0
2	3 2	3 2	3 2	3 2	3 2	3 2	3 2	3 2	2 1	1 1	0 0
3	6 3	6 3	6 3	6 3	6 3	5 2	4 2	3 1	2 1	1 1	0 0
4	10 4	9 3	8 3	7 2	6 2	5 2	4 1	3 1	2 1	1 1	0 0
5	10 3	9 2	8 2	7 2	6 2	5 1	4 1	3 1	2 1	1 1	0 0
6	10 2	9 2	8 2	7 2	6 1	5 1	4 1	3 1	2 1	1 1	0 0

源码

import java.util.Scanner;
public class bag2 {
	//动态规划 背包问题
		public static void main(String[] args)
	    {
	        Scanner sc = new Scanner(System.in);
	        int num=sc.nextInt();
	        int weight[] = new int[num];
	        int sum=0,m=0;
	        for(int i=0;i<num;i++)
	        {
	        	weight[i]=sc.nextInt();
	        	sum+=weight[i];
	        }
	        m=sum;
	        sum/=2;
	        int dp[]=new int[sum+1];
	        int count[]=new int[sum+1];
	        for(int i=0;i<num;i++)
	        {
	        	for(int j=sum;j>=weight[i];j--)
	        	{
	        		if(dp[j]<(dp[j-weight[i]]+weight[i]))
	        		{
	        			dp[j]=dp[j-weight[i]]+weight[i];
	        			count[j]=count[j-weight[i]]+1;
	        		}
	        		else if(dp[j]==(dp[j-weight[i]]+weight[i]))
	        		{
	        			if(count[j]>count[j-weight[i]]+1)
	        			{
	        				count[j]=count[j-weight[i]]+1;
	        			}
	        		}
	        		 System.out.println(dp[j]+" "+count[j]+"   ");
	        	}
	        }
	        System.out.print((m-2*dp[sum])+" ");//输出重量最小差

	        System.out.print(num-2*count[sum]);//输出数量最大差
	    }
}

另一种思路
先考虑重量最小，然后可以得知，两个背包分别放入总量。可以转化为N个整数，选出M个整数的和为固定值，找出所有可能的组合。（速度太慢了，不能通过测试）

import java.util.Scanner;
public class bag1 {
	//动态规划 背包问题
	public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int num=sc.nextInt();
        int weight[] = new int[num];
        int sum=0,m=0;
        int dp[]=new int[10000];
        for(int i=0;i<num;i++)
        {
        	weight[i]=sc.nextInt();
        	sum+=weight[i];
        }
        m=sum;
        sum/=2;
        for(int i=0;i<num;i++)
        {
        	for(int j=sum;j>=weight[i];j--)
        	{
        		dp[j]=(dp[j]>(dp[j-weight[i]]+weight[i]))?dp[j]:(dp[j-weight[i]]+weight[i]);
        	}
        }
        System.out.print((m-2*dp[sum])+" ");//输出重量最小差
        int A=m-2*dp[sum];
        int B=m;
        int C=(A+B)/2; //重量更多的物体的和
        int large=binaryCal(weight,C);
        System.out.print(large-(num-large));//输出数量最大差
        
    }
    
	public static int binaryCal(int[] a,int m) {
		int n = a.length;
        //最大的数为2的n次方
		int max = 1 << n;
		int result=0;
		for(int i = 1;i < max;i++) {
            //转成二进制数
			String binaryNum = Integer.toBinaryString(i);
			//转成相同的位数，不足n位的在前补0
            binaryNum = toSameLen(binaryNum,n);
			char[] bitNum = binaryNum.toCharArray();
			int sum = 0;
			for(int j = 0;j < bitNum.length;j++) {
                //二进制数当前位置为1，则加起来
				if (bitNum[j] == '1') {
					sum += a[j];
				}
			}
            //和为m了，输出
			if (sum == m) {
				int tmp=output(bitNum,a);
				if(result<tmp)
					result=tmp;
			}
		}
		return result;
	}
	
	private static String toSameLen(String binaryNum, int len) {
		//数的长度
        int numLen = binaryNum.length();
		if (numLen == len) {
			return binaryNum;
		}
		StringBuilder sb = new StringBuilder();
        //差几位补几个0
		for(int i = 0;i < len - numLen;i++) {
			sb.append(0);
		}
		return sb.append(binaryNum).toString();
	}
 
	private static int output(char[] bitNum, int[] a) {
		int sum=0;
		for(int i = 0;i < bitNum.length;i++) {
			if (bitNum[i] == '1') {
				sum++;
			}
		}
		return sum;
	}
}