（0-1背包）Jin Ge Jin Qu，UVa 12563

部分转自：https://blog.csdn.net/u013480600/article/details/40376143
UVA 12563 Jin Ge Jin Qu hao(01背包变形:两个条件最优化)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4008

题意:

   KTV里面有n首歌曲你可以选择,每首歌曲的时长都给出了. 对于每首歌曲,你最多只能唱1遍. 现在给你一个时间限制t (t<=10^9) , 问你在最多t-1秒的时间内可以唱多少首歌曲num , 且最长唱歌时间是多少time (**time必须<=t-1**) ? 最终输出num+1 和 time+678 即可.

   注意: 你需要优先让歌曲数目最大的情况下,再去选择总时长最长的.

分析:

   其实本题本质上就是一个标准的01背包问题. 问你<=t-1时间内最多可以选择哪些歌曲使得 (数据1,数据2) 最优. 这里的**数据1**是歌曲数目, **数据2**是歌曲总时长, 且**数据1优先.**

   一般我们做的01背包问题都是问你<=t-1的时间内, 最多选择哪些歌曲使得歌曲数目最多 **或** 总时间最长. 但是本题需要同时考虑两个最优条件, 那么该怎么做呢?

   我们令dp[i][j]==x 表示当决策完全前i个物品后(选或不选), 所选的总歌曲时长<=j时, 所得到的**最优状态**为x. (**这里的x就不是平时我们所说的最长时间或最多歌曲数目了**)

   怎么理解最优状态为x这个事实呢? 假设有两种选择前i个歌曲的方法能使得**决策完前i个物品且总时长<=j时的状态**分别为x1 和x2.

   那么如果x1状态的歌曲数目> x2状态的歌曲数目, 那么明显x1状态更优. 所以dp[i][j]应==x1.

   如果x1状态的歌曲数目与x2的相等, 但是x2状态的时长 > x1状态时长, 那么此时x2状态更优. 所以dp[i][j]应==x2.

   经过上面的分析,我们可以用一个(具有歌曲数和总时长双属性的)结构体来表示一个状态. 且可以得到下面状态转移公式:

   dp[i][j] = **最优( **dp[i-1][j] **, ** 在dp[i-1][j-t[i]]的基础上选择第i首歌后得到的新状态tmp **)**

   所有dp初始化为0即可. 最终我们所求为dp[n][max_time]

   最后还有一个问题就是t<=10^9.我们不可能循环判断j到10^9\. 其实一共50首歌曲, 每首歌曲最多180秒, 所以我们求出所有歌曲的时长和sum(sum<=50*180==9000).

   如果t-1>=sum, 那么明显所有歌曲都能被选一遍.

   如果t-1<sum,那么明显我们需要遍历到dp[i][t-1]为止.

   程序实现用的滚动数组,所以dp只有[j]这一维.

这里贴三份代码

这份主要在于结构体的使用

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
const int maxn=180*50+5;  
  
int n,max_t;  
int t[50+5]; //每首歌曲的时间  
struct Node  
{  
    int num; //总歌曲数  
    int time;//歌总时间  
    bool operator<(const Node &rhs)const//判断是否更优  
    {  
        return num<rhs.num || (num==rhs.num && time<rhs.time);  
    }  
}dp[maxn];  
  
int main()  
{  
    int T;  
    scanf("%d",&T);  
    for(int kase=1;kase<=T;kase++)  
    {  
        printf("Case %d: ",kase);  
  
        scanf("%d%d",&n,&max_t);  
        memset(dp,0,sizeof(dp));  
  
        int sum=0;//所有歌曲总时长  
        for(int i=1;i<=n;i++)  
        {  
            scanf("%d",&t[i]);  
            sum +=t[i];  
        }  
        //max_t是我们最大需要考虑的时间  
        max_t = min(sum,max_t-1);  
        //注意max_t==sum和max_t==0时的情况.  
  
        int ans=0;  
        for(int i=1;i<=n;i++)  
        {  
            for(int j=max_t;j>=t[i];j--)  
            {  
                Node tmp;//tmp表示当选择第i首歌时的情况  
                tmp.num  = dp[j-t[i]].num+1;  
                tmp.time = dp[j-t[i]].time+t[i];  
                if(dp[j]<tmp)//tmp更优  
                {  
                    dp[j]=tmp;  
                }  
            }  
        }  
        printf("%d %d\n",dp[max_t].num+1,dp[max_t].time+678);  
    }  
    return 0;  
}  

这份在于滚动数组的使用

#include<cstdio> 
#include<iostream> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
#define maxn 100000 
int dp[maxn],d[maxn]; 
int main() { 
        // freopen("input.txt","r",stdin); 
    int q; 
    scanf("%d",&q); 
    for(int w=1;w<=q;w++) 
    { 
        int n,t,i,j,a; 
        scanf("%d%d",&n,&t); 
        memset(dp,0,sizeof(dp)); 
        memset(d,0,sizeof(d)); 
        for(i=1;i<=n;i++) { //正序
            scanf("%d",&a); 
            for(j=t-1;j>=a;j--) {//逆序
                if(dp[j]<dp[j-a]+1){
                    dp[j]=dp[j-a]+1; 
                    d[j]=a+d[j-a] ;
                } else if(dp[j]==dp[j-a]+1){ 
                        d[j]=max(d[j-a]+a,d[j]); 
                                }
                            } 
          } 
          printf("Case %d: %d %d\n",w,dp[t-1]+1,d[t-1]+678); 
      } 
      return 0; 
}

第三份就是照着书上二维实现的代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 100;
int d[maxn][maxn+10000];
int path[maxn][maxn+10000];//前i个在第j秒最多能唱的歌曲数目；
int w[maxn];
int n,t;

int main(){
    int cont;
    scanf("%d", &cont);
    int cnt = 0;
    while(cont--){
        cnt++;
        scanf("%d %d", &n ,&t);
    for(int i = 1; i <= n; i++){
        scanf("%d", &w[i]);
    }
    memset(path, 0 , sizeof(path));
    memset(d,0,sizeof(d));
    for(int i = n; i>= 1; i--){ 
        for(int j = 0; j <= t-1; j++){
            d[i][j] = d[i+1][j];
            path[i][j] = path[i+1][j];
            if(j >= w[i]){
                if(d[i][j]<d[i+1][j-w[i]]+1)
                {
                    d[i][j]=d[i+1][j-w[i]]+1;
                    path[i][j]=path[i+1][j-w[i]]+w[i];
                }
                else if(d[i][j]==d[i+1][j-w[i]]+1)
                {
                    path[i][j]=max(path[i][j],path[i+1][j-w[i]]+w[i]);
                }
            }
        }
    }
    
    printf("Case %d: %d %d\n", cnt ,d[1][t-1]+1, path[1][t-1]+678); 
    
    }
    return 0;
}

其中，第一二种方法耗时小，第三种耗时大。