动态规划之背包问题

0-1背包

有一个容量为 C的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品最多只能装一个。要求用这个背包装下价值尽可能多的物品

定义w[i-1],v[i-1]分别 第i个物品的重量和价值，dp[i][j]为容量为j的背包装第i件物品的最大价值，可以得出如下递推公式：

• dp[0][j]和dp[i][0]=0
• 当w[i-1]>j时,dp[i][j]=dp[i-1][j],（当装第i个物品时，物品的重量大于背包重量j）
• 当w[i]<=j时，dp[i][j]=max(dp[i-1][j], v[i-1]+dp[i-1][j-w[i-1]])

java代码

package com.ds.dp;

public class Knapsack {
    /**
     * 
     * @param C 背包的容量
     * @param v 物品的价格表
     * @param w 物品的重量表
     * @return
     */
    public static int knapsack01(int C, int[] v, int[] w) {
        int dp[][] = new int[v.length + 1][C + 1];
        for (int i = 1; i <= v.length; i++) {
            for (int j = 1; j <= C; j++) {

                if (w[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]]);
                }

            }
        }
        return dp[v.length][C];

    }

    public static void testKnapsack01() {
        int[] v = {15, 30, 25};
        int[] w = {1, 4, 3};
        System.out.println(knapsack01(4, v, w));
    }

    public static void main(String[] args) {
        testKnapsack01();
    }
}

代码地址

https://github.com/spraysss/data-structure/blob/master/src/main/java/com/ds/dp/Knapsack.java