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

时间: 07-18

编程算法 - 多重部分和问题 代码(C)的相关文章

编程算法 - 二叉树的深度 代码(C)

二叉树的深度 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 输入一棵二叉树的根节点, 求该树的深度. 依次选择最深的左右子树, 然后递归加1. 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio.h> #include <stdlib.h> #include <

编程算法 - 迷宫的最短路径 代码(C++)

迷宫的最短路径 代码(C++) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 给定一个大小为N*M的迷宫. 迷宫由通道和墙壁组成, 每一步可以向邻接的上下左右四格的通道移动. 请求出从起点到终点所需的最小步数. 请注意, 本题假定从起点一定可以移动到终点. 使用宽度优先搜索算法(DFS), 依次遍历迷宫的四个方向, 当有可以走且未走过的方向时, 移动并且步数加一. 时间复杂度取决于迷宫的状态数, O(4*M*N)=O(M*N). 代码: /* * m

编程算法 - 翻转单词顺序 代码(C)

翻转单词顺序 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 输入一个英文句子, 翻转句子中单词的顺序, 但单词内字符的顺序不变. 首先翻转(reverse)整个句子, 然后查找空格, 如遇到空格, 则翻转前面的单词, 或遇到结束符, 同样进行翻转. 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #inclu

编程算法 - 左旋转字符串 代码(C)

左旋转字符串 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部. 请定义一个函数实现字符串左旋转操作的功能. 编程珠玑, 首先翻转前部分, 再翻转后部分, 最后全部翻转. 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio

编程算法 - 字符串的排列 代码(C)

字符串的排列 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 输入一个字符串, 打印出该字符串中字符的所有排列. 方法: 使用递归依次交换位置, 打印输出. 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio.h> void Permutation(char* pStr, char

编程算法 - 链表逆序 代码(C)

链表逆序 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 链表逆序, 作为链表操作的基础必须要熟练手写. 主要包含3个部分, 一个指针记录后面节点, 一个指针记录前面节点, 把当前节点指到前面节点, 移动到后面节点, 前后指针依次移动. 非递归链表逆序算法的核心代码只有10行. 代码: /* * main.cpp * * Created on: 2014.9.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.

编程算法 - 扑克牌的顺子 代码(C)

扑克牌的顺子 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 从扑克牌中随机抽取5张牌, 推断是不是一个顺子, 即这5张牌是不是连续的. 2~10为数字本身, A为1, J为11, Q为12, K为13, 而大小王能够看成随意数字. 排序, 推断字符串之间的间隔数, 假设小于等于大小王的数量, 则是连续, 否则不是. 代码: /* * main.cpp * * Created on: 2014.7.12 * Author: spike */

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

部分和问题 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 给定整数a1, a2, ..., an, 判断是否可以从中选出若干数, 使它们的和恰好为k. 解法很多, 最简单的解法是使用深度优先搜索, 时间复杂度O(2^n), 不是最优解法. 代码: /* * main.cpp * * Created on: 2014.7.13 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <s

编程算法 - 两个链表的第一个公共结点 代码(C)

两个链表的第一个公共结点 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 输入两个链表, 找出它们的第一个公共结点. 计算链表的长度, 然后移动较长链表的指针, 使其到相同结点的距离的相同, 再同时移动两个链表的指针, 找到相同元素. 时间复杂度: O(n) 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #i