AcWing-01背包问题

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]);                   // 优化后
    }