好幾天了，來個高手搬下我吧，算法問題~

Question

A1*X1+A2*X2+...+An*Xn=Q;其中A1...An，Q为已知且为正整数， 
求使得方程成立的整数解，且，X1...Xn只能为0或者1，想了很久不知道如果求解，虚心求教，谢了！ 
 
 

Answer 1

X1...Xn只能为0或者1，这个有什么规律没有啊？

Answer 2

算法?是不是考虑先把X1=0算算,再把X1=1算算;然后又是X2=0算算,X2=1算算依此推算!

Answer 3

你求的是什么，X1-XN，还是A1-AN？

Answer 4

貌似是运筹学里面的问题啊 。matlab中好像有这样的函数可以直接求解。

Answer 5

这题就相当于：
给定一个大数Q，给一堆数A1-AN，求出A1-AN中哪些数加起来正好等于Q

Answer 6

实例就是 生产中的包装问题：产品是由小盒子包成一小盒一小盒(BOX)的，再把这些小盒组成一个大的箱子CARTON，CARTON和BOX之间是有绑定关系的，即一个CARTON对应了确定的几个BOX。由于客户的实际需求，现需要将CARTON 里的产品的数量改成C，现在是如何挑选这里头的N个小盒（A1...AN）使得他们的数量总和刚好等于客户的需求量C
不知道还有什么需补充的没，各位大侠继续，帮帮小弟吧

Answer 7

穷举法:(直接伪代码了,木时间敲代码调试)
xn因为只可以取0或1所以可以看做一个int(一般来说一个int 32个位够你用的了)
这里设为X,设an依次存储在数组A中.然后从1开始X自增,对于每次循环的X:
int q=0
for i = 0 to n-1
 b = X & (1<<i);
 if (b!=0){
   q += A[i];
 }
end for
if (q == Q)
{
  X的各个位即为对应xn的解.
}

Answer 8

ChrisAK：b = X & (1 < <i);这段什么意思，新手还请见谅啊！

Answer 9

matlab 奶奶的，大學上課就沒有聽懂過這個玩意~

Answer 10

1<<i
即1左移i个位
i=0的时候=1
i=2的时候=2
其实说白了就是在求2的i次方.
对于一个二进制整数(32位太长了这里用4位):
1<<0 = 0001
1<<1 = 0010
1<<2 = 0100
1<<3 = 1000
只于那个&是位的与运算运算规则很简单.
二进制位对齐后如果都为1则该位为1否则为0.
所以b = X & (1 <<i);就是在求X的第i位是否为1
如果b不等于0则说明X的第i位为1.

Answer 11

private void button1_Click(object sender, EventArgs e)
        {
            int[] m = new int[] { 1, 2, 3 };
            int q = 6;
            List<int[]> result = fangfa(m, q);
        }
        private List<int[]> fangfa(int[] shuzu, int q)
        {
            List<int[]> l = new List<int[]>();
            int leng=shuzu.Length;            
            int[] result = new int[leng];            
            char[] linshi;
            int q1 = 0;
            for (int i = 0; i < jisuanmi(2, leng); i++)
            {
                linshi = Convert.ToString(i, 2).ToCharArray();
                for (int j = 0; j < linshi.Length; j++)
                {
                    result[j] = int.Parse(linshi[j].ToString());
                }
                for (int k = 0; k < leng; k++)
                {
                    q1 = q1 + result[k] * shuzu[k];
                }
                if (q1 == q)
                {
                    l.Add(result);
                }
                q1 = 0;
            }            return l;        }
        private Int64 jisuanmi(int di,int mi)
        {
            int result=1;
            for (int i = 0; i < mi; i++)
            {
                result = result * di;
            }
            return result;
        }
特殊情况没考虑

Answer 12

int s=null;
for(int i=0;i<=n;i++)
{
  if(Xi==1)
    {
      s += Ai;
     }
}
return s;

Answer 13

liherun：
謝謝你的代碼，只是不好意思啊，大學计算机基礎學的太烂了,C#也是最近才学的，怎么获得LIST里面的值？
为什么我MESSAGEBOX.SHOW(RESULT[0].TOSTRING()) 显示的是SYSTEM32.INT32啊，抱歉，抱歉

