28 动态规划-- 状态与状态转移方程

理论说明

在之前的LCS、递推等中，我们已经梳理了一些较为经典的动态规划问题的解法，本节将对这两种算法进行总结，并探讨解动态规划问题的统一思路。

回顾两种典型问题的算法模式，我们都首先定义了一个数字量，如最长递增子序列中用dp[i]表示以序列中第i个数字结尾的最长递增子序列长度和最长公共子序列中用dp[i][j]表示的两个字符串中前i,j个字符的最长公共子序列，我们就是通过对这两个数字量的不断求解得到答案的。这个数字量被我们称为状态。状态是描述问题当前状态的一个数字量。首先，它是数字的，是可以被抽象出来保存在内存中的。其次，它可以完全的表示一个状态的特征，而不需要其他任何的辅助信息。最后，也是状态最重要的特点，状态之间的转移是完全依赖于各个状态本身的，如最长递增子序列中，dp[x]的值由dp[i]的值确定。若我们在分析动态规划问题的时候能够找到这样一个符合以上所有条件的状态，那么多半这个问题是可以被正确解出的。

我们将注意力放到状态的推移过程中来，由一个或者多个老的状态得出一个新的状态的过程，被称为状态的转移。而之前说到的数字量之间的递推关系就被我们称为状态的转移规则，也称为状态迁移方程，确定状态的转移规则即确定了怎样由前序状态递推求出后续状态。

最后，在说一下，动态规划中，时间复杂度的估计。动态规划问题的时间复杂度由两部分组成：状态数量和状态转移的复杂度，往往程序总的复杂度为他们的乘积。

题目描述

搬寝室是很累的,xhd 深有体会.时间追述 2006 年 7 月 9 号,那天 xhd 迫于无奈要从 27 号楼搬到 3 号楼,因为 10 号要封楼了.看着寝室里的 n 件物品,xhd 开始发呆,因为 n 是一个小于 2000 的整数,实在是太多了,于是 xhd 决定随便搬 2k 件过去就行了.但还是会很累,因为 2k 也不小是一个不大于 n 的整数.幸运的是 xhd 根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd 每次搬两件东西,左手一件右手一件).例如 xhd 左手 拿重量为 3 的物品,右手拿重量为 6 的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的 xhd 希望知道搬完这 2k 件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.

输入说明

每组输入数据有两行,第一行有两个数 n,k(2<=2k<=n<2000).第二行有 n 个整数分别表示 n 件物品的重量(重量是一个小于 2^15 的正整数)

输出说明

对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.

样例展示

样例输入：
2 1
1 3
样例输出：
4

题目分析

基于贪心的思想，在选定的最优方案中，每对物品都是重量相邻的意见物品。在这个结论的前提下，我们设计描述该问题的状态。首先将所有物品按照重量递增排列，并由1和n进行编号。设dp[i][j]为在前j件物品中选择i对物品时最小的疲劳度。那么根据物品j和物品j-1是否被配对选择，该状态由两个来源：若物品j和物品j-1为配对，则物品j一定没被选择，所以dp[i][j]等价于dp[i][j-1];若物品j和物品j-1配对，则dp[i][j]为dp[i-1][j-2]再加上这两件物品配对后产生的疲劳度，即前j-2件物品配成的i-1对再加上最后两件配成的一对物品，共得到i对物品。

综上状态转移方程为：

dp[i][j]=min{dp[i][j-1],dp[i-1][j-2]+(list[i]-list[j)^2

然后确定初始状态：dp[0][i]，即不选择任何一堆物品时，疲劳度为0

C++代码

#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x7fffffff //预定义最大的int值为无穷

int list[20001];
int dp[1001][2001];

int n,k;

int main() {
    while(scanf("%d%d",&n,&k)!=EOF) {
        for(int i=1;i<=n;i++) {
            scanf("%d",&list[i]);
        }
        sort(list+1,list+1+n);
        //初始值
        for(int i=1;i<=n;i++) {
            dp[0][i]=0;
        }
        //递推
        for(int i=1;i<=k;i++) {
            for(int j=2*i;j<=n;j++) {
                if(j>2*i) { //如果j>2i,说明最后两个物品可以不配对，因此将dp[i][j]初始化为dp[i][j-1]
                     dp[i][j]=dp[i][j-1];
                }
                else {
                    dp[i][j]=INF; //如果j==2*i,说明最后两个物品必须配对，不能由dp[i][j-1]得到
                }
                if(dp[i][j]>dp[i-1][j-2]+(list[i]-list[j])*(list[i]-list[j])) {
                    dp[i][j]=dp[i-1][j-2]+(list[i]-list[j])*(list[i]-list[j]);
                }
            }
        }
        printf("%d\n",dp[k][n]);
    }    
    return 0;
}

Greedy Tino

题目描述

Tino wrote a long long story. BUT! in Chinese... So I have to tell you the problem directly and discard his long long story. That is tino want to carry some oranges with "Carrying pole", and he must make two side of the Carrying pole are the same weight. Each orange have its' weight. So greedy tino want to know the maximum weight he can carry.

输入说明

The first line of input contains a number t, which means there are t cases of the test data. for each test case, the first line contain a number n, indicate the number of oranges. the second line contains n numbers, Wi, indicate the weight of each orange n is between 1 and 100, inclusive. Wi is between 0 and 2000, inclusive. the sum of Wi is equal or less than 2000.

输出说明

For each test case, output the maximum weight in one side of Carrying pole. If you can't carry any orange, output -1. Output format is shown in Sample Output.

样例展示

样例输入：
1
5
1 2 3 4 5
样例输出：
Case 1:7

问题分析

本题大意:有一堆柑橘，重量为0到2000,总重量不超过2000。要求我们从中取出两堆放在扁担的两头且两头的重量相等，问符合条件的每堆重量最大为多少。没有符合条件的分堆方式则输出-1.

在求解该问题之前，我们首先关注本题的输入特点。与以往我们讨论过的问题不同，该例在输入中将预先告诉我们输入的测试数据个数，即整数T。所以我们的程序只需要准确的处理T组数据即可，一面照成不必要的错误。

首先，我们只考虑柑橘重量非0的情况。

因为本题要求解的是重量相等的两堆柑橘中每堆的最大数量，并且在堆放过程中，由于新的柑橘被加到第一堆或者第二队，两堆之间的重量差会动态发生改变，所以我们设定状态dp[i][j]表示前i个柑橘被选择后，第一堆比第二堆中j时（note:当j为负数时表示第二堆比第一堆中），两堆的最大总重量和。

初始时，dp[0][0]为0，即不在两堆中加任意柑橘时，两堆最大总重量为0，dp[0][j]为负无穷，即其他状态都不存在。

根据每一个新加入的柑橘被加入到第一堆还是第二堆或者不加到任何一堆，设当前加入柑橘重量list[i],这将造成第一堆与第二堆的重量差增大list[i]或者减小list[i]或者不变，我们在他们之间取最大值。

因此，递推公式：

dp[i][j]表示前i个柑橘被选择后，第一堆比第二堆重j时两堆的最大总重量和
dp[i][j]=max(dp[i-1][j-list[i]]+list[i],
             dp[i-1][j+list[i]]+list[i],
             dp[i-1][j])

C++代码