Greedy Tino动态规划问题-搬橘子

• 例7.6 Greedy Tino（九度教程第100题）

题目大意：给定n个橘子的重量，要求从这些橘子中选出若干个分成两堆，使得这两堆的重量相同，问这两堆橘子的总重量是多少？

解法：使用动态规划。dp[i][j]表示放入第i个橙子之后，第一堆比第二堆重j，两堆的总重量，dp[][]的每一个值代表一个状态，求出所有状态之后，dp[n][0]/2即为所得。
代码如下：

//动态规划问题
#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define OFFSET 2000//因为两堆的重量差j可能是负数，所以选j+OFFSET作为数组下标
int ganju[101];//柑橘重量
int dp[101][4001];//状态转移数组，其中dp[i][j]表示放入第i个橙子之后，第一堆比第二堆重j，两堆的总重量
int main()
{
    int T;
    int cases=0;
    cin>>T;
    while(T--){
        int n;//n个柑橘
        cin>>n;
        int cnt=0;//记录有多少个重量非0的柑橘
        bool havezero=false;
        for(int i=1;i<=n;i++)
            {
                cin>>ganju[++cnt];//输入橘子的重量
                if(ganju[cnt]==0)
                {
                    cnt--;
                    havezero=true;
                }
            }
        n=cnt;
        //初始化
        for(int i=-2000;i<=2000;i++)
            dp[0][i+OFFSET]=-INF;//状态不存在
        dp[0][0+OFFSET]=0;//选0个橘子，两堆重量差是0时，重量和也是0
        //算法
        for(int i=1;i<=n;i++){//每一个橘子
            for(int j=-2000;j<=2000;j++){//每种重量
                int tmp1=-INF,tmp2=-INF;
                if(j+ganju[i]<=2000 && dp[i-1][j+ganju[i]+OFFSET]!=-INF)
                    tmp1=dp[i-1][j+ganju[i]+OFFSET]+ganju[i];//有第一堆转化而来
                if(j-ganju[i]>=-2000 && dp[i-1][j-ganju[i]+OFFSET]!=INF)
                    tmp2=dp[i-1][j-ganju[i]+OFFSET]+ganju[i];//由第二堆转化而来
                if(tmp1<tmp2)
                    tmp1=tmp2;5
                if(tmp1<dp[i-1][j+OFFSET])
                    tmp1=dp[i-1][j+OFFSET];//与柑橘不放入任何堆的原状态比较，取最大值
                dp[i][j+OFFSET]=tmp1;//加入这个橘子后，当前状态值为三个状态转化而来的最大值
            }
        }
        cases++;
        cout<<"Case"<<cases<<":";
        if(dp[n][0+OFFSET]==0)
            puts(havezero==true?"0":"-1");//puts()自动换行
        else
            cout<<dp[n][0+OFFSET]/2<<endl;

    }
    return 0;
}