<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
<title>无标题文档</title>
</head>
<style type="text/css"> 
body{ font-size:36px; line-height:24px;} 
textarea{ font-size:24px;} 
</style> 
<body>
<form id="form1" name="form1" method="post" action="">
  <label>动态规划<br>
  <textarea name="textarea" rows="40" cols="100">
 1.题目描述
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
输入
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。
输出
输出数据只有一个整数，表示计算出的最大值。
示例输入:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
示例输出:
30 
 #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int a[105][105] = {0};
int dp[105][105] = {0};

int main(){
    int n;
    cin>>n;
    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= i; j++ )
            cin>>a[i][j];
    for( int i = 1; i <= n; i++ )    
        for( int j = 1; j <= i; j++ )
            dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + a[i][j];
    int ans = 0;
    for( int j = 1; j <= n; j++ )
        ans = max(ans,dp[n][j]);
    cout<<ans<<endl;
    return 0;
} 
2.题目描述
蒜头君要回家，如图所示(两个0的位置)，蒜头君在左下角位置，家在右上角位置。蒜头君走上一个格子会花费一定的体力（每个格子上的数字表示蒜头君要花费的体力值）。每一步蒜头君只能走到上面或右面的与当前相邻的一个格子。蒜头君想知道他回到家需要花费的最少体力值是多少？
5 4 0
6 2 5
0 3 4
解题思路：
蒜头君只能走到上面或右面的与当前相邻的一个格子，所以到家的前一步只有两种情况：
1：从家的左边一个格子向右走到家
2：从家的下边一个格子向上走回家
这样可以得到递推式：
Fi,j  =  min ( Fi-1,j , Fi,j-1) + Ai,j    ,Ai,j 表示在点（i,j）花费的力气


#include<stdio.h>
#include<algorithm>
using namespace std;
 
int a[110][110];
int dp[110][110]; 
int n;
 
void solve()
{
	dp[0][0] = 0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(i == 0 && j == 0)  //边界点，如果都为0意味着初始的位置，花费力气为0 
			   continue;
			else if(i == 0)            //边界点，如果 i 为0表示只能向上走才能到家 
			    dp[i][j] = dp[i][j-1] + a[i][j];
			else if(j == 0)            //边界点，如果 j 为0表示只能向右走才能到家 
			    dp[i][j] = dp[i-1][j] + a[i][j];
			else
			    dp[i][j] = min(dp[i][j-1] , dp[i-1][j])+a[i][j];//状态转移方程
		}
	}
	printf("%d",dp[n-1][n-1]); 
}
 
int main()
{
	scanf("%d",&n);// n x n的矩阵
	for(int i=0;i<n;i++)
	{
		getchar();
		for(int j=0;j<n;j++)
		    scanf("%d",&a[i][j]);
	}
	solve();
	
	return 0;
}


3.题目描述
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述 Input Description
一个整数v，表示箱子容量
一个整数n，表示有n个物品
接下来n个整数，分别表示这n 个物品的各自体积
输出描述 Output Description
一个整数，表示箱子剩余空间。

#include <iostream>
#include <cstring>
using namespace std;
int max(int x, int y)
{
  return x>y?x:y;
}
int main()
{
  int v,n;
  cin >> v >> n;
  int a[n];
  int dp[v+1];
  memset(dp, 0, sizeof(dp));
/*
分析：背包型动态规划，相当于背包容量和背包中物品价值二者相等的一般背包问题。（貌似也称为伪背包问题）
对于每一个物品i，都存在放入箱子和不放入箱子两种情况。当前箱子容量剩余j时，若i放入，则为dp[j-a[i]]+a[i])；
若i不放入，则为dp[i]；因此，状态转移方程为：dp[j] = max(dp[j], dp[j-a[i]]+a[i])。*/
  for(int i=0; i<n; i++)//n个物品循环
  {
    cin>>a[i];
    for(int j=v; j>=a[i]; j--)//剩余容量
    {
      dp[j] = max(dp[j], dp[j-a[i]]+a[i]);
    }
  }
  cout << v-dp[v];
}
 
4.题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入
第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出
包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
提示
数据规模和约定
对于30%的数据，M <= 10；
对于全部的数据，M <= 100。
运用动态规划建立数组dp[m][t]，其涵义是，在t时间内，在前m个草药里挑到的最大的价值。
核心代码是：
if(tm[m]>t) dp[m][t]=dp[m-1][t];
else
{
dp[m][t]=max(dp[m-1][t-tm[m]]+v[m],dp[m-1][t]);
}
即若m号草药tm[m]的时间大于现在的时间t时，则m号物体不能选择，于是前m种的情况与前m-1种的情况一样。
即dp[m][t]=dp[m-1][t]。
反之，则比较前m-1个物体时且时间为t-tm[m]时的最大价值+m号元素的价值v[m]（即选择了m号药草）与dp[m-1][t]（不选择m号药草）的大小，选择其最大值。
因为建立的dp与T与M相关，循环的次数与之相关。故时间复杂度为O(T*M)。
方法1：
#include <iostream>
using namespace std;
#define Max_T 1005
#define Max_M 105
 
int main()
{
    ///代表在前n种草药与t时间内能够获得的最大的价值
    int dp[Max_M][Max_T];
    ///记录草药的价值与要花费的时间
    int v[Max_M],tm[Max_M];
    int T,M;
    cin>>T>>M;
    for(int i=0;i<=M;i++)
    {
        ///当t=0时，价值肯定为0
        dp[i][0]=0;
    }
    for(int i=0;i<=T;i++)
    {
        ///当m=0时，价值肯定为0
        dp[0][i]=0;
    }
    for(int i=1;i<=M;i++)
        cin>>tm[i]>>v[i];
    for(int m=1;m<=M;m++)
    {
        for(int t=1;t<=T;t++)
        {
            if(tm[m]>t) dp[m][t]=dp[m-1][t];
            else
            {
                dp[m][t]=max(dp[m-1][t-tm[m]]+v[m],dp[m-1][t]);
            }
        }
    }
    cout<<dp[M][T]<<endl;
    return 0;
}

这样做的话如果数据量大的话会内存超限，所以考虑只有2行的二维数组的改进：
方法2：
#include<bits/stdc++.h>
using namespace std;
int main(){
	 
	int a[101]={0},v[101]={0}, dp[2][1001]={0};
	int m,t,i,j;
	scanf("%d%d",&t,&m);
	for(i=1;i<=m;i++)scanf("%d%d",&a[i],&v[i]);
	for(i=1;i<=m;i++){
		for(j=1;j<=t;j++){
			if(j<a[i])dp[1][j]=dp[0][j];
			else
			dp[1][j]=max( dp[0][j],dp[0][j-a[i]]+v[i]);
			
		}
		memcpy(dp[0],dp[1],sizeof(dp[0]));//复制数组第1行数据到第0行 ，重复更新新旧阶段数据 
		
	}
	printf("%d",dp[1][t]);
   
}
利用每个阶段的各状态的最优值只跟上一阶段小于或等于本阶段状态下标的原理能减少内存到只有1行的一维数组的更狠的改进：
方法3：
#include<bits/stdc++.h>
using namespace std;
int dp[1010];
 
int main() {
	int t, m;
	cin >> t >> m;
	int price, value;
	for(int i = 0; i < m; i++) {
		cin >> price >> value;
		for(int j = t; j >= price; j--) {
			dp[j] = max(dp[j], dp[j - price] + value);
		}
	}
 
	cout << dp[t];
}
 
  </textarea>
  </label>
</form>
</body>
</html>