c语言动态规划

① 硬币问题 动态规划 c语言 编程 数学

#include<queue>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stack>
#include<math.h>
#include<stdio.h>
#include<list>
#include<memory.h>
usingnamespacestd;
intmain()
{
inta[12][12],b[12][12],i,j,m,n;
while(cin>>n>>m!=NULL)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cin>>a[i][j];
}
for(i=0;i<=m;i++)
a[0][i]=INFINITY;
for(i=0;i<=n;i++)
a[0][i]=INFINITY;
b[1][1]=a[1][1];
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(i==1&&j==1)
continue;
if(a[i-1][j]>a[i][j-1])
b[i][j]=b[i][j-1]+a[i][j];
else
b[i][j]=b[i-1][j]+a[i][j];
}
}
cout<<b[n][m]<<endl;
}
return0;
}

② C语言-动态规划

#include <stdio.h>
#include <stdlib.h>

​struct tree {
int value;
struct tree *left;
struct tree *right;
};

#define min(x, y) x < y ? x : y

int a[3][3] = {10, 9, 14, 9, 12, 10, 6, 5, 8};

void add_tree_node(struct tree **node, int x, int y, int depth)
{
// printf("x = %d, y = %d, value = %d, depth = %d\n", x, y, a[x][y], depth);
*node = (struct tree *)malloc(sizeof(struct tree));
((struct tree *)*node)->value = a[x][y] + a[x][x];
if(depth == 1) {
((struct tree *)*node)->left = ((struct tree *)*node)->right = NULL;
return;
} else {
add_tree_node(&(((struct tree *)*node)->left), y, (y+1)%3, depth-1);
add_tree_node(&(((struct tree *)*node)->right), y, (y+2)%3, depth-1);
}
depth--;
}

void print_tree(struct tree *t)
{
if(t == NULL)
return;
printf("%d ", t->value);
print_tree(t->left);
print_tree(t->right);
}

void free_tree(struct tree *t)
{
if(t == NULL)
return;
free_tree(t->left);
free_tree(t->right);
free(t);
}

int get_short_time(struct tree *t)
{
if(t->left == NULL || t->right == NULL)
return t->value;
return(min(get_short_time(t->left), get_short_time(t->right))+t->value);
}
void main()
{
struct tree *root;
int i, j, minx=0, miny=1;
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++)
if(i != j && a[minx][miny] > a[i][j])
minx = i, miny = j;
printf("拆卸时间最短的是从第%d套仪器换为第%d套仪器，时间为%d\n", minx+1, miny+1, a[minx][miny]);

// 创建深度为5的二叉树，将做5次试验的全部可能路径都放到二叉树中
add_tree_node(&root, minx, miny, 5);
print_tree(root);
printf("\n");
printf("最短可以完成全部实验的时间是：%d\n", get_short_time(root));
free_tree(root);
}

③ 求C语言动态规划经典例题及答案

