看正月点灯笼老师的笔记

看正月点灯笼老师的笔记—01背包

视频地址：https://www.bilibili.com/video/BV1U5411s7d7?t=1942

一i，题目

给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

其中，对于 01 背包来说，每件物品都只能选择一次。

二，错误的思考

之前曾经想到，可以求出每件物品的单价（即价格/重量），在根据单价进行排序和选择。

后来写出来答案不对，才发现这样做有个问题，即这里的物品并不是真的称斤买的。

例如，你背包空间剩下 4，此时还剩下两件物品没有决策，一个 w: 1，v: 5，一个 w: 4，v: 6

这时，两件物品无法同时选择，答案很明显应该选第二个，但是在我对这种方法下，会选择第一个，因为第一个单价更高。

这种方法会出错的原因在于：带了最后，尽管你单价更高，但你的空间利用的不够。

这种或许可以特殊判断一下，不过我想不出来解决办法：

以下是错误的代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 100
struct Node
{
    int w, v;
    double av;
}kp[N];
bool vis[N];   // 标记这个物品是否偷过
bool cmp(Node a, Node b)
{
    return a.av - b.av < 1e-6;
}
int W, n;  // W 背包的最大空间  ，n 代表物品个数
int V;  // 最大价值
void knapsack_01()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (kp[j].w < W&&vis[j] == 0)
            {
                vis[j] = 1;
                W -= kp[j].w;
                V += kp[j].v;
            }
        }
    }
}
int main(void)
{
    scanf("%d%d", &n, &W);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &kp[i].w, &kp[i].v);
        kp[i].av = (double)kp[i].v / (double(kp[i].w));
    }
    sort(kp + 1, kp + n + 1, cmp);
    knapsack_01();

    printf("%d
", V);
    
    system("pause");
    return 0;
}
/*测试数据：
5 20
2 3
3 4
4 5
5 8
9 10
*/

View Code

三，动态规划

这题这种 01背包应该还是比较一般性的动态规划问题，即可以由前面的状态堆出后面的状态。

可以从函数关系和函数出口来概括这种问题。( ｡ớ ₃ờ)ھ

其中 B(k,w) 代表：如果背包共计装 w 重的物品，那么在前 k 个物品都决策好了的情况下，背包能装的物品的最大的价值。

四，代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define MAX(x,y) (((x)>(y))?(x):(y))
#define N 100
int B[N][N];
int w[N];
int v[N];
int W, n;  // W 背包的最大空间  ，n 代表物品个数
int dp(int k, int W)
{
    if (k == 0)
        return 0;
    if (W == 0)
        return 0;
    if (w[k] > W)
        return dp(k - 1, W);
    return MAX(dp(k - 1, W - w[k]) + v[k], dp(k - 1, W));
}
void knapsack_01()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (w[i] > j)              
                B[i][j] = B[i - 1][j];
            else
            {
                int v1 = B[i - 1][j - w[i]] + v[i];
                int v2 = B[i - 1][j];
                B[i][j] = MAX(v1, v2);
            }
        }
    }
}
int main(void)
{
    scanf("%d%d", &n, &W);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &w[i], &v[i]);
    }

    knapsack_01();

    printf("
W == > ");
    for (int i = 0; i <= W; i++ )
    {
        printf("%3d", i);
    }puts("");
    for (int i = 0; i <= n; i++)
    {
        printf("第%d件: ",i);
        for (int j = 0; j <= W; j++)
        {
            printf("%3d", B[i][j]);
        }puts("");
    }
    printf("当背包可装重 %d 的物品时，最多可偷 %d 价值的物品
", W, dp(n, W));

    system("pause");
    return 0;
}
/*测试数据：
5 20
2 3
3 4
4 5
5 8
9 10
*/

View Code

========== ========= ======== ======= ====== ===== ==== === == =

清平乐 · 六盘山　　毛润之

天高云淡，望断南飞雁。

不到长城非好汉，屈指行程二万。

六盘山上高峰，红旗漫卷西风。

今日长缨在手，
何时缚住苍龙？