AcWing-01背包问题

AcWing-01背包问题,第1张

AcWing-01背包问题

朴素写法(二维):

f[i][j]定义为前i个物品,重量j下的最优解

(1) 重量不够 j

f[i][j]=f[i-1][j]

(2)重量够

选:f[i][j]=f[i-1][j-w[i]]+v[i]

不选:f[i][j]=f[i-1][j]

public static void main(String[] args) throws Exception
	{
		int n,V;
		n=sc.nextInt();
		V=sc.nextInt();
		for(int i=1;i<=n;i++)
		{
			v[i]=sc.nextInt();
			w[i]=sc.nextInt();
		}
		for(int i=1;i<=n;i++)
			for(int j=0;j<=V;j++)
			{
				f[i][j]=f[i-1][j];
				if(j>=v[i])
				{
					f[i][j]=Math.max(f[i-1][j], f[i-1][j-v[i]]+w[i]);
				}
			}
		out.println(f[n][V]);
		out.close();
	}

优化写法(一维):

一维相当于对二维进行等价变换

 注意:当需要用到i-1层时,此时需要从大到小遍历,反之则是从小到大(y总说的记住)

for(int i = 1; i <= n; i++) 
    for(int j = m; j >= 0; j--)
    {
        if(j < v[i]) 
            f[i][j] = f[i - 1][j];  // 优化前
            f[j] = f[j];            // 优化后,该行自动成立,可省略。
        else    
            f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  // 优化前
            f[j] = max(f[j], f[j - v[i]] + w[i]);                   // 优化后
    }  

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5722152.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表(0条)

保存