P1013 （C++代码）简单的01背包的变形（循环 + 动态规划）

解题思路:

注意事项:

参考代码:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int rmb[1010];//消耗1
int rp[1010];//消耗2
int t[1010];
int f[101][101];//钱为i，人品为j时泡最多mm的数量
int mint[101][101];//钱为i，人品为j时泡最多mm的最少时间

int main()
{
    int n,i,m=0,r=0;//m->money,r->rp
    int v1,v2;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d%d%d",&rmb[i],&rp[i],&t[i]);
    scanf("%d%d",&m,&r);

    for(i=1;i<=n;++i)
    {
        for(v1=m;v1>=0;--v1)
        {
            for(v2=r;v2>=0;--v2)
            {
                if(v1>=rmb[i]&&v2>=rp[i])
                {
                    if(f[v1][v2]<f[v1-rmb[i]][v2-rp[i]]+1)//先找个数多的
                    {
                        f[v1][v2]=f[v1-rmb[i]][v2-rp[i]]+1;
                        mint[v1][v2]=mint[v1-rmb[i]][v2-rp[i]]+t[i];
                    }
                    else if(f[v1][v2]==f[v1-rmb[i]][v2-rp[i]]+1)//个数相同取时间最小
                    {
                        mint[v1][v2]=min(mint[v1][v2],mint[v1-rmb[i]][v2-rp[i]]+t[i]);
                    }
                }
            }

        }
    }
    printf("%d",mint[m][r]);
    return 0;
}