考考大家一道某著名IT的面试题

jimmyixy

变相背包问题嘛

jerrymy

{:2_174:}头大。

zidaneback

动态规划？

jeasun

回复 36# ssa852741
把字母全换成小写，应该能看懂了

ssa852741

回复  ssa852741
把字母全换成小写，应该能看懂了
jeasun 发表于 2010-08-19 10:55

还是看不明白，能举个实例么....

ljt2k

要考虑算法的通用性，如果不是12、7、5，怎么办？

shymn

看了这么多,jeasun写的与我所想的一样,不过后面的不一样

假设x,y,z,5x+7y+12z=w;

那么
1) x,y异号,z=0                        5x+7y=w                        {5, -7}, {-5, 7}
2) x>0, y=0(或x=0, y>0), z>0        5x+12z=w 或 7y+12z=w        {5, 12}, {7, 12}
3) x>0, y=0(或x=0, y>0), z=0        5x=w 或 7y=w                {5}, {7}
4) x=0, y=0, z>0                   12z=w                        {12}

改一下好看些, 下面的x,y,z>0, 对于给定的w只会有下列几种:
第一组：5x+12z=w,        7y+12z=w
第二组：5x=w,        7y=w,        12z=w
第三组：5x-7y=w,        -5x+7y=w

程序可以这样想：
迭代地减去12,直到w<0且能够被5或7整除（至于为什么减去12,很多人应该已经猜到了,上面三组式子都（显示或隐式）有12出现,5-12能被7整除,7-12能被5整除,还有一点,-12不可能出现）

我证明了：
逐次减去12会有: 第一组 --> 第二组 [--> 第三组 --> -5a=w 或 -7b=w]

5x+12z=w --> 5x=w'(w'=w-12z) --> 5(x-x')-7x'=w''(w''=w'-12x') --> 最后一定是-7x=w'''<0
..................... 若w'==0--> 12z=w

举个例子,就设w=1
w-12 = -11                k = 1
-11-12 = -23                k = 2
-23-12 = -35                k = 3
-35小于0能被7整除得-5(也能被5整除但是从大到小)
；
q = |-5| = 5
因为是被7整除且q > k, 所以一定是第三组中的5x-7y=w(这是证明后的结论)
马上可以知道x = k = 3, y = q-k = 2

结果是-7*2+5*3,总共5个
如果之前拿5去除,结果就是-5*4+7*3,总共7个

另外若w=40，并不是8个5，而是4个7和1个12

代码如下，没写注释:

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main(int argc, char **argv)
   
5. {
   
6.         int        w, q, i, k;
   
7. 
   
8.         if (argc < 2) {
   
9.                 fprintf(stderr, "Usage: %s w ...", argv[0]);
   
10.                 exit(0);
    
11.         }
    
12. 
    
13.         for (i = 1; i < argc; i++) {
    
14.                 printf("%s: ", argv[i]);
    
15.                 w = atoi(argv[i]);
    
16. 
    
17.                 for (k = 0; w > 0 || (w%7 && w%5); k++)
    
18.                         w -= 12;
    
19. 
    
20.                 if (w == 0)
    
21.                         printf("(12)*%d\n", k);
    
22.                 else if (w%7 == 0) {
    
23.                         q = w/7 >= 0 ? w/7 : -w/7;
    
24.                         if (q > k)
    
25.                                 printf("(-7)*%d + (5)*%d\n", q-k, k);
    
26.                         else if (q == k)
    
27.                                 printf("(5)*%d\n", q);
    
28.                         else
    
29.                                 printf("(5)*%d + (12)*%d\n", q, k-q);
    
30.                 }
    
31.                 else if (w%5 == 0) {
    
32.                         q = w/5 >= 0 ? w/5 : -w/5;
    
33.                         if (q > k)
    
34.                                 printf("(-5)*%d + (7)*%d\n", q-k, k);
    
35.                         else if (q == k)
    
36.                                 printf("(7)*%d\n", q);
    
37.                         else
    
38.                                 printf("(7)*%d + (12)*%d\n", q, k-q);
    
39.                 }
    
40.         }
    
41. }

复制代码

shymn

其中的证明过程如下，不知道有没有讲清楚

设k为减去12的次数
对于第一组,
5x+12z=w
7y+12z=w        需要y+z块
要把w减成非正数,中途肯定得变成第二组中的一个,当w减到0时,就表示他是12的倍数,此时k就是所要的结果;
否则此时的w肯定是大于0的,也就是说变成下面两个之一:
5x=w
7y=w

5x=w最终一定会变成-7x=w-12x,也就是一定要减去x个12才能满足要求,7y=w会变成-5y=w-12y
证明如下(证7y=w, 另一个是一样的证法):
首先对这个w最优解为7y=w,用反证法得出他不是最优解
假设w还没有减到x个12就满足了要求(w<0且w%5==0或w%7==0)

7y=w ==> 7a-5b=w-12b<0,其中a+b=y若能被5整除,则a=5n,式子转化为
7*5n-5b=w-12b<0 ==> 5*(7n-b)=w-12b<0
所以7n-b<0即7n<b, 现在就会有5跟12的组合
而此时原来的最优解5n+b>b>7n-b+b,即w=7y并不是最优解,这与最开始是完全矛盾的,所以不可能

下面看当b=7n时
7a-5*7n=w-12b<0 ==> 7*(a-5n)=w-12b<0
有a-5n<0即a<5n,现在就有7跟12的组合
而a+7n>a-5n+5n,同样会得出w=7y不是最优解,产生矛盾

=============================================
下面的只要随便划一下就可以得到:
若q<k,第一组是最优解
若q=k,第二组是最优解
若q>k,第三组是最优解

kamingli

我觉得， 只要组出1来， 那么W就能实现了。 若W为负数， 那么还得组出-1来

kamingli

12-7+5-7 = 3, 7-5 = 2, 3-2 = 1, 那么W就什么都能组合了.