本文共 1987 字，大约阅读时间需要 6 分钟。

原题链接：

一：原题内容

3 101 2 4 2 1 12 51 4 2 10 0

84

二：分析理解

一个模板题！！

三：AC代码

#include
   
      #include
    
       using namespace std;int dp[100005];int value[105];int number[105];int n, m;void ZeroOnePack(int value, int weight){	for (int i = m; i >= value; i--)		dp[i] = max(dp[i], dp[i - value] + weight);}void CompletePack(int value, int weight){	for (int i = value; i <= m; i++)		dp[i] = max(dp[i], dp[i - value] + weight);}void MultiplePack(int value, int weight, int number){	if (number*value >= m)	{		CompletePack(value, weight);		return;	}	int k = 1;	while (k <= number)	{		ZeroOnePack(k*value, k*weight);		number -= k;		k *= 2;	}	ZeroOnePack(number*value, number*weight);}int main(){	while (~scanf("%d%d", &n, &m), n + m)	{		memset(dp, 0, sizeof(dp));		for (int i = 0; i < n; i++)			scanf("%d", &value[i]);		for (int i = 0; i < n; i++)			scanf("%d", &number[i]);		for (int i = 0; i < n; i++)			MultiplePack(value[i], value[i], number[i]);		int num = 0;		for (int i = 1; i <= m; i++)			if (dp[i] == i)				num++;		printf("%d\n", num);	}	return 0;}
    
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/51243686 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！