Answer 14

大侠，好人做到底吧，能不能给段代码，我觉得ChrisAK的思路挺不错的，没想到过这点，用C#帮我写段代码，谢了~一会结贴啊，谢谢大家了

Answer 15

private void button1_Click(object sender, EventArgs e)
        {
            decimal d1 = 12345.123m;
            MessageBox.Show(d1.ToString());
            int[] m = new int[] { 1, 2, 3 };
            int q = 6;
            List<int[]> result = fangfa(m, q);
            for (int i = 0; i < result.Count; i++)
            {
                for (int j = 0; j < result[i].Length; j++)
                {
                    MessageBox.Show(result[i][j].ToString());
                }
            }
        }
        private List<int[]> fangfa(int[] shuzu, int q)
        {
            List<int[]> l = new List<int[]>();
            int leng=shuzu.Length;            
            int[] result = new int[leng];            
            char[] linshi;
            int q1 = 0;
            for (int i = 0; i < jisuanmi(2, leng); i++)
            {
                linshi = Convert.ToString(i, 2).ToCharArray();
                for (int j = 0; j < linshi.Length; j++)
                {
                    result[j] = int.Parse(linshi[j].ToString());
                }
                for (int k = 0; k < leng; k++)
                {
                    q1 = q1 + result[k] * shuzu[k];
                }
                if (q1 == q)
                {
                    l.Add(result);
                }
                q1 = 0;
            }            return l;        }
        private Int64 jisuanmi(int di,int mi)
        {
            int result=1;
            for (int i = 0; i < mi; i++)
            {
                result = result * di;
            }
            return result;
        }

Answer 16

liherun：测试不成功啊 全是1，当Q是5时没输出结果。。

Answer 17

 
ChrisAK：还在没在，能不能给段C#的代码，劳驾，劳驾

Answer 18

A1*X1+A2*X2+...+An*Xn=Q   X1...Xn只能为0或者1 ，那么这个问题就能看成A1.....An的那些数累加等于Q的问题举个例子：
1 2 3 4 5  Q=10 ;
那么只要求出这5个数字其中那几个数字加起来刚好等于10，其余的全部为0即可。如果还对数字有其他要求，看看动态规划。算法中可以先对数字进行排序，剔除掉大于Q的数字，如果有等于的更加好。
然后递归吧。

Answer 19

using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication52
{
    class Program
    {
        static int M = 5;
        static List<int> OrgA = new List<int>(new int[] { 1, 2, 3, 4 });
        static List<String> Result = new List<String>();        static void Main(string[] args)
        {            GetIt(OrgA, 0, String.Empty);            for (int i = 0; i < Result.Count; i++)
            {
                List<String> R = new List<String>(Result[i].Split(new Char[] { ' ' }));                for (int j = 0; j < OrgA.Count; j++)
                    Console.Write(OrgA[j].ToString() + "*" + (R.Contains(OrgA[j].ToString()) ? "1" : "0") + " ");                Console.WriteLine();
            }            Console.Read();
        }        static void GetIt(List<int> A, int V, String R)
        {
            if (V == M)
            {
                String[] S = R.Split(new Char[] { ' ' });
                Array.Sort(S);
                R = String.Join(" ", S);
                if (!Result.Contains(R))
                    Result.Add(R);
                return;
            }
            else if (V > M)
                return;            List<int> T = new List<int>(A);            foreach (int I in A)
            {
                T.Remove(I);
                GetIt(T, V + I, R + " " + I.ToString());
                T.Add(I);
            }
        }
    }
}

Answer 20

wartim：非常感谢，能不能为这个方法GetIt(OrgA, 0, String.Empty);
添加段注释呢。当数组里面有相同数的时候 测试不成功，他会将所有相同的全部列出，我实际中只需求1个就可以~谢谢了
 

Answer 21

抱歉，说错了，比如当 static int M = 80;
        static List<int> OrgA = new List<int>(new int[] { 20, 20, 30, 14,16,15 });
