代码随想录day42

01背包

n种物品每种只有一个

01背包

有 N件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i件物品的体积是 vi价值是 wi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。

输入格式
第一行两个整数NV用空格隔开分别表示物品数量和背包容积。

接下来有 N行每行两个整数 vi,wi用空格隔开分别表示第 i件物品的体积和价值。

输出格式
输出一个整数表示最大价值。

数据范围
0<N,V≤1000

0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8

import java.util.*;
public class Main{
    public static void main(String[] args){
        // System.out.println("====");
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int V = cin.nextInt();
        int[] weight = new int[N];
        int[] value = new int[N];
        for(int i= 0;i < N;i++){
            weight[i] = cin.nextInt();
            value[i] = cin.nextInt();
        }
        cin.close();
        // dp数组的含义:dp[i][j]表示遍历到第i个位置体积为j的最大价值
        // 递归公式 dp[i][j] = max(dp[i-1][j],dp[i-1][j - weight[i]]+value[i]);
         int[][] dp = new int[N][V + 1];
        for(int i = 0;i <= V;i++){
            if(i < weight[0]){
                dp[0][i] = 0;
            }else{
                dp[0][i] = value[0];
            }
        }
        for(int j =0;j < N;j++){
            dp[j][0] = 0;
        }
       
        for(int i = 1;i < N;i++){
            for(int j = 1;j <= V;j++){
                if(j-weight[i]>=0){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[N-1][V]);
    }
}

思想

优化的前提二维数组dp[i][j]的值时从左上角和正上方得到的那么我们转换成一维数组的时候我们如果从左向右遍历的话我们就不能得到左上角的值了因为它已经被更新完了

import java.util.*;
public class Main{
    public static void main(String[] args){
        // System.out.println("====");
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int V = cin.nextInt();
        int[] weight = new int[N];
        int[] value = new int[N];
        for(int i= 0;i < N;i++){
            weight[i] = cin.nextInt();
            value[i] = cin.nextInt();
        }
        cin.close();
        
        // 一维滚动数组 dp[j] 表示最大体积j的最大价值
        int[] dp = new int[V + 1];
        dp[0] = 0;
        for(int i = 0;i < N;i++){
            for(int j = V;j >=weight[i];j--){
                dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
                // System.out.println(dp[j]+"---------"+j);
            }
                // System.out.println(Arrays.toString(dp));
            
        }
        System.out.println(dp[V]);
    }
}

完全背包

n种物品每种物品有无限个

多重背包

n种物品每种物品的个数各不相同

递归超时

class Solution {
    boolean flag ;
    public boolean canPartition(int[] nums) {
        // 其实这就是0/1背包判断其是否
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        flag = false;
        dfs(nums,0,0,sum);
        return flag;
       

    }
    public void dfs(int[] nums,int index,int count,int sum){
        if(index >= nums.length){
            return;
        }
        if(2 * count == sum){
            System.out.println(count);
            flag = true;
            return;
        }
        for(int i = index;i < nums.length;i++){
            dfs(nums,i + 1,count+nums[i],sum);
            dfs(nums,i + 1,count,sum);
        }
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        // 01背包存在问题
        // dp[i] = dp[i] | dp[i-nums[j]]
        // dp[j] 表示元素和j是否存在

        int sum = 0;
        for(int num:nums){
            sum += num;
        } 
        if(sum % 2 == 1) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        

        for(int i = 0;i < nums.length;i++){
            for(int j = target;j >= nums[i];j--){
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];

    }
}