UVA 12563 劲歌金曲（两个最优条件的dp问题）

紫书上的0-1背包例题，但是跟普通的0-1背包还是有些差别。
题意： 在告知的n首歌曲里，要选取一些歌曲 使得 歌曲数量尽量多，其次 唱的时间也要尽量长。
那么我们假定 i与j，和0-1背包类似，i代表前i首歌曲，j代表的是时间，是不是跟0-1背包里的第几个物品和重量类似呢，
那么0-1背包里 dp[i][j]代表的是前i个物品里，总共能承受的最大重量j内存放的最大重量。
那么这道题，dp[i][j]又代表什么呢？
很容易发现，他既要代表 歌曲的数目，又要代表选取歌曲的总长
那么我们就可以用一个结构体来表示

struct Nature 
{int number; //代表选取的歌曲数目int totaltime; //代表选取的歌曲数目加起来的时间长度bool operator < (const Nature & h){return number<h.number || ( number==h.number && totaltime < h.totaltime) ;}//重载小于运算符，用来后面比较（因为首先要看歌曲数量，后面再看时间长度）
};

OK，状态定义好了，那么状态转移方程该如何写呢，通过简单的0-1背包我们很容易就能够推出

dp[i][j] = MAX ( dp[i-1][j], 选取这首歌之后的状态（数目+1 时间+t[i] ） )

然后就是代码了

#include 
#include 
#include 
using namespace std;
struct nature
{int number; //歌曲数int totaltime; //选取的歌曲时间bool operator<(const nature &h)const{return number<h.number || ( number==h.number && totaltime < h.totaltime ) ;}
};
const int ConstNumber = 55;
const int MaxTime = 1e4;
nature dp[ConstNumber][MaxTime];
int main()
{int N; // 代表 样例数cin >> N;int kase = 1;int t[ConstNumber]; //用来储存歌曲的时间while(N--){int num,sumtime;cin>>num>>sumtime;int sum = 0;for(int i=1;i<=num;i++){cin>>t[i];sum += t[i];}sumtime = min( sum , sumtime-1 );  // 如果说 sum <= sumtime-1  那么就一定能放完所有歌曲且还有时间放 劲歌金曲，反之，就不能放完所有歌曲，那么总的播放时间就是sumtime-1 ，要预留出一秒给劲歌金曲。memset(dp,0,sizeof(dp));for( int i = 1; i <= num ; i++ ){for(int j=sumtime ;j>=0;j--){dp[i][j]=dp[i-1][j];if(j>=t[i]){nature temp;temp.number = dp[i-1][j-t[i]].number+1;temp.totaltime = dp[i-1][j-t[i]].totaltime+t[i];if(dp[i][j] < temp)dp[i][j] = temp;}}}cout << "Case " << kase++ << ": " <<dp[num][sumtime].number+1 <<' '<< dp[num][sumtime].totaltime+678<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！