一道算法问题

从A数组得到序列的大小（length）没有限制么？

写了个深搜，暴力了一下。
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;public class Main {
public static int[] a = { 3, 3, 3, 3, 1, 6, 2, 2, 2, 2, 1, 1, 4, 2, 5, 1, 1, 3, 2, 3, 1, 3 };
public static int[] b = { 1, 21, 36, 61, 118, 122, 129, 144, 144, 149, 157, 167, 208, 344, 395, 407, 517, 531, 544, 561, 587, 631 };
public static int min = Integer.MAX_VALUE;
public static List<Integer> ans = new LinkedList();
public static List<Integer> temp = new LinkedList();
public static int index = -1;

public static void main(String[] args) throws Exception {
dfs(0,0,0);
System.out.println(min);
for(int x:ans){
System.out.print(x+" ");
}
System.out.println();
}
public static void dfs(int pos,int aSum,int bSum){
if(aSum == 24){
min = bSum;
copy(temp,ans);
return;
}
for(int i = pos; i < a.length;i++){
if(a[i]+aSum <= 24 && b[i] + bSum < min){
index++;
temp.add(i);
dfs(i+1,a[i]+aSum,b[i]+bSum);
temp.remove(index);
index--;
}
}
}
public static void copy(List<Integer> src,List<Integer> dest){
dest.clear();
Iterator<Integer> it = src.iterator();
while(it.hasNext()){
dest.add(it.next());
}
}

}

min为最小值。
ans记录了选取的角标序列。选取的序列是不是可以不连续？我写的是选取的序列可以是不连续的。

就是遍历查找，找到sum(A[n])为24的子列，然后取相同下表的b子列，找到b子列的和最小的就是结果了
for example
import java.util.*;
public class Test {
    public static void main(String[] args) throws Throwable {
        int[] a = { 3, 3, 3, 3, 1, 6, 2, 2, 2, 2, 1, 1, 4, 2, 5, 1, 1, 3, 2, 3, 1, 3 };
        int[] b = { 1, 21, 36, 61, 118, 122, 129, 144, 144, 149, 157, 167, 208, 344, 395, 407, 517, 531, 544, 561, 587, 631 };
        List<int[]> list = new ArrayList<int[]>(); //保存找到a子列和为24的，用于检验b子列和是否为最小        int start=-1, end=-1, sa=0, sb=0, suma=0, sumb=0, min=Integer.MAX_VALUE;
        for (int i=0; i<a.length; i++) {
            suma = 0;
            sumb = 0;
            for (int j=i; j<a.length; j++) {
                suma += a[j];
                sumb += b[j];
                if (suma >= 24) {
                    if (suma == 24) {
                        list.add(new int[]{i, j, suma, sumb}); //每次找到a子列就保存
                        if (sumb < min) { //如果b子列的和小于上一次的子列的和
                            start = i; //则保存最小的为最终结果
                            end = j;
                            sa = suma;
                            sb = sumb;
                            min = sumb;
                        }
                    }
                    break;
                }
            }
        }        if (start != -1) {
            System.out.println("----------最终结果----------");
            int[] suba = Arrays.copyOfRange(a, start, end+1);
            int[] subb = Arrays.copyOfRange(b, start, end+1);
            System.out.printf("suma:%d, %s\n", sa, Arrays.toString(suba));
            System.out.printf("sumb:%d, %s\n", sb, Arrays.toString(subb));            System.out.println("----------检验和为24的A子列，并查看B子列的和----------");
            for (int[] f : list) {
                suba = Arrays.copyOfRange(a, f[0], f[1]+1);
                subb = Arrays.copyOfRange(b, f[0], f[1]+1);
                System.out.printf("suma:%d, %s\n", f[2], Arrays.toString(suba));
                System.out.printf("sumb:%d, %s\n", f[3], Arrays.toString(subb));
                System.out.println("-----------------------------------------");
            }
        }
    }
}

