編程算法 - 完全背包問題 代碼(C)

編程算法 - 完全背包問題 代碼(C)

完全背包問題 代碼(C)

題目: 有n個重量和價值分別為w,v的物品, 從這些物品中挑選出總重量不超過W的物品, 求所有挑選方案中價值總和的最大值.

*每件物品可以挑選任意多件.

動態規劃: 每次選取最大的組合, 加入到數組, 第一種時間復雜度O(nW^2), 第二種時間復雜度O(nW).

解法1, max()部分表明, 要麼來源於上面, 要麼來源於前面.

代碼:

/*
 * 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];
public:
	void solve() {
		for (int i=0; i
輸出:
 
 
result = 10





為了節約內存, 可以使用一維數組進行求解.
 
代碼:
 
/*
 * 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=3, W=7;
	int w[MAX_N] = {3,4,2}, v[MAX_N]={4,5,3};
	int dp[MAX_N+1];
public:
	void solve() {
		memset(dp, 0, sizeof(dp));
		for (int i=0; i
輸出:
 
 
result = 10