动态规划，动态规划主要是用于求最值的问题，我认为比较重要的东西是 3部分：
1.找到迭代式，也是状态转换方程（注意不是递归，不过递归也是可以做的，但是却不能体现动态规划的好处-“可以通过前面的值来推导出当前的值”，其实这也有个问题，就是必须保证前面的值是无后效性，就是必须保持独立性）
2.设置初始值 （一般考虑 0、1 、2等几个简单的状态）
3.写出代码
下面我列举了两个动态规划的思想 1.0/1背包问题 2.硬币问题
一：0/1背包问题
0/1 背包问题，主要是通过一个限定的 承载量来获得价值最多的物品。其实也是可以用 贪婪算法来做的，但是现在我们就讨论一下动态规划
1.状态方程
（1）首先对 n个物体编号 为： 0、1、2、3... n-1 ;
(2) 对于这个问题 我们首先要知道 两个变量 就是 物件的个数和总容量，因为不管怎么样我们不能超过总的容量
（3）C[i][j] ：表示前i（包括i）个物体，在总容量为j的， 价值最多的
(4) 方程 C[i][j] = max{C[i-1][j],C[i-1][j-W[i]] + P[i]}，
对与 前i个物件，我们可以这样考虑，对于第 i个物件 我们可以放入（保证容量是够的 而且 比前i-1个物件在j容量的价值要大 ），也可以不放入（容量不够，或者 比前i-1个物件在j容量的价值要小），反正就是在容量的允许下，取最大值
/*
* 背包问题
*
**/
void bagOf0_1() {
//背包问题
int W[] = {0,3,4,5};//重量
int P[] = {0,4,5,6};//价值
int C[4][11] = {0};
//C[i][j] = max{C[i-1][j],C[i-1][j-W[i]] + P[i]}
//C[i][j] 表示前i个物件 在容量为j 的总价值
for (int i = 1; i < 4; i++) { //宝石的编号
for (int j = 1 ; j < 11; j++) { //剩余容量的编号
int value1 = C[i-1][j];
int value2 = j-W[i]>=0?(C[i-1][j-W[i]]+P[i]):value1;
C[i][j] = MAX(value1, value2);
}
}
for (int i = 1; i < 4; i++) { //宝石的编号
printf("\n");
for (int j = 1 ; j < 11; j++) { //剩余容量的编号
printf(" %2d ",C[i][j]);
}
}
/*递归调用**/
NSLog(@" maxValue = %d",bagOf0_3(4,10,P,W));
}
下面介绍一个递归调用的方法
/* 递归实现 01背包问题 **/
int bagOf0_3(int i,int j,int P[],int W[]) {
if (i == 0 || j == 0) {
return 0;
}
if (j-W[i] >= 0) {
return MAX(bagOf0_3(i-1,j,P,W), bagOf0_3(i-1,j-W[i],P,W)+ P[i]);
}else {
return bagOf0_3(i-1,j,P,W);
}
}
二：硬币问题问题
描述： 有硬币是 1元 3元 5元，就设x 需要最少多少个硬币数量
/*
* 递推式 是 dp[i] = min{dp[i - iconType[0]] + 1, dp[i - iconType[1]] + 1,..., dp[i - iconType[j]] +1,...}
**/
void needMoneyCount_2() {
//假设100 元需要几个硬币
int dp[101] = {0};
int iconType[] = {1,3,5};
int iconTypeCount = sizeof(iconType)/sizeof(int);
int dpCount = sizeof(dp)/sizeof(int);
//1.设置初始值
// dp[i] = k, 表示i元钱，需要多少个硬币
dp[0] = 0;
//2.写出迭代式 dp[i] = min{dp[i - iconType[0]] + 1, dp[i - iconType[1]] + 1,..., dp[i - iconType[j]] +1,...}
//3.从下标为1 开始计算 （这里有个缺点就是 必须保证 每个值都有解，否则往下走，就不能根据前面计算好的值来）
for (int i = 1;i < dpCount;i++) {
int minCount = INT_MAX;
for (int j = 0; j < iconTypeCount; j ++) {
if (i - iconType[j] >=0) {
if (minCount > (dp[i - iconType[j]] +1)) {
minCount = dp[i - iconType[j]] +1;
}
}
}
dp[i] = minCount;
}
printf("硬币的动态规划 \n");
for (int i = 1 ; i < dpCount; i++) {
printf("dp[%d] = %d、 ",i,dp[i]);
}
}
网友评论