2134混合背包 简单动态规划(简单易理解版)

解题思路:就是01背包,多重背包,和无限背包合起来,加个判断条件就好了

注意事项:  1.这里使用普通的dp数组,方便初学者理解. 加上这道题普通的dp数组也可以过,就不再优化了

                2.N物品数量有大于三十的情况,题目有误.所以数组要开大点.

参考代码:

#include<bits/stdc++.h>

using namespace std;

int M,N;

int dp[305][2005];

int i,j,k;

int W[305],C[305],P[305];

int main()
{
	scanf("%d %d",&M,&N);
	getchar();

	for(i = 1; i <= N; i++)
	{
		scanf("%d %d %d",&W[i],&C[i],&P[i]);
		getchar();
	}
	
	for(i = 1; i <= N; i++)
	{
	  	for(j = 1; j <= M; j++)
		{
			if(P[i] == 0)//无限背包
			{
				for(k = 0;(j - k*W[i]) >= 0 ; k++)
				{
					dp[i][j] = max(dp[i][j],dp[i-1][j-k*W[i]]+k*C[i]);
				}
			}
			else//01背包 与 多重背包
			{
	   			for(k = 0; k <= P[i] && (j- k*W[i] >= 0); k++)
				{
					dp[i][j] = max(dp[i-1][j- k*W[i]] + k*C[i],dp[i][j]);
				}
			}
	  	}
	}

	cout << dp[N][M];

	return 0;
}