贪吃的大嘴

解题思路:

此题一看就知道是一个多重背包题，只不过我们要求吃的小蛋糕数量。我们知道多重背包就是可以选物品n个，我们首先把01背包的程序的for循环写出来。然后在考虑多重的for如何写。

我们知道当物品i选择一次后就会选择下个物品了，那我们可以选在原来的基础上嵌入一个for用来表示当前选择了i物品的次数，由此我们dp[k]就等于dp[k - t[i]] + 1和dp[k]相互比较了。dp[k]表示当前我j的美味度时最少需要吃的小蛋糕数量。我们要去他们的最小值所以我们的初始化要尽可能的大，dp[0]=0一个边界值。

参考代码:

#include

#define INF 0x3fffffff

using namespace std;

int t[51];

int coin[51];

int dp[20002] = {0};

 int main(){

    int n;

    int m;

    int i, j, k;

   cin >> m >> n;

   for( i = 1; i<= n; i++ ) {

        cin >> t[i] >> coin[i];

    }

   for( i = 1; i <= m; i++ ) {

        dp[i] = INF;

    }

   dp[0] = 0;

    for( i = 1; i <= n; i++ )

        for( j = 1; j <= coin[i]; j++ )

            for( k = m; k >= t[i]; k-- ) {

                dp[k] = min( dp[k - t[i]] + 1, dp[k] );

            }

   if( dp[m] == INF ) cout << "><" << endl;

   else cout << dp[m] << endl;

   return 0;

}