当前位置：首页 -> AI编程基础 -> c语言编程

编程算法 - 多重部分和问题 代码(C)

2015-01-22 21:12:13 · 作者: · 浏览: 19
标签: 编程 算法 多重 部分 问题 代码

多重部分和问题 代码(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