尼采般地抒情

尼采般地抒情

尼采般地抒情

音乐盒

站点信息

文章总数目: 313
已运行时间: 1541

问题描述

问题描述

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

物品总数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 &lt; m; i++)
{
    DP0_1KnapsackCaller(N[i], W[i], &amp;w[i][0], &amp;v[i][0]);
}

return 0;

}

动态规划Result

评论区