編程算法 - 多重部分和問題 代碼(C)

編程算法 - 多重部分和問題 代碼(C)

多重部分和問題 代碼(C)

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

題目: 有n種不同大小的數字a, 每種各m個. 判斷是否可以從這些數字之中選出若干使它們的和恰好為K.

使用動態規劃求解(DP),

方法1: dp[i+1][j] = 用前n種數字是否能加和成j, 時間復雜度O(nKm), 不是最優.

方法2: dp[i+1][j] = 用前i種數加和得到j時, 第i種數最多能剩余多少個. 時間復雜度O(nK).

例如: n=3, a={3,5,8}, m={3,2,2}, K=17時.

i\j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 起始 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0(3,3) 3 -1 -1 2 -1 -1 1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 1(5,2) 2 -1 -1 2 -1 1 2 -1 1 2 0 -1 -1 0 1 -1 -1 -1 2(8,2) 2 -1 -1 2 -1 2 2 -1 2 2 2 1 -1 1 1 -1 1 1

代碼:

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

/*eclipse cdt, gcc 4.8.1*/

#include 
#include 

class Program {
	static const int MAX_N = 100;
	int n = 3;
	int K = 17;
	int a[MAX_N] = {3,5,8};
	int m[MAX_N] = {3,2,2};
	bool dp[MAX_N+1][MAX_N+1];
public:
	void solve() {
		dp[0][0] = true;
		for (int i=0; i= 0) {
					dp[j] = m[i];
				} else if (j < a[i] || dp[j-a[i]]<=0){
					dp[j] = -1;
				} else {
					dp[j] = dp[j-a[i]]-1;
				}
			}
		}
		if (dp[K]>=0) printf("result = Yes\n");
		else printf("result = No\n");
	}
};

int main(void)
{
	Program2 iP;
	iP.solve();

	return 0;
}

result = Yes