尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 298
已运行时间: 991
目录
  1. 问题描述
    1. 问题描述
    2. 问题的判定性说法
    3. 问题的形式化定义
  2. 问题思路
    1. 动态规划思路
    2. 递归思路
  3. 代码实现
    1. 动态规划Code
    2. 动态规划 Result

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 298
已运行时间: 991

问题描述

问题描述

给定一组已知重量和价值的物品和一个容量已知的背包,求解在不超过背包容量情况下,选用那些物品放入背包,使得所选用的所有物品价值最大化。

物品总数N

4

背包容量M

8

每个物品重量wi

{5, 4, 3, 2}

每个物品价值vi

{15, 10, 6, 2}

问题的判定性说法

问题的形式化定义

问题思路

动态规划思路

动态规划解决该问题,类似于莱文斯坦距离的解法类似。利用CAAIS数据来说明这个问题的解决思想。

动态规划DP方程构造

PS:V[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值

(整张表格是从上往下,从左往右地填)

举例说明表格中的数值填法,倒数第二行倒数第四列的16 4的填法:

  • 首先不满足DP方程的第一种和第二种情况
  • 所以代入取最大值max函数
    • V(i-1,j):不选本物品(3,6),还是用之前的值,继承上面的第一个物品和第二个物品,DP值为15 U
    • V(i-1,j)+vi:用该容量(7)-所选物品的重量为4,然后再查容量为4的时候DP值为10,然后求出该情况DP是,10加上该物品的价值,所以该情况下的DP值为16,右上标为4(CAAIS),值来源于前面容量为4的情况。

格子如上方式填就好了!

递归思路

第二节课将递归的时候,也讲了这个问题的递归思路。不过复杂度记得是指数级的,暂时不写了~~

代码实现

动态规划Code

#include <iostream>

#include <vector>
using namespace std;
namespace NS_DP0_1Knapsack {
int DP0_1Knapsack(int n, int W, int *w, int *v);
void Output(int n, int W, int *w, int *v, int OptV);
static vector<vector<int>> V;
static vector<int> x;
void DP0_1KnapsackCaller(int n, int W, int *w, int *v)
{
V.clear();
V.resize(n + 1, vector<int>(W + 1, 0));
x.resize(n + 1);
int OptV = DP0_1Knapsack(n, W, w, v);
Output(n, W, w, v, OptV);
}
int DP0_1Knapsack(int n, int W, int *w, int *v)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= W; j++)
if (j < w[i - 1])
V[i][j] = V[i - 1][j];
else if (V[i - 1][j] >=
V[i - 1]j - w[i - 1]] + v[i - 1])
V[i][j] = V[i - 1][j];
else
V[i][j] = V[i - 1]j - w[i - 1]] + v[i - 1];
int j = W;
for (int i = n; i > 0; i--)
if (V[i][j] == V[i - 1][j])
x[i] = 0;
else
{ x[i] = 1; j -= w[i - 1]; }
return V[n][w];
}
void Output(int n, int W, int *w, int *v, int OptV)
{
//inputs
printf("DP to solve 0-1 knapsack:\n");
printf("%d items with knapsack capacity %d.\n", n , W);
printf("%-6s: ", "Weight");
for (int i = 0; i < n; i++)
printf("%3d", w[i]);
printf("\n");
printf("%-6s: ", "Value");
for (int i = 0; i < n; i++)
printf("%3d", v[i]);
printf("\n");
//the value matrix
printf("\nThe value matrix:\n");
printf(" ");
for (int j = 0; j <= W; j++)
printf("%3d", j);
printf("\n");
for (int i = 0; i <= n; i++)
{
printf("%2d", i);
for (int j = 0; j <= W; j++)
printf("%3d", V[i][j]);
printf("\n");
}
//solution
printf("\nThe optimal value: %d\n", OptV);
printf("The optimal solution:\n");
for (int i = 1; i <= n; i++)
printf("%2d", x[i]);
printf("\n\n");
}
} //namespace NS_DP0_1Knapsack
using namespace NS_DP0_1Knapsack;
int main()
{
// 物品个数
vector<int> N = { 4, 10};
// 背包容量
vector<int> W = { 8, 100};
// 各物品重量
vector<vector<int>> w = {
{ 5, 4, 3, 2 },
{ 4, 3, 7, 2, 9, 3, 1, 7, 2, 5 }
};
// 各物品价值
vector<vector<int>> v = {
{ 15, 10, 6, 2 },
{ 15, 10, 6, 2, 23, 12, 33, 7, 22, 10 }
};

    int m = N.size();
    for (int i = 0; i < m; i++)
    {
        DP0_1KnapsackCaller(N[i], W[i], &w[i][0], &v[i][0]);
    }

    return 0;

}

动态规划 Result

评论区

Twikoo giscus