拆分整数为2的幂次项和 → 理解多重背包问题二进制优化的核心思想

【题目描述】
输入一个整数，输出为2的幂次项和的形式。

【输入样例】
26

【输出样例】
26=1+2+4+8+11

【算法分析】
理解了此题，就明白了多重背包问题的二进制优化的主要思想。
多重背包问题的二进制优化思想解析及题目详见 https://blog.csdn.net/hnjzsyjyj/article/details/126190151

为了方便说明问题，此处简述多重背包问题的二进制优化思想如下：
多重背包问题通常可转化成01背包问题求解。但若将每种物品的数量拆分成多个1的话，时间复杂度会很高，从而导致TLE。所以，需要利用二进制优化思想。即：一个正整数n，可以被分解成1,2,4,…,2^(k-1),n-2^k+1的形式。其中，k是满足n-2^k+1>0的最大整数。
例如，假设给定价值为2，数量为10的物品，依据二进制优化思想可将10分解为1+2+4+3，则原来单个价值为2，数量为10的物品可等效转化为价值分别为1*2，2*2，4*2，3*2，即价值分别为2，4，8，6，数量均为1的物品。
 .
【算法代码一】

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin>>n;
	cout<<n<<"=";

	int k=1;
	while(k<=n) {
		if(k==n) cout<<k;
		else cout<<k<<"+";
		n=n-k;
		k=k*2;
	}

	if(n>0) {
		cout<<n;
	}
	
	return 0;
}

/*
in1:
26
out1:
26=1+2+4+8+11

in2:
7
out2:
7=1+2+4
*/

【算法代码二】

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin>>n;
	cout<<n<<"=";

    int t=0;
	int k=1;
	while(k<=n) {
		if(k==n) cout<<"2^"<<t;
		else cout<<"2^"<<t<<"+";
		n=n-k;
		k=k*2;
		t++;
	}

	if(n>0) {
		cout<<n;
	}
	
	return 0;
}

/*
in1:
26
out1:
26=2^0+2^1+2^2+2^3+11


in2:
7
out2:
7=2^0+2^1+2^2
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/126190151