背包问题(学习后总结)

1.定义:

• 一个背包里面放n样东西,每样东西有价值和重量或体积,求出最优秀的放置方法。

Q1:

对于给定的背包体积V;

选择若干个物品,使得总体积不超过V的前提下总价值最大->求这个价值。

Example:

体积:8 5 5

价值:1 1 1

Wrong Answer:

①直接贪心体积小的X

②直接贪心价值大的X

③直接贪心性价比高的X

Example:

直接贪性价比:

体积:8,5,5;

价值:16,9,9;

选5,5的价值>选8的价值。

Right Answer:

假设你已经知道了前i-1种物品在对应体积下可以获得的最大价值,那么对于第i种物品要考虑->体积V&&价值Value.

分类1:

不带某物品:

dp[i(物品)][j(体积)]=dp[i-1][j];

分类2:

• 带上某物品dp[i][j]=dp[i-1][j-V]+Value;

合并->状态转移方程:

• dp[i][j]=max(dp[i-1][j],dp[i-1][j-V]+Value);

T1: P1048 采药

Solution 1:

二维数组(物品&时间限制)

当前物品限制下&当前时间限制下保证最大价值

状态转移方程:

• 1.没时间采: dp[i][t]=dp[i-1][j];

• 2.有时间采,则比较价值:

dp[i][j]=max(dp[i-1][j],dp[i-1][j-ti]+v);

Solution 2:

一维数组

• 其实,第j位的答案只和第j-t位的答案有关系,for循环从后往前写.

• 状态转移方程: dp[j]=max(dp[j],dp[j-t]+v);

T2: P1616 疯狂的采药

Example:

time:3 value:5

0 1 2 3 4 5 6 7 8 9 10

0 0 0 5 5 5 10 10 10 15 15

Solution:

动态转移方程:

• 二维: dp[i][j]=max(dp[i-1][t],dp[i][j-t]+v);

• 一维: dp[j]=max(dp[j],dp[j-t]+v);

Attention:

• 本题与正常的采药唯一区别在于草药量无限,所以说在二维中没有i-1.

Compare:

• 01背包 max(dp[i-1][j],dp[i-1][j-t]+v);

• 无限背包 max(dp[i-1][t],dp[i][j-t]+v);

T3:1507 NASA的食物计划

Solution:

二维数组(体积,重量)

动态转移方程:

• f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+c[i]);

T4: P1060 开心的金明

• 本题是01背包的一个小改动,非常简单

Solution:

动态转移方程:

• dp[j]=max(dp[j],dp[j-money[i]]+im[i]);

T5:P1049 装箱问题

• 本题是一个存在性问题,不再是最值问题

Example:

V:3&5;

1->true;0->false;

0 1 2 3 4 5 6 7 8 9 10

1 0 0 1 0 1 0 0 1 0 0

Solution:

• 假如不用:让前一个得到true;

• 假如要用:可以什么都不选;

• 动态转移方程:dp[j]=dp[j]||dp[j-v];

p.s.所有例题均是洛谷的题目(上课讲的)。这是本蒟蒻第一次发讨论，有不足的地方麻烦dalao们指出

码字不易，求您高抬贵手，给个赞再走吧