public class Main {

public static int[] arg1 = { 3, 3, 3, 3, 1, 6, 2, 2, 2, 2, 1, 1, 4, 2, 5, 1,
1, 3, 2, 3, 1, 3 }; public static int[] arg2 = { 1, 21, 36, 61, 118, 122, 129, 144, 144, 149, 157,
167, 208, 344, 395, 407, 517, 531, 544, 561, 587, 631 }; public static void main(String[] args) {
int sumArg1 = 0;
int sumArg2 = 0;
int[][] sum = new int[6][6];
int sumIndex = 0;

for(int i=0; i< arg1.length;i++ ){
sumArg1 =0;
sumArg2 =0;
for(int j=i; j<arg1.length;j++ ){
sumArg1 += arg1[j];
sumArg2 += arg2[j];
if(sumArg1==24){
sum[0][sumIndex] = sumArg2;
sum[1][sumIndex] = i;
sum[2][sumIndex] = j;
sumIndex ++;
}
}
}
for(int i:sum[0]){
System.out.print(i +"\t");
}
System.out.println();
for(int i:sum[1]){
System.out.print(i +"\t");
}
System.out.println();
for(int i:sum[2]){
System.out.print(i +"\t");
}
}
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class CibTest {
public static void main(String args[]){
int[] a={ 3, 3, 3, 3, 1, 6, 2, 2, 2, 2, 1, 1, 4, 2, 5, 1, 1, 3, 2, 3, 1, 3 };
int[] b={ 1, 21, 36, 61, 118, 122, 129, 144, 144, 149, 157, 167, 208,344,395,407, 517,531,544,561,587,631};
int[] c=new int[22];
int sumA = 0;
int sumB = 0;
int minB = 0;
Map<String,List<Integer>> map =new HashMap<String,List<Integer>>();
List<Integer> list = null;
List<Integer> numberlist = null;
List<Integer> listA = null;
while(c[21]<2){
c[0]++;
int k = 0;
while(k<21){
if(c[k]==2){
c[k]=0;
c[k+1]+=1;
}
k++;
}
list = new ArrayList<Integer>();
numberlist = new ArrayList<Integer>();
listA = new ArrayList<Integer>();
sumA=0;sumB=0;
for(int i=0;i<22;i++){
if(c[i]==1){
sumA+=a[i];
sumB+=b[i];
list.add(b[i]);
numberlist.add(i);
listA.add(a[i]);
}
}
if(sumA==24){
if(minB==0){
minB = sumB;
map.put("listA",listA);
map.put("下标", numberlist);
map.put(minB+"",list);
}
else if(minB > sumB){
map.remove(minB+"");
map.remove("listA");
map.remove("下标");
minB = sumB;
map.put(minB+"",list);
map.put("下标", numberlist);
map.put("listA",listA);
}
}
}
System.out.println(map);
}
}

没刷新页面，貌似搞重复了！！！尴尬ing..............
这是连续下标的

是的，连续下标，一般取子列都是连续下标的吧，非连续下标也不难，就是组合一下
for example
import java.util.*;
public class Test {
    public static void main(String[] args) throws Throwable {
        int[] a = { 3, 3, 3, 3, 1, 6, 2, 2, 2, 2, 1, 1, 4, 2, 5, 1, 1, 3, 2, 3, 1, 3 };
        int[] b = { 1, 21, 36, 61, 118, 122, 129, 144, 144, 149, 157, 167, 208, 344, 395, 407, 517, 531, 544, 561, 587, 631 };
        List<int[]> list = new ArrayList<int[]>();        int suma=0, sumb=0, cnt=0, min=Integer.MAX_VALUE;
        int[] idx = null;        int[] bit = new int[a.length]; //某个位置为1表示这个位置的元素被用于组合
        bit[bit.length-1] = 1;        while (bit[0] < 2) {//从0000000000000000000001到1111111111111111111111遍历
            suma = 0;
            sumb = 0;
            cnt  = 0;
            for (int i=0; i<bit.length; i++) {
                if (bit[i] == 1) { //被选中的元素求和
                    suma += a[i];
                    sumb += b[i];
                    cnt++;
                }
            }            if (suma == 24) { //如果sum(A[n])为24
                int[] t = new int[cnt+2];
                t[0] = suma;
                t[1] = sumb;
                for (int i=0,j=2; i<bit.length; i++) {
                    if (bit[i]==1) {t[j++] = i;}
                }
                list.add(t); //保存被选元素的下标
                if (sumb < min) { //如果sum(B[n])小于上一次的和，则保存最小的一次
                    idx = t;
                    min = sumb;
                }
            }            bit[bit.length-1]++;
            for (int i=bit.length-1; i>0; i--) {
                if (bit[i] == 2) {
                    bit[i] = 0;
                    bit[i-1]++;
                } else {
                    break;
                }
            }
        }        if (idx != null) {
            StringBuilder[] buf = new StringBuilder[2];
            for (int i=0; i<buf.length; i++) {buf[i] = new StringBuilder();}            System.out.println("----------最终结果----------");
            buf[0].append(String.format("suma:%d, [%d", idx[0], a[idx[2]]));
            buf[1].append(String.format("sumb:%d, [%d", idx[1], b[idx[2]]));
            for (int i=3; i<idx.length; i++) {
                buf[0].append(",").append(a[idx[i]]);
                buf[1].append(",").append(b[idx[i]]);
            }
            System.out.printf("%s]\n", buf[0].toString());
            System.out.printf("%s]\n", buf[1].toString());
/*
            System.out.println("----------和为24的A元素组合----------");
            //组合太多，有20几万个
            for (int[] f : list) {
                buf[0].delete(0, buf[0].length());
                buf[1].delete(0, buf[1].length());
                buf[0].append(String.format("suma:%d, [%d", f[0], a[f[2]]));
                buf[1].append(String.format("sumb:%d, [%d", f[1], b[f[2]]));
                for (int i=3; i<f.length; i++) {
                    buf[0].append(",").append(a[f[i]]);
                    buf[1].append(",").append(b[f[i]]);
                }
                System.out.printf("%s]\n", buf[0].toString());
                System.out.printf("%s]\n", buf[1].toString());
                System.out.println("-----------------------------------------");
            }
*/
        }
    }
}

气死，公司掉线半天，不然代码早贴上来了：动态规划的：package com.test;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class DPTest {
public static void main(String args[]) {
int a[]={3, 3, 3, 3, 1, 6, 2, 2, 2, 2, 1, 1, 4, 2, 5, 1, 1, 3, 2, 3, 1, 3 };
int b[]={1, 21, 36, 61, 118, 122, 129, 144, 144, 149, 157, 167, 208, 344, 395, 407, 517, 531, 544, 561, 587, 631 };

int matrix[][]=getDynamicProgrammingMatrix(a,b,24);
List<Integer> ids=getDynamicProgrammingIndexList(matrix,a,24);

System.out.println("满足条件的值：");
System.out.println("下标："+Arrays.toString(ids.toArray()));
System.out.println("Sum(B)的最小值："+matrix[matrix.length-1][24]);
}

static int[][] getDynamicProgrammingMatrix(int weight[],int value[],int limitWeight) {
int len=Math.min(weight.length,value.length);
int m[][]=new int[len+1][];

for(int i=0;i<m.length;i++)
m[i]=new int[limitWeight+1];

for(int i=0;i<m[0].length;i++)
m[0][i]=-1;

for(int i=1;i<=len;i++) {
m[i][0]=-1;
int w=weight[i-1];
int v=value[i-1];

for(int j=1;j<=limitWeight;j++)
if(w==j)
m[i][j]=m[i-1][j]<0?v:Math.min(m[i-1][j],v);
else if(w<j&&m[i-1][j-w]>=0)
if(m[i-1][j]<0)
m[i][j]=m[i-1][j-w]+v;
else
m[i][j]=Math.min(m[i-1][j],m[i-1][j-w]+v);
else
m[i][j]=m[i-1][j];
}

return(m);
}

static List<Integer> getDynamicProgrammingIndexList(int matrix[][],int weight[],int limitWeight) {
List<Integer> list=new ArrayList<Integer>();

for(int i=matrix.length-1;i>0&&matrix[i][limitWeight]>=0;i--) {
if(matrix[i][limitWeight]<matrix[i-1][limitWeight] || matrix[i-1][limitWeight]<0) {
list.add(i-1);
limitWeight-=weight[i-1];
}
}

Collections.reverse(list);

return(list);
}
}

忘记贴结果了：下标：[0,1,2,3,5,6,12]
最小Sum(B)：578

报歉，在下说成子串让人产生误解了。要注意的是a数组的值全部非负。对于这种情况可以对循环进行优化。用一个指针index记录当前求和的子串起点，通过末指针i与index相互合作控制求和子串的区间，以此完成内层循环的功能。
最终可将二重循环优化为一重循环，时间复杂度由O(n^2)减少为O(n)：package com.test;public class PartProgressTest {
public static void main(String args[]) {
int a[]={3, 3, 3, 3, 1, 6, 2, 2, 2, 2, 1, 1, 4, 2, 5, 1, 1, 3, 2, 3, 1, 3 };
int b[]={1, 21, 36, 61, 118, 122, 129, 144, 144, 149, 157, 167, 208, 344, 395, 407, 517, 531, 544, 561, 587, 631 };
int start,index,end,suma,sumb,min=Integer.MAX_VALUE,len=Math.min(a.length,b.length);

start=index=end=suma=sumb=0;

for(int i=0;i<len;i++) {
suma+=a[i];
sumb+=b[i];

if(suma>=24) {
if(suma==24&&sumb<min) {
start=index;
end=i;
min=sumb;
}

suma-=a[index];
sumb-=b[index];
index++;
}
}

if(end>0) {
System.out.println("计算结果：");
System.out.println("起始下标："+start+"\t长度："+(end-start+1));
System.out.println("满足条件的子数组A：");
for(int i=start;i<=end;i++)
System.out.print(a[i]+" ");
System.out.println("\n满足条件的子数组B：");
for(int i=start;i<=end;i++)
System.out.print(b[i]+" ");
System.out.println("\n最小Sum(B)："+min);
}
}
}

我的算法是这样的：
1.算出数组a,b每个元素的比例b[i]/a[i],存入double数组c[i]中。
2.对c[i]进行排序，并将相应的下标存入数组index中。
3.index数组存放的是a,b比例最小的下标，遍历index数组，依次累加相应的a[index[i]],b[index[i]],分别记为sumA,sumB
当sumA为24时，即可得所求结果sumB。由于没装java环境，这里先贴一段c++代码// test2.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"
#include <stdio.h>int _tmain(int argc, _TCHAR* argv[])
{
const int SIZE = 22;
const int TOTAL_SUM_A = 24;
int a[SIZE] = {3,3,3,3,1,6,2,2,2,2,1,1,4,2,5,1,1,3,2,3,1,3};
int b[SIZE] = {1,21,36,61,118,122,129,144,144,149,157,167,208,344,395,407,517,531,544,561,587,631};
double c[SIZE];
for(int i = 0;i <SIZE;i++)
c[i] = b[i] * 1.0 / a[i];//获取数组a,b的比例
int index[22];
for(int i = 0;i < SIZE;i++)
index[i] = i;
//以比例大小进行排序，并依次存放相应的下标
for(int i = 0;i < SIZE;i++){
for(int j = i + 1;j < SIZE;j++){
if(c[i] > c[j]){
int temp = index[i];
index[i] = index[j];
index[j] = temp;
double temp2 = c[i];
c[i] = c[j];
c[j] = temp2;
}
}
}
int sumA = 0;
int sumB = 0;
int result[SIZE];//记录相应的下标
//遍历排序后的下标数组，并累加数组a,b相应的元素
//当数组a累加和为24时，数组b累加和即为所求答案
for(int i = 0,k = 0;i < SIZE;i++){
sumA += a[index[i]];
sumB += b[index[i]];
result[k++] = index[i];
if(sumA == TOTAL_SUM_A){
printf("min sum is %d\n",sumB);
printf("index:");
for(int j = 0;j < k;j++)
printf("%d ",result[j]);
break;
}else if(sumA > TOTAL_SUM_A){
sumA -= a[index[i]];
sumB -= b[index[i]];
--k;
}
}
getchar();
return 0;
}
结果：578
0，1，2，3，5，12，6（按比例大小排序）

调试易

一道算法问题

解决方案 »