編程算法 - 背包問題(三種動態規劃) 代碼(C)

編程算法 - 背包問題(三種動態規劃) 代碼(C)

背包問題(三種動態規劃) 代碼(C)

可以用動態規劃(Dynamic Programming, DP)求解, 可以通過記憶化搜索推導出遞推式, 可以使用三種不同的方向進行求解.

動態規劃主要是狀態轉移, 需要理解清晰.

代碼:

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

/*eclipse cdt, gcc 4.8.1*/

#include 
#include 
#include 

#include 
#include 
#include 

using namespace std;

class Program {
	static const int MAX_N = 100;

	int n=4, W=5;
	int w[MAX_N] = {2,1,3,2}, v[MAX_N]={3,2,4,2};
	int dp[MAX_N+1][MAX_N+1]; //默認初始化為0
public:
	void solve() {
		for (int i=n-1; i>=0; i--) {
			for (int j=0; j<=W; ++j) {
				if (j
輸出:
 
 
result = 7



 
節省空間, 可以使用1維數組的動態規劃.
代碼:
 
/*
 * main.cpp
 *
 *  Created on: 2014.7.17
 *      Author: spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
#include 
#include 

#include 
#include 
#include 

using namespace std;

class Program {
	static const int MAX_N = 100;

	int n=4, W=5;
	int w[MAX_N] = {2,1,3,2}, v[MAX_N]={3,2,4,2};
	int dp[MAX_N+1];
public:
	void solve() {
		memset(dp, 0, sizeof(dp));
		for (int i=0; i=w[i]; --j) {
				dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
			}
		}
		printf(result = %d
, dp[W]);
	}
};


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






輸出:
 
 
result = 7