背包

Acwing

01背包采药

二维背包费用 宠物小精灵之收服

二维背包+ “至少”问题 潜水员

体积最大时方案数 背包问题求方案数

01背包最大体积具体方案 背包问题求具体方案

01背包固定体积方案数 数字组合（01背包方案数）

完全背包固定体积方案数 买书

完全背包固定体积方案数 货币系统

三重循环多重背包

多重背包拆分成01背包 多重背包问题 II

滑动窗口多重背包 多重背包问题 III

01分组背包 机器分配

力扣

01背包[采药]

import java.util.*;
import java.io.*;
public class Main{
    static int[] f = new int[1010];
    static int[] v = new int[1010];
    static int[] w = new int[1010];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String[] input = scan.nextLine().split(" ");
        int T = Integer.valueOf(input[0]), M = Integer.valueOf(input[1]);
        for (int i = 1; i <= M; i ++){
            w[i] = scan.nextInt();
            v[i] = scan.nextInt();
        }
        for (int i = 1; i <= M; i ++){
            for (int j = T; j >= w[i]; j --){
                f[j] = Math.max(f[j], f[j - w[i]] + v[i]);
            }
        }
        System.out.println(f[T]);
    }
}

1024. 装箱问题

更换顺序的典中典

import java.util.*;
import java.io.*;
public class Main{
    static int[] f = new int[20010];
    static int[] w = new int[20010];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int V = scan.nextInt();
        int n = scan.nextInt();
        for (int i = 1; i <= n; i ++){
            w[i] = scan.nextInt();
        }
        for (int i = 1; i <= n; i ++){
            for (int j = V; j >= w[i]; j --){
                f[j] = Math.max(f[j], f[j - w[i]] + w[i]);
            }
        }
        System.out.println(V - f[V]);
    }
}

宠物小精灵之收服

import java.util.*;
import java.io.*;
public class Main{
    static int[][] f = new int[1010][510];
    static int[] ball = new int[110];
    static int[] damage = new int[110];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int total = scan.nextInt();
        int energy = scan.nextInt();
        int n = scan.nextInt();
        for (int i = 1; i <= n; i ++){
            ball[i] = scan.nextInt();
            damage[i] = scan.nextInt();
        }
        for (int i = 1; i <= n; i ++){
            for (int j = total; j >= ball[i]; j --){
                for (int k = energy - 1; k >= damage[i]; k--){
                    f[j][k] = Math.max(f[j][k], f[j - ball[i]][k - damage[i]] + 1);
                }
            }
        }
        System.out.print(f[total][energy - 1] + " ");
        int resE = 0;
        for (int j = 0; j < energy; j ++)
            if (f[total][j] == f[total][energy - 1]){
                System.out.println(energy - j);
                break;
            }
    }
}

完全背包固定体积求最值322. 零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        //完全背包
        int n = coins.length;
        int[] f = new int[amount + 1];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for (int i = 0; i < n; i ++){
            for (int j = coins[i]; j <= amount; j ++)
                if (f[j - coins[i]] != Integer.MAX_VALUE)
                    f[j] = Math.min(f[j], f[j - coins[i]] + 1);
        }
        if (f[amount] == Integer.MAX_VALUE)return -1;
        else return f[amount];
    }
}

普通完全背包279. 完全平方数

class Solution {
    public int numSquares(int n) {
        //完全背包
        List<Integer> v = new ArrayList<Integer>();
        v.add(0);
        for(int i = 1; i * i <= n; i ++)
            v.add(i * i);
        int m = v.size();
        int[] f= new int[n + 1];
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for (int i = 1; i <= m - 1; i++)
            for (int j = v.get(i); j <= n; j++)
                f[j] = Math.min(f[j], f[j - v.get(i)] + 1);
        return f[n];                
    }
}