rnqoj-57-找啊找啊找GF-二维背包 - c++编程基础

简单的二维背包问题。

数组t[j][k]记录时间

数组dp[j][k]记录数量

保证数量的前提下，时间最少

#include  
#include  
#include  
#include  
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]




ns)  
                {  
                    ns=dp[i][j];  
                    ts=t[i][j];  
                }  
                else if(dp[i][j]==ns)  
                {  
                    ts=min(ts,t[i][j]);  
                }  
            }  
        }  
        cout<