背包問題(遞歸) 代碼(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