背包问题——哈士奇

#include <bits/stdc++.h>
using namespace std;
int main()
{
   
    int n, x, dp[1005][1005], p[105], m[105];
            //dp[哈士奇数量][拥有的钱]
            // i j
    while(cin>>n>>x)
    {
   
        memset(dp, 0, sizeof(dp));
        for(int i=1;i<=n;i++)
        {
   
            cin>>p[i]>>m[i];
        }
        for(int i=1;i<=n;i++)
        {
   
            for(int j=x;j>0;j--)//代表当前拥有的钱
            {
   
                if(j>=p[i])//如果当前的钱够买第i只哈士奇，有两种选择，买或者不买
                {
   
                    dp[i][j]=max(dp[i-1][j], dp[i-1][j-p[i]]+m[i]);
                                    //不买 买
                }
                else
                {
   
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        cout<<dp[n][x]<<endl;
    }
    return 0;
}
/**************************** 2 100 50 20 60 40 40 —————————————————————————————— 3 100 20 55 20 35 90 95 95 —————————————————————————————— 1 10 20 50 0 ****************************/