简单的二维背包问题。
数组t[j][k]记录时间
数组dp[j][k]记录数量
保证数量的前提下，时间最少
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 99999999
int dp[101][101];
int t[101][101];
int main()
{int a,b,c,i,j,k,n;while(~scanf("%d",&n)){scanf("%d%d%d",&a,&b,&c);for(j=0;j<101;j++){for(k=0;k<101;k++)t[j][k]=INF;}dp[0][0]=0;t[0][0]=0;dp[a][b]=1;t[a][b]=c;for(i=2;i<=n;i++){scanf("%d%d%d",&a,&b,&c);for(j=100;j>=a;j--){for(k=100;k>=b;k--){if(dp[j][k]<dp[j-a][k-b]+1){dp[j][k]=dp[j-a][k-b]+1;t[j][k]=t[j-a][k-b]+c;}if(dp[j][k]==dp[j-a][k-b]+1){t[j][k]=min(t[j-a][k-b]+c,t[j][k]);}}}}scanf("%d%d",&a,&b);int ts,ns;ns=0;ts=99999;for(i=0;i<=a;i++){for(j=0;j<=b;j++){if(dp[i][j]>ns){ns=dp[i][j];ts=t[i][j];}else if(dp[i][j]==ns){ts=min(ts,t[i][j]);}}}cout<<ts<<endl;}return 0;
}