背包问题 多重背包2(爱思创)

这篇文章还是是为了帮助一些

像我这样的菜鸟

找到简单的题解

注: 本题只是多重背包1的数据加大版

4 5
1 2 3
2 4 1
3 4 3
4 5 2

10

点这里看多重背包1

稍加优化就好了

注释不写了

给位大佬能看懂

#include
using namespace std;
int N,V,dp[2005];//用滚动数组
int main()
{
    cin>>N>>V;
    for(int i = 1;i <= N;++i)
	{
        int v,w,s;
		cin>>v>>w>>s;
        for(int j = 1;j <= s;s -= j,j *= 2)
		{ 
            for(int k = V;k >= j * v;--k)
            {
                if(dp[k] < dp[k - j * v] + j * w)
                {
                    dp[k] = dp[k - j * v] + j * w;
                }
            }
        }
        if(s==true)
        {
            for(int k = V;k >= s * v;--k)
            {
                if(dp[k] < dp[k - s * v] + s * w)
                {
                    dp[k] = dp[k - s * v] + s * w;
                }
            }
        }
    }
    cout< 
AC