背包问题(递归) 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 有n个重量和价值分别为w,v的物品, 从这些物品中挑选出总重量不超过W的物品, 求所有挑选方案中价值总和的最大值.

即经典动态规划问题.

可以使用深度优先搜索, 把每个部分都遍历到, 选取最优解, 但不是最好的方法.

代码:

/*
 * main.cpp
 *
 *  Created on: 2014.7.17
 *      Author: spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>
#include <limits.h>

#include <utility>
#include <queue>
#include <algorithm>

using namespace std;

class Program {
	static const int MAX_N = 10000;

	int n=4, W=5;
	int w[MAX_N] = {2,1,3,2}, v[MAX_N]={3,2,4,2};

	int rec (int i, int j) {
		int res;
		if (i==n) {
			res = 0;
		} else if (j<w[i]) {
			res = rec(i+1, j);
		} else {
			res = max(rec(i+1,j), rec(i+1, j-w[i])+v[i] );
		}
		return res;
	}
public:
	void solve() {
		printf("result = %d\n", rec(0, W));
	}
};


int main(void)
{
	Program P;
	P.solve();
    return 0;
}

result = 7