背包问题（穷举）的一种非常好理解的简单解法

最近在做算法题，遇到背包问题，网上的办法好是好但不够明了，既然是穷举不是贪心算法，那我就自己想了一个用二进制的算法，如下

思路

设置一个01数组，模拟二进制，比如4个商品，就从0000遍历到1111，不断+1，总共2的四次方种可能。是1就表示取到，0就是不取。穷举没什么好说的，看代码吧，我感觉还是比网上找的那些简洁一些？

测试用例

输入

10 4
7 42
3 12
4 40
5 25

出处：《算法设计与分析》（第3版）清华大学出版社 - Anany Levitin（美）

代码

#include <iostream>
using namespace std;

int main()
{
	int max_price = 0;                /*当前最大承重*/
	int weight_line = 0;			  /*承重线，即背包最大承重*/
	int goods_num = 0;                /*货物数量*/
	int goods_price[100] = {0};       /*货物价格*/
	int goods_weight[100] = { 0 };    /*货物重量*/
	int goods[100] = { 0 };           /*货物编号，0为不取，1为取*/
	int goods_g[100] = { 0 };         /*最后取得的货物*/
	int temp_price = 0;				  /*临时价格*/
	int temp_weight = 0;              /*临时重量*/
	int now_weight = 0;               /*最后取得货物重量*/


	cout << "请输入背包最大承重：" << endl;
	cin >> weight_line;
	cout << "请输入货物数量：" << endl;
	cin >> goods_num;
	cout << "请输入货物重量和价格：" << endl;
	for (int i = 0; i < goods_num; i++) {
		cin >> goods_weight[i];
		cin >> goods_price[i];
	}
	
///*核心部分*///
	for (int i = 0; i < goods_num*goods_num; i++) {
		goods[0] += 1;                    //模拟二进制不断往最低位+1
		temp_price = 0;
		temp_weight = 0;                  
		for (int j = 0; j < goods_num+1; j++) {
			if (goods[j] > 1) {
				goods[j] = 0;
				goods[j + 1] += 1;        //如果某一位大于1，就进位
			}
			if (goods[j] == 1) {          //计算临时的重量和价格，是1就取上
				temp_price += goods_price[j];
				temp_weight += goods_weight[j];    
			}
		}
		if (temp_price >= max_price && temp_weight <= weight_line) {
			max_price = temp_price;
			now_weight = temp_weight;
			copy(begin(goods), end(goods), begin(goods_g));
		}
	}


	cout << "最后结果是：" << endl;
	cout << "取";
	for (int i = 0; i < goods_num; i++) {
		if (goods_g[i] == 1) {
			cout << i+1 << ",";
		}
	}
	cout << "号货物" << endl;
	cout << "最高价值为：";
	cout << max_price << endl;
	cout << "重量为：";
	cout << now_weight << endl;
	return(0);
}

暴力穷举就是最简单粗暴的办法，用高时间复杂度换代码简单和完美解，适用于输入规模小的问题