一道算法问题
两个数组，长度均为22int[] 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 }
从A数组得到序列(对应下标为n)，要求：
Sum(A[n]) A和值为24
Sum(B[n]) B和值最小
--------------------编程问答-------------------- 从A数组得到序列的大小（length）没有限制么？ --------------------编程问答--------------------
没限制。最多就是全部，但这肯定超过了指定的和值。
--------------------编程问答-------------------- 没太看懂需求。
是指A、B两个对应子串满足这两个条件么？ --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答--------------------
是的，取下标，需要满足A、B符合的两个条件
--------------------编程问答-------------------- 写了个深搜，暴力了一下。
--------------------编程问答-------------------- min为最小值。
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());
}
}
}
ans记录了选取的角标序列。
选取的序列是不是可以不连续？
我写的是选取的序列可以是不连续的。 --------------------编程问答-------------------- 就是遍历查找，找到sum(A[n])为24的子列，然后取相同下表的b子列，找到b子列的和最小的就是结果了
for example
import java.util.*;--------------------编程问答-------------------- 正解 - 算法就是这样的 --------------------编程问答-------------------- public class Main {
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 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..............
这是连续下标的 --------------------编程问答--------------------
宝哥，你这个是连续下标的吧。 --------------------编程问答-------------------- 就是0-1背包，用动态规划多好，效率高。 --------------------编程问答--------------------
是的，连续下标，一般取子列都是连续下标的吧，非连续下标也不难，就是组合一下
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);
}
}
}
答案一样。 --------------------编程问答--------------------
-_-
那当然，同一组数组算出来的嘛……
感觉你写的深度优先检索有点像回溯。 --------------------编程问答--------------------
好长时间不搞算法了。
dp都忘得差不多了。
原来背包九讲，基本上都做过题。
--------------------编程问答-------------------- 我的算法是这样的：
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（按比例大小排序）
补充：Java , Java SE
