01背包问题 poj 3624-蒲公英云

01背包问题 poj 3624

理解01背包问题，首先要从二维数组的开始。二维数组的理解之后，优化成为一维，就是轻而易举的事了。
01背包动态规划的转移公式：
当考虑第i件物品的时候，背包能装得下的话，
dp(i,j)=max{dp(i-1,j),dp(i-1,j-w[i])+v[i]}
如果背包装不下第i件物品的话
dp(i,j)=dp(i-1,j)

package p3624;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
    static int r;
    static int c;
    static int[] w;
    static int[] v;
    static int mv[][];// max value
    public static void main(String[] args) throws FileNotFoundException {
        File file = new File("c:\\data.txt");
        Scanner cin = new Scanner(file);
        // Scanner cin = new Scanner(System.in);
        r = cin.nextInt();
        c = cin.nextInt();
        mv = new int[r + 1][c + 1];
        w = new int[r + 1];
        v = new int[r + 1];
        for (int i = 1; i <= r; i++) {
            w[i] = cin.nextInt();
            v[i] = cin.nextInt();
        }
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                boolean f = j >= w[i];
                if (f) {// 装得下
                    int a = mv[i - 1][j];// 不装i物品
                    int b = mv[i - 1][j - w[i]] + v[i];// 装i物品
                    mv[i][j] = max(a, b);
                } else {
                    mv[i][j] = mv[i - 1][j];
                }
            }
        }
        System.out.println(mv[r][c]);
    }
    static int max(int i, int j) {
        return i > j ? i : j;
    }
}

二维数组的形式，用mv的二维数组记录mv(i,j)：当扫描到第i件物品，占用j容量的时候，所能的到的最大value。
_______________________________________________________粉葛先___________________________________________________
对于二维数组，除了处理第i行的时候用到i-1行的数据，其他之前的数据都不再有用了。而且用到i-1行的数据也只是（1，j），j之后的数据是用不到的。
所以，可以优化为一维。
但是注意，优化成一维的时候，不能再像二维那样遍历背包承重的时候从1开始遍历，因为一维数组如果从1开始遍历，那么前面的数据就被覆盖掉了。所以要从c开始往前遍历。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Main {
    static int r;
    static int c;
    static int[] w;
    static int[] v;
    static int mv[];// max value
    public static void main(String[] args) throws FileNotFoundException {
        //File f = new File("c:\\data.txt");
        //Scanner cin = new Scanner(f);
         Scanner cin = new Scanner(System.in);
        r = cin.nextInt();
        c = cin.nextInt();
        mv = new int[c + 1];
        w = new int[r + 1];
        v = new int[r + 1];
        for (int i = 1; i <= r; i++) {
            w[i] = cin.nextInt();
            v[i] = cin.nextInt();
        }
        for (int i = 1; i <= r; i++) {// 遍历所有物品
            for (int j = c; j >= w[i]; j--) {//遍历背包承重
                int a = mv[j - w[i]];//
                int d = mv[j];//不加i这件物品的最大价值
                int b = a + v[i];//加上i这件物品的最大价值
                mv[j] = max(d, b);//取二者的最大价值
            }
        }
        System.out.println(mv[c]);
    }
    static int max(int i, int j) {
        return i > j ? i : j;
    }
}