Backpack V 0-1 背包问题

0/1 Knapsack Problem

单次选择+装满可能性总数

Description

Given n items with sizenums[i]which an integer array and all positive numbers. An integertargetdenotes the size of a backpack. Find the number of possible fill the backpack.

Each item may only be used once

Example

Given candidate items[1,2,3,3,7]and target7,

A solution set is: 
[7]
[1, 3, 3]

return2

Solution & Analysis

一维DP,0-1 背包问题

注意这里因为是 0 -1背包问题,与Backpack IV相比,就要将内层循环遍历方向逆序,因为需要确保每个元素最多只能用一次。

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public int backPackV(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = target; j >= nums[i - 1]; j--) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }

        return dp[target];
    }
}

关于(内层)循环的遍历顺序,九章有一个问答解释的很好:

https://www.jiuzhang.com/qa/2863/

>

首先2维的状态是一个完整的状态,能表示状态详细的信息,为什么会有变成1维,实际上是在2维的前提下,优化了空间复杂度。
本质来说,f[i][*]只和f[i - 1][*]有关,这给我了我们优化空间复杂度的契机,所有可以优化到一维。(又因为物品是取一个还是可以无限取,那么在一维状态的时候就要仔细考虑如何枚举状态的顺序)。

接下来是关于状态顺序的枚举。就是顺序是怎么思考的。
动态规划问题枚举的顺序只有一个原则如果b状态的计算依赖于a状态,那么a状态必须在b状态之前被枚举和计算

>

results matching ""

    No results matching ""