算法趣题-Q28

        一眼背包问题，那么就是使用动态规划可以比较好的解决，当然在这种数据量比较小的题目也可以暴力，并且也可以不用数组迭代直接递归，如C/C++实现。然而这体由于数据的分布过于离散，使用数组迭代也会有内存浪费，那么可以使用字典或者vector只记录有的数据，不去直接开辟所有空间，如Python实现。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef struct{
	int area, numbers;
}Club;

const int MAX_CLUB_NUM = 10;
const Club clubs[] = { {11000, 40}, {8000, 30}, {400, 24}, {800, 20}, {900, 14},
					   {1800, 16}, {1000, 15}, {7000, 40}, {100, 10}, {300, 12} };

int get_best(int remain, int index)
{
	if (index >= 10 or index < 0)
		return 0;
	if (remain < clubs[index].numbers)
		return 0;
	return max(get_best(remain - clubs[index].numbers, index + 1) + clubs[index].area, get_best(remain, index + 1));
}

int main()
{

	cout << get_best(150, 0) << endl;

	return 0;
}

# coding = utf-8

CLUBS = [(11000, 40), (8000, 30), (400, 24), (800, 20), (900, 14),
         (1800, 16), (1000, 15), (7000, 40), (100, 10), (300, 12)]

iter_list = [(0, 150), ]

if __name__ == '__main__':
    max_area = 0

    for i in range(len(CLUBS)):
        tmp = []
        for item in iter_list:
            if item[1] >= CLUBS[i][1]:
                max_area = max(max_area, item[0] + CLUBS[i][0])
                tmp.append((item[0] + CLUBS[i][0], item[1] - CLUBS[i][1]))
        iter_list.extend(tmp)

    print(max_area)
    pass