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