有n个重量和价值分别为wi,vi的物品。从这些物体中挑选出总重量不超过W的物品,求所有方案中价值总和的最大值。
1 朴素方法
** 将每个物体是否放入背包进行搜索试一试 **
int n, W;
int w[MAX_N], v[MAX_N];
//从第i个物品选择总重小于j的部分
int res(int i, int j) {
int res;
if (i == n) {
//已经没有剩余物品了
res = 0;
} else if (j < w[i]) {
//无法挑选这个物品
res = rec(i + 1, j);
} else {
//挑选和不挑选的情况都试一下,不选这个选下一个或许v更大
res = max(rec(i + 1, j), rec(i + 1, j + 1) + v[i]);
}
return res;
}
void solve() {
printf("%d\n", rec(0, W));
}
** 这种方法的搜索深度是n,每一层需要两次分支,最坏需要O($2^n$)的时间。**
2 使用数组记录结果,省略第二次以后的重复计算时间。
int dp[MAX_N + 1][MAX_N + 1]; //记忆化数组
int rec(int i, int j) {
if (dp[i][j] >= 0) {
//已经计算过的话直接使用之前的结果
return dp[i][j];
}
int res;
if (i == n) {
res = 0;
} else if (j <w[j]) {
res = rec(i + 1, k);
} else {
res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
}
//将结果记入dp数组
return dp[i][j] = res;
}
void solve() {
//用-1表示尚未计算过,初始化整个数组
memset(dp, -1, sizeof(dp));
printf("%d\n", rec(0, w));
}
** 根据定义,有如下的递推式 **
dp[n][j] = 0;
dp[i][j] = dp[i + 1][j] (j < w[i])
else = max(dp[i + 1][j], dp[i + 1][j -w[i]]+v[i])
int dp[MAX_N + 1][MAX_N + 1]; //记忆化数组
void solve() {
for (int i = n - 1; i >= 0; i --) {
for (int j = 0; i < j<= W; ++j) {
if (j < w[i]) {
dp[i][j] = dp[i + 1][j];
} else {
dp [i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
}
}
}
printf("%d\n", dp[0][W]);
}
** 上面所述的dp中i的循环是逆向进行的,如果按照下面定义递推,则可以正向进行i的循环 **
dp[i + 1][j] :=从0到i这i+1个物品中选出来总重量不超过j的物品时总价值的最大值
dp [0][j] = 0;
dp[i + 1][j] = dp [i][j] (j < w[i])
else = max(dp[i][j], dp[i][j - w[i]] + v[i])
void solve() {
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < w; ++j)
{
if (j < w[i])
{
dp[i + 1][j] = dp[i][j];
} else {
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}
printf("%d\n", dp[n][w]);
}
** 还可以把状态转移想象成从"前i个物品中选取总重不超过j时的状态"向"前i + 1个物品中选取总重不超过j"和"前i+1个物品中选取总重不超过j+w[i]时的状态"的转移,于是可以实现下面形式 **
void solve() {
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < w; ++j)
{
dp[i + 1][j] = max(dp[i+1][j], dp[i][j]);
if (j + w[i] <= W)
{
dp[i + 1]{j + w[i] = max(dp[i + 1][j + w[i], dp[i][j] + v [i]);
}
}
}
printf("%d\n", dp[n][w]);
}
网友评论