背包问题

01背包（物品只有一个）

有N件物品和一个容量为V的背包。第i建物品的费用是w[i],价值是v[i]。求解将哪些物品装入背包可使价值总和最大?每种物品只有一件，可以选择放或者不放

• dp[i][v] = max{dp[i - 1][v - k * c[i]] + w[i],dp[i-1][v]}

public class Main {
    public int bag(int w[],int v[],int len, int volume) {
        int bag[] = new int[volume+1];
        for(int i=0;i<=volume;i++){
            bag[i] = 0;
        }
        for(int i=0;i<len;i++){
            for(int j=volume;j>=0;j--){
                int a,b=0;
                a=bag[j];
                if(w[i]<=j){
                    b = bag[j-w[i]]+v[i];
                }
                if(a<b) a=b;
                bag[j] =a;
            }
        }
        System.out.println(bag[volume]);
        return bag[volume];
    }
    
    public static void main(String[] args) {
        Main main = new Main();
        int w[] = new int[]{3,4,5};
        int v[] = new int[]{4,5,6};
        main.bag(w, v, w.length, 10);//11
    }
}

完全背包（物品有重复）

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价格是v[i].求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

• 第一种解法dp[i][v] = max{dp[i-1][v - k * c[i]] + k * w[i] | 0 <= k * c[i]<= v}
• 转化为01背包

public class Main {
    public int bag(int w[],int v[],int len, int volume) {
        int bag[] = new int[volume+1];
        for(int i=0;i<=volume;i++){
            bag[i] = 0;
        }
        for(int i=0;i<len;i++){
                //这里不一样
            for(int j=0;j<=volume;j++){
                int a,b=0;
                a=bag[j];
                if(w[i]<=j){
                    b = bag[j-w[i]]+v[i];
                }
                if(a<b) a=b;
                bag[j] =a;
            }
        }
        System.out.println(bag[volume]);
        return bag[volume];
    }
    
    public static void main(String[] args) {
        Main main = new Main();
        int w[] = new int[]{3,4,5};
        int v[] = new int[]{4,5,6};
        main.bag(w, v, w.length, 10);//13
    }
}

多重背包问题

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件，每件费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

• dp[i][v] = max{dp[i - 1][v - k * c[i]] + w[i] | 0 <=k <= n[i]}

public class Main {
    public int bag(int w[],int v[],int n[] ,int len, int volume) {
        int bag[] = new int[volume+1];
        for(int i=0;i<=volume;i++){
            bag[i] = 0;
        }
        for(int i=0;i<len;i++){
            for(int j=volume;j>=0;j--){
                int max =0;//不一样了
                for(int k=0;k<=n[i];k++){//不一样了
                    int a,b=0;
                    a=bag[j];
                    if((j-k*w[i])>=0){//不一样了
                        b = bag[j-k*w[i]]+k*v[i];//不一样了
                    }
                    if(a<b) a=b;
                    if(a>max) max = a;//不一样了
                }
                bag[j] = max;//不一样了
            }
        }
        System.out.println(bag[volume]);
        return bag[volume];
    }
    
    public static void main(String[] args) {
        Main main = new Main();
        int w[] = new int[]{3,4,5};
        int v[] = new int[]{4,5,6};
        int n[] = new int[]{4,4,4};
        main.bag(w, v, n,w.length, 10);
    }
}