首页 > 代码库 > 编程算法 - 多重部分和问题 代码(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 <stdio.h>
#include <memory.h>
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<n; ++i) {
for (int j=0; j<=K; ++j) {
for (int k=0; k<=m[i]&&k*a[i]<=j; ++k) {
dp [i+1][j] |= dp[i][j-k*a[i]]; //或运算
}
}
}
if (dp[n][K]) printf("result = Yes\n");
else printf("result = No\n");
}
};
class Program2 {
static const int MAX_N = 100;
static const int MAX_K = 20;
int n = 3;
int K = 17;
int a[MAX_N] = {3,5,8};
int m[MAX_N] = {3,2,2};
int dp[MAX_K+1];
public:
void solve() {
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i=0; i<n; ++i) {
for (int j=0; j<=K; ++j) {
if (dp[j] >= 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
编程算法 - 多重部分和问题 代码(C)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。