[AcWing] 423. 采药（C++实现）01背包问题

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

读题：

采每一株草药时间会减少 ===》 体积
每一株草药有自身的价值 ===》 价值

且每一株草药只有选或不选两种情况

即：

时间 ===》 体积
价值 ===》 价值

思路：

将空间优化为二维：滚动数组
优化方式与[AcWing] 2. 01背包问题（C++实现）0-1背包问题模板题相同，在此不再赘述。

---------------------------------------------------解法---------------------------------------------------

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static int[] v = new int[N]; // 体积（时间）
    static int[] w = new int[N]; // 价值
    static int[] f = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        int m = Integer.parseInt(s[0]); // 总体积
        int n = Integer.parseInt(s[1]); // 物品数量
        for(int i = 1;i <= n;i++){
            s = reader.readLine().split(" ");
            v[i] = Integer.parseInt(s[0]);
            w[i] = Integer.parseInt(s[1]);
        }

        for(int i = 1;i <= n;i++)
            for(int j = m;j >= v[i];j--)
                f[j] = Math.max(f[j],f[j-v[i]]+w[i]);

        System.out.println(f[m]);
    }
}

可能存在的问题

• [AcWing] 2. 01背包问题（C++实现）0-1背包问题模板题

• 动态规划
• 01背包问题

01背包模型，可以发展为不同的01背包题目

01背包模型的特征：
1. 可以将一个属性看成 价值；
2. 可以将一个属性看作 背包体积；
3. 每种物品只有选或不选两种情况，不能重复选。