【算法竞赛入门经典】多阶段决策问题 例题9-5 UVa12563

• 【算法竞赛入门经典】多阶段决策问题 例题9-5 UVa12563

例题UVa12563

Input

Output

Sample Input

2
3 100
60 70 80
3 100
30 69 70

Sample Output

Case 1: 2 758
Case 2: 3 777

分析

这是一个0-1背包问题，但是和普通的0-1背包不同的是，他有两个决策条件
决策条件1：相同时间内唱的歌曲要尽量多
决策条件2：满足决策条件1的同时，唱歌的时长要尽量多
鉴于此，有两种做法
Tip：本处所有的方法均利用了滚动数组优化了空间，因此只需要d[j]表示第j分钟时的情况【这也导致了分钟j必须从后往前扫描】
方法1：只记录d[j]表示第j分钟时，最多能唱歌的数目
因为仅仅记录了歌曲的数目，实际上没有办法判定你实际能够唱多长时间的歌。因此，为了知道自己唱了多久的歌曲，应该只允许前j分钟填满的情况出现，即除了最后一段，之前不允许存在空1秒的情况，这样的话，d[j]的值等于最大歌曲数目的那一个j值就是实际唱了多少分钟。这用

if((j==tim[i])||dp[j-tim[i]]>0){
    dp[j]=max(dp[j],dp[j-tim[i]]+1);
    num=max(num,dp[j]);
}

来保证。
为了避免这样麻烦的情况出现，不如新增加一个数组dpt来记录实际能够唱歌的时间。这样就有了方法二
方法2：最多曲目和时间都记录
由于决策条件2制于决策条件1，dpt数组的更改必须严格满足新的条件下，dp[j]的值大于或等于最大曲目数量。只有满足这个条件才最dpt数组进行更新操作。

样例实现代码

第一种：只记录最大曲目

#include<iostream>
#include<cstring>
#include<cmath>
#define maxn 50+5
#define maxt 10000
using namespace std;
int tim[maxn],dp[maxt];
int main(){
    int n,t,T,kase=0;
    cin>>T;
    while(T--){
        cin>>n>>t;
        int num=0;
        for(int i=1;i<=n;i++)
            cin>>tim[i];
        memset(dp,0,sizeof(dp));
        t--;
        for(int i=1;i<=n;i++){
            for(int j=t;j>=tim[i];j--){
                if((j==tim[i])||dp[j-tim[i]]>0){
                    dp[j]=max(dp[j],dp[j-tim[i]]+1);
                    num=max(num,dp[j]);
                }
            }
        }
        int j=t;
        for(;dp[j]!=num;j--);
        if(num==0)
            cout<<"Case "<<++kase<<": "<<num+1<<" "<<678<<endl;
        else
            cout<<"Case "<<++kase<<": "<<num+1<<" "<<j+678<<endl;
    }
    return 0;
}

第二种：最大曲目和时间都记录

#include<iostream>
#include<cstring>
#include<cmath>
#define maxn 50+5
#define maxt 10000
using namespace std;
int tim[maxn],dp[maxt],dpt[maxt];
int main(){
    int n,t,T,kase=0;
    cin>>T;
    while(T--){
        cin>>n>>t;
        int num=0;
        for(int i=1;i<=n;i++)
            cin>>tim[i];
        memset(dp,0,sizeof(dp));
        memset(dpt,0,sizeof(dpt));
        t--;
        for(int i=1;i<=n;i++){
            for(int j=t;j>=tim[i];j--){
                if(dp[j]<dp[j-tim[i]]+1){
                    dp[j]=dp[j-tim[i]]+1;
                    dpt[j]=dpt[j-tim[i]]+tim[i];
                }
                else if(dp[j]==dp[j-tim[i]]+1)
                    dpt[j]=max(dpt[j],dpt[j-tim[i]]+tim[i]);
            }
        }
        cout<<"Case "<<++kase<<": "<<dp[t]+1<<" "<<dpt[t]+678<<endl;
    }
    return 0;
}

结果

20844486为只记录最大曲目
20845255为都记录