完全背包 poj 2063 Investment

#include <iostream>#include <cstdio>#include <cstring>using namespace std;int c[20];int I[20];int dp[50050];int main(){    int rest,capital,t,year,bnum;    scanf("%d",&t);    while(t--)    {        rest=0;        capital=0;        year=0;        bnum=0;        scanf("%d%d",&capital,&year);        scanf("%d",&bnum);        for(int i=0;i<bnum;i++)        {            scanf("%d%d",&c[i],&I[i]);            c[i]/=1000;        }        for(int i=0;i<year;i++)        {            memset(dp,0,sizeof(dp));            rest=capital%1000;            capital=capital/1000;            for(int j=0;j<bnum;j++)            {                for(int k=c[j];k<=capital;k++)                {                    dp[k]=max(dp[k],dp[k-c[j]]+I[j]);                }            }            //cout<<dp[capital]<<' '<<rest<<endl;            //capital=rest+dp[capital]+capital*1000;            int sum=dp[capital];            capital=rest+sum+capital*1000;            //cout<<capital<<endl;        }        cout<<capital<<endl;    }    return 0;}