时，30+14+16+20就对了，至于是哪个20随便，可是你的结果会输出2个20，30+14+16+20+20，还是恳请你注释下你的代码，菜鸟在这谢了~

Answer 22

wartim：非常感谢，已经看明白了，也达到我实际中的需求了，各位大侠，由衷感谢，想不到会得到这么多人的帮助。发现自己还是很菜，基本的递归也不会，献丑了。
ChrisAK：希望有时间你能给个实现代码，我蛮想看下你的方法的，似乎比较简单。谢了~

Answer 23

private void button1_Click(object sender, EventArgs e)
        {            
            int[] m = new int[] { 1, 2, 3 };
            int q = 1;
           int[] result = fangfa(m, q);
            
                for (int j = 0; j < result.Length; j++)
                {
                    if (result[j]%2==1)
                        MessageBox.Show(m[j].ToString());
                }
            }        
        private int[] fangfa(int[] shuzu, int q)
        {           
            int leng=shuzu.Length;            
            int[] result = new int[leng];            
            char[] linshi;
            int q1 = 0;
            for (int i = 0; i < jisuanmi(2, leng); i++)
            {
                linshi = Convert.ToString(i, 2).ToCharArray();
                for (int j = 0; j <linshi.Length; j++)
                {
                    result[leng - j - 1] = int.Parse(linshi[linshi.Length-j-1].ToString());
                }
                for (int k = 0; k < leng; k++)
                {
                    q1 = q1 + result[k] * shuzu[k];
                }
                if (q1 == q)
                {                    
                    return result;
                }
                q1 = 0;
            }            return result;        }
        private Int64 jisuanmi(int di,int mi)
        {
            int result=1;
            for (int i = 0; i < mi; i++)
            {
                result = result * di;
            }
            return result;
        }
        public void mm()
        {
            Form5 f5 = new Form5();
            f5.ShowDialog();
        }
        private void button2_Click(object sender, EventArgs e)
        {            
            Thread t = new Thread(new ThreadStart(mm));
            t.Start();
            int result=0;
            for (int i = 0; i < 1000000; i++)
            {
                result += i;
            }
            t.Abort();
        }

Answer 24

哦，那是显示的问题
 Console.Write(OrgA[j].ToString() + "*" + (R.Contains(OrgA[j].ToString()) ? "1" : "0") + " ");
会把相同的20输出2次，因为只按数字判断，结果里还是只有一个20的最好结果最后再Trim一下，不然结果会有一个空字符串
   R = String.Join(" ", S).Trim();
/// <summary>
        /// 递归求合计值
        /// </summary>
        /// <param name="A">当前取值集合</param>
        /// <param name="V">当前合计值</param>
        /// <param name="R">解答字符串</param>
        static void GetIt(List<int> A, int V, String R)
        {
            if (V == M) // 如果合计已经等于要求的值
            {
                String[] S = R.Split(new Char[] { ' ' }); // 按空格拆分结果组成数组
                Array.Sort(S); // 数组从小到大排序
                R = String.Join(" ", S).Trim(); // 把排序后数组重新组装成字符串
                if (!Result.Contains(R)) // 解答集合里是否包含了这个解答
                    Result.Add(R); // 如果是新的解答，就加入解答集合
                // 只所以这么处理，是由于比如"1 2"和"2 1"这两个答案是一样的， 只取一个
                // 组装成字符串是由于方便用Contains判断
                return;
            }
            else if (V > M) // 如果合计值已经大于要求的值，就放弃往下继续累加求解答
                return;            List<int> T = new List<int>(A); // 定义和当前取值集合元素一样的集合克隆版本
                                            // 作为新的取值集合            foreach (int I in A) // 当前取值集合每个数都尝试一遍
            {
                T.Remove(I); // 从取值集合里去掉这个数，等于求子集
                GetIt(T, V + I, R + " " + I.ToString()); // 递归调用，把该数字累加进合计值，
                                                         // 传入子集
                T.Add(I); // 恢复取值集合，说明这个数字这次已经尝试过，可供之后的递归继续尝试
            }
        }