简单的二维背包问题。
数组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;
}