类型 *变量=(类型*）malloc(size);
类型 *变量=（类型 *）calloc(n,size);
free(*变量);

类型指的是什么int 啊 char 啊 double啊 还有自定义

④ C程序的动态规划是啥意思

动态规划和贪心算法的区别
动态规划和贪心算法都是一种递推算法
均有局部最优解来推导全局最优解

不同点：
贪心算法：
1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。

动态规划算法：
1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
3.边界条件：即最简单的，可以直接得出的局部最优解
==============================================================================
贪心算法与动态规划
贪心法的基本思路：

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。实现该算法的过程：
从问题的某一初始解出发；

while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解

贪心算法最经典的例子，给钱问题。
比如中国的货币，只看元，有1元2元5元10元20、50、100

如果我要16元，可以拿16个1元，8个2元，但是怎么最少呢？
如果用贪心算，就是我每一次拿那张可能拿的最大的。
比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿个5元，剩下1元
也就是3张 10、5、1。

每次拿能拿的最大的，就是贪心。

但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数
贪心只能得到一个比较好的解，而且贪心算法很好想得到。
再注意，为什么我们的钱可以用贪心呢？因为我们国家的钱的大小设计，正好可以使得贪心算法算出来的是最优解（一般是个国家的钱币都应该这么设计）。如果设计成别的样子情况就不同了
比如某国的钱币分为 1元3元4元
如果要拿6元钱 怎么拿？贪心的话 先拿4 再拿两个1 一共3张钱
实际最优呢？ 两张3元就够了

求最优解的问题，从根本上说是一种对解空间的遍历。最直接的暴力分析容易得到，最优解的解空间通常都是以指数阶增长，因此暴力穷举都是不可行的。
最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，如上面的分析，这是不可行的。
贪心和动态规划本质上是对子问题树的一种修剪。两种算法要求问题都具有的一个性质就是“子问题最优性”。即，组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的。如果以自顶向下的方向看问题树（原问题作根），则，我们每次只需要向下遍历代表最优解的子树就可以保证会得到整体的最优解。形象一点说，可以简单的用一个值（最优值）代表整个子树，而不用去求出这个子树所可能代表的所有值。
动态规划方法代表了这一类问题的一般解法。我们自底向上（从叶子向根）构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。动态规划的代价就取决于可选择的数目（树的叉数）和子问题的的数目（树的节点数，或者是树的高度？）。
贪心算法是动态规划方法的一个特例。贪心特在，可以证明，每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。通常这个值都是对于当前的问题情况下，显而易见的“最优”情况。因此用“贪心”来描述这个算法的本质。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。这样，与动态规划相比，它的代价只取决于子问题的数目，而选择数目总为1。

⑤ 如何用c语言编程实现动态规划

动态规划主要是 状态 & 状态转移方程 如果转移方程写出来了 程序就自然出来啦

对于这题 dp[i][j] 表示 走到格子 (i,j) 时 的总和最大值 val[i][j] 表示格子 (i, j) 的值

那么有 dp[i][j] = max( dp[i-1][j] , dp[i][j-1]) + val[i][j];
当然 边界的时候要特殊考虑一下

for(int i = 1; i <= m ; i++)
for(int j = 1; j <= n; j++)
{
if( i == 1 ) ....;
else if( j == 1 ) ....;
else dp[i][j] = max( dp[i-1][j] , dp[i][j-1]) + val[i][j];
}
最后 dp[m][n] 就是答案啦 ^ ^

⑥ C语言动态规划

定义 d(a, b) 为原字符串中从第 a 个字符开始，包含 b 个阿拉伯数字的数。
定义 s(in, ik) 为以下情况中，最后一个 * 前面 ik 个数的最大乘积：插入 ik + 1 个 * ，最后一个 * 前面有 in + 1 个阿拉伯数字。
则：
s(in, 0) = d(0, in + 1);
s(in, ik) = min{ s(ip, ik - 1) * d(ip + 1, in - ip) } （其中 ip = 0, 1, 2, ..., in - 1）;
题目结果则是 s(n - 1, k + 1) 。

下面是程序，CUnsignedBigNumber 我现写的，可以的话就随便搞一个吧，实在不行我这个再给你。

#include <iostream>
#include <stdlib.h>

CUnsignedBigNumber BiggestProct(unsigned int n, unsigned int k, const char * digits)
{
if (n <= k)
return CUnsignedBigNumber();

CUnsignedBigNumber * intermediateResults = new CUnsignedBigNumber[n * k];
unsigned int ik, in, ip;

for (in = 0; in < n; ++in) // 这里求每个 s(in, 0)
intermediateResults[in].set(digits, in + 1); // d(0, in + 1)

for (ik = 1; ik < k; ++ik)
{
for (in = 0; in < n; ++in)
{
CUnsignedBigNumber & current = intermediateResults[ik * n + in]; // s[in, ik]
for (ip = 0; ip < in; ++ip)
{
CUnsignedBigNumber temp(digits + ip + 1, in - ip); // d(ip + 1, in - ip)
temp *= intermediateResults[(ik - 1) * n + ip]; // d(ip + 1, in - ip) * s(ip, ik - 1)
if (current < temp)
current.swap(temp); // current = temp;
}
}
}

CUnsignedBigNumber result; // s[n - 1, k + 1]
for (ip = 0; ip < in; ++ip)
{
CUnsignedBigNumber temp(digits + ip + 1, n - 1 - ip));
temp *= intermediateResults[(k - 1) * n + ip];
if (result < temp)
result.swap(temp);
}

delete [] intermediateResults;
return result;
}

int main(void)
{
unsigned int n = 0, k = 0;
char digits[21];
scanf("%d%d%s", &n, &k, digits);

std::cout << BiggestProct(n, k, digits) << std::endl;

system("pause");
return 0;
}

⑦ c语言动态规划的一个问题

动态规划关键是找到问题中的子问题，写出状态方程。
这个问题的子问题可以定义为前n件物品，总费用为v的最大价值总和。
先考虑第n件物品，如果c[n]<v的话，它有两种选择，放入背包和不放入背包。它的价值为w[n]*i(i为0或1)，费用c[n]*i(i为0或1),则还需要从n-1件物品中选择费用为v-c[n]*i物品的最大价值总和，所以状态方程为:
f(n,v)=max{f(n-1,v-c[n]*i)+w[n]*i};i根据物品费用和对应的总费用确定取值，即小于对应的总费用时可取0，1，否则为0。
很明显最简单的是从前1件物品中选取，这个就是最后用递归程序编写程序时候的出口。
算法思想就是上面所写的。程序的精华在于思想，仅供你编程参考。

⑧ 一道C语言动态规划题

#include<iostream>
#include<cstring>
using namespace std;

int a[101][101],f[101][101],n,T;

int maxi(int a,int b,int c)
{
if(a<b)
a=b;
if(a<c)
a=c;
return a;
}

int main()
{
cin>>T;
for(;T;T--)
{
cin>>n;
memset(a,0,sizeof(a));
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;cin>>a[i][j],j++);
//f[i][j]=max{f[i+1][j-1],f[i+1][j],f[i+1][j+1]}+a[i][j],1<=i,j<=n.
for(int i=n;i>=1;i--)
for(int j=1;j<=n;j++)
f[i][j]=maxi(f[i+1][j-1],f[i+1][j],f[i+1][j+1])+a[i][j];
int maxans=-32768;
for(int i=1;i<=n;i++)
if(f[1][i]>maxans)
maxans=f[1][i];
cout<<maxans<<endl;
}
return 0;
}

这是一个我写的程序，LZ试试这个可以不

你的程序唯一一处不对劲的地方，就是规划过程中的else语句。把它改成if(j!=0&&j!=m-1)试试？

⑨ C语言，算法，动态规划。我遇到了一个问题，这个问题的题目要求都没看懂。

大概是楼主理解错题意了。
输入的表格是每个分公司分配J台机器（不是分配第J台机器）时的盈利。
最大盈利为每个公司分配一台，30+20+20 = 70