#include <iostream>//使用优递推的动态规划题,此题可以化成单数列的递推,也可以化为 0 1 数列
using namespace std;//递推关系:如果 dp[i]>=0 (意味着此处已经可以用之前的硬币组成) 那么dp[i]赋值为0,也就是只需要 0 个当前硬币即可组成
//                     如果 dp[i]==-1 (意味着此处不能用之前的硬币组成) 那么dp[i]就赋值为 dp[i-当前硬币的币值]+1 (但需提前判断dp[i-当前硬币的币值]是否存在并且小于当前硬币的总数)
//                     被记录为 非负的位置,永远不会再等于 -1(初始值)  最终不是 -1 的位置就是可以达成的价格

int N = 0, M = 0;//硬币种数 最大价格
int A[1001], C[1001];//硬币币值 硬币数量
int dp[100001];//记录在当前硬币情况下,为了组成价格[],使用此硬币的最少数量,如果不可能则为 -1
int ans;//记录最终输出的结果

int main()
{
	while (true)
	{
		scanf("%d%d", &N, &M);
		if (!N)
		{
			return 0;
		}
		memset(dp, -1, sizeof(dp));//可以将数组赋值为 -1

		for (int i = 0; i < N; i++)
		{
			scanf("%d", &A[i]);
		}
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &C[i]);
		}

		dp[0] = 0;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j <= M; j++)
			{
				if (dp[j] >= 0)
				{
					dp[j] = 0;
				}
				else if(j >= A[i])
				{
					if (dp[j - A[i]] < C[i])
					{
						if (dp[j - A[i]] >= 0)
						{
							dp[j] = dp[j - A[i]] + 1;
						}
					}
				}
			}
		}

		ans = 0;
		for (int i = 1; i <= M; i++)
		{
			if (dp[i] >= 0)
			{
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;//记得加 return 0; 否则VS2017虽然能够编译,但是在OJ上会超时
}

• Re:贴个标准DP代码 内附详细讲解 (1404) a280920481 2018-10-16 23:22:50
• Re:贴个标准DP代码 内附详细讲解 (12) a280920481 2018-10-16 23:23:40
• 要是超时了可以看看这篇 (1404) a280920481 2018-10-16 23:24:00