2 3 Computer 3 3 English 20 1 Math 3 2 3 Computer 3 3 English 6 3 Math 6 3
2 Computer Math English 3 Computer English Math
dp问题
#include <iostream>
using namespace std;
#include <string>
#include <stack>
struct Q{
string s;
int d;
int c;
};
struct DPT{
int time;
int pos;
int last;
int score;
};
DPT *dp;
Q *q;
int main()
{
freopen("C:\\in.txt","r",stdin);
int T;
const int INF=0x7fffffff;
cin>>T;
while(T--){
int N;
cin>>N;
q=new Q[N];
dp=new DPT[1<<N];
for(int i=0;i<N;i++){
cin>>q[i].s>>q[i].d>>q[i].c;
}
int end=1<<N;
int recent=0;
int reduce=0;
int past=0;
dp[past].score=0;
dp[past].pos=0;
dp[past].last=0;
dp[past].time=0;
for(int s=1;s<end;s++){
dp[s].score=INF;
for(int i=N-1;i>=0;i--){
recent=1<<i;
if(s&recent){
past=s-recent;
reduce=dp[past].time+q[i].c-q[i].d;
if(reduce<0)reduce=0;
if(reduce+dp[past].score<dp[s].score){
dp[s].score=reduce+dp[past].score;
dp[s].pos=i;
dp[s].last=past;
dp[s].time=dp[past].time+q[i].c;
}
}
}
}
stack<int>path;
recent=end-1;
while(recent){
//cout<<dp[recent].pos;
path.push(dp[recent].pos);
recent=dp[recent].last;
}
cout<<dp[end-1].score<<endl;
while(!path.empty()){
int top=path.top();
cout<<q[top].s<<endl;
path.pop();
}
delete[] q;
delete[] dp;
}
return 0;
}原文：http://blog.csdn.net/starcuan/article/details/18951561