本文主要是介绍无聊的逗(二进制法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
c++版
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{int n;//n个木棍 每根的长度 cin>>n;int length[20]={0};//存每个木棍的长度 int number[1<<n]={0};//存储每一种组合方式的总长度 难道是因为没有初始化的原因?? 数组初始化很重要for(int i=0;i<n;i++){cin>>length[i]; number[1<<i]=length[i]; //只有一根木棍的时候的长度 也是一种组合情况 //移位是表示用了第几根木棍 }for(int i=0;i<(1<<n);i++) //遍历每一种组合方式 i=0 空集也是一种组合方式 {for(int j=0;j<n;j++)//每一种木棍的情况 {if((i&(1<<j))==0)//没有重合的木棍 因为j是10进制 i是二进制 1<<j把转换成二进制就能知道当前是取的哪个木棍了 {continue;}number[i]=number[i-(1<<j)]+length[j];//存入该组合的排列长度 break;}}int MAX=0;for(int i=0;i<(1<<n);i++){int j=(1<<n)-1-i;//用总的组合- i当前的排列 就是除了i的其他所有的组合for(int k=j;k>0;k=(k-1)&j) //因为j才是剩下没用的木棍,不是i,所以是和j按位与 {//cout<<number[k]<<" " ;if(number[k]==number[i]){MAX=max(MAX,number[i]);}}}cout<<MAX;return 0;
}
别人写的java版(我也写了很多自己的注释进去)
package com.lanqiao;import java.util.Scanner;/*** @author */
public class 算法训练_无聊的逗 {static int n;static int[] nums;/*** 最长的相同木棍长度*/static int maxLength = Integer.MIN_VALUE;/*** 存储某种排列组合下木棍的长度*/static int[] length;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();nums = new int[n];//对于n个木棍,共有2^n种排列组合方式 就是相当有n个元素有2^n个集合 length = new int[1<<n];//1<<n二进制的1向左移动n位得到的答案和2^n相等 开这么大的数组 for(int i=0;i<n;i++){nums[i] = scanner.nextInt();//存入几个木棍长度 //1<<i表示的下标 指的是只选第i根木棍的长度length[1<<i] = nums[i];//因为i是从0开始的 如果i从1开始 length[1<<(i-1)] = nums[i];只选第一根木棍的长度 }//遍历存储每一种选择方式的长度,i=1的情况for(int i = 0;i < ( 1 << n ); i++){//这是二进制的表现形式 //这一层遍历是用来选择木棍的for(int j = 0;j < n;j++){//如果i这种情况和选择木棍j有冲突,也就是第i种选择方式并没有选择第j跟木棍//举个例子,比如i为4,二进制就是100(选了第三根木棍),但是j为0,也就是选择了第1根木棍//此时 1<<j = 001 那么第i种情况明显没有选择木棍j,所以他们进行按位与运算的结果就是0//因此这种情况出现冲突,不用进行运算if((i & (1<<j) ) == 0){//说明当前的j与组合方式没有选到同一个木棍,后面赋值就不准确 continue;//后面的语句不再执行 ,又执行 for语句中的j++ }//如果这种情况考虑在内了,那么第i种情况的长度就是木棍j的长度加上情况i不选择木棍j的长度//还是举个例子//比如目前i是5,也就是101,j是2,也就是第三根木棍,此时1<<j = 100,//那么第i种组合的情况其实就是i = 001 时的长度加上木棍j的长度length[i] = length[i - (1<<j)] + nums[j];//这个break是用来防止重复计算的 进入下一个组合 break;}}//枚举每一种情况ifor(int i=0;i< (1 << n);i++){//j就是选出了所有情况i没有选择的木棍的情况,(1<<n) -1指的是选择了所有木棍的一种情况//1<<n 就是第n+1位为1,其余每一位为0,比如n=5时,表示100000,//1<<n - 1 就是从1到第n位每一位都为1,比如n=5时,表示的就是11111;用11111-当前的情况就是另一种没选的 //(1<<n) - 1 -i 就是选择了所有i没有选择的木棍的情况,比如n=5,i=3//那么(1<<n)-1 = 11111,i=00011,那么(1<<n) - 1 -i = 11100int j = (1 << n) -1 -i;//j是剩下的木棍 //接下来的循环是尝试从选择了全部i没选的木棍的情况开始枚举//枚举每一种可能的选择情况,k--会存在不合理的数据,比如说现在剩下的木棍是11000,而k当前枚举到的实是10000,//那么此时k-- = 01111,后面会多出三个木棍,所以我们需要使用按位与来去除多余的木棍,for(int k = j;k > 0;k = (k-1)&j){//没选的多种情况 if(length[k] == length[i]){//木棍长度相等 maxLength = Math.max(maxLength,length[k]);//选择其中较大的数 }}}System.out.println(maxLength);}}
这篇关于无聊的逗(二进制法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!