ACM 基础：贪婪的 Knapsack 问题 knapsack- I. Knapsack 问题
1.描述
小偷抢劫商店，发现n件物品，物品i价值 v i v_i vi美元，重量为 w i w_i wi磅，小偷在背包中最多只能携带W磅重量，但他想尽可能多地携带贵重物品。他应该带哪些物品？
问题符号：
-
n：物品的个数 -
i：物品的序号 - v i v_i vi：某物品的价值value
- w i w_i wi：某物品的重量weight
-
W：背包的最大承重量
解法符号：
-
x
i
x_i
xi：表示该物品装入背包多少。在0-1背包问题中，
0（不拿）或1（拿走整件）；在分数背包问题中，是个浮点数 [ 0.0 , 1.0 ] [0.0, 1.0] [0.0,1.0]，0.0（不拿）或0.x（拿走部分）或1.0（拿走整件）
解法：
在满足
∑
1
≤
i
≤
n
w
i
∗
x
i
≤
W
\displaystyle \sum_{1\leq i\leq n}w_i*x_i\leq W
1≤i≤n∑wi∗xi≤W的条件下，使
∑
1
≤
i
≤
n
v
i
∗
x
i
\displaystyle \sum_{1\leq i\leq n}v_i*x_i
1≤i≤n∑vi∗xi最大。
2.难度划分
依据 x i x_i xi是分数还是01，命名：
- 简单：分数背包问题(Fractional knapsack)
- 难：0-1背包问题(0-1 knapsack)