【算法训练-初级篇】2.动态规划（DP）1

1.背包问题:
有n个重量和价值分别为w1， v1的物品，从这些物品中挑选出总重量不超过w的物品， 求所有挑选方案中价值总和的最大值。
（限制条件：1《n《100；1《wi，vi《 100； 1《w《10000）

方法一：（时间复杂度0（2^n））

#include <stdio.h>

#define MAX_N 100

int n = 0;
int w = 0;
int ww[MAX_N];
int v[MAX_N];

int rec(int i, int j)
{
    int res;

    if (i == n)
    {
        res = 0; /*没有剩余的物品*/
    }
    else if (j < ww[i])
    {
        res = rec(i + 1, j); /*无法挑选这个物品*/
    }
    else /*挑选和不挑选的情况都尝试*/
    {
        res = max(rec(i +1, j), rec(i + 1, j - ww[i]) + v[i]);
    }

    return res;
}

int max(int x, int y)
{
    return (x > y ? x : y);
}

void solve()
{
    printf("能取得最大价值为：%d\n", rec(0, w));
}

int main()
{
    int i = 0;

    printf("请输入物品数量：\n");
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        printf("输入第%d个物品的重量和价值:\n", i + 1);
        scanf("%d %d", &ww[i], &v[i]);
    }

    printf("要取物品重量：");
    scanf("%d", &w);

    solve();

    return 0;
}

运行结果：


方法2：（采用记忆化搜索，时间复杂度为O（nw））

#include <stdio.h>

#define MAX_N 100

int n = 0;
int w = 0;
int ww[MAX_N];
int v[MAX_N];
int dp[MAX_N + 1][MAX_N + 1]; /*记忆数组*/

int rec(int i, int j)
{
    int res;

    /*已经搜索过了*/
    if (dp[i][j] >= 0)
    {
        return dp[i][j];
    }

    if (i == n)
    {
        res = 0; /*没有剩余的物品*/
    }
    else if (j < ww[i])
    {
        res = rec(i + 1, j); /*无法挑选这个物品*/
    }
    else /*挑选和不挑选的情况都尝试*/
    {
        res = max(rec(i +1, j), rec(i + 1, j - ww[i]) + v[i]);
    }

    dp[i][j] = res; /*记忆！*/

    return res;
}

int max(int x, int y)
{
    return (x > y ? x : y);
}

void solve()
{
    memset(dp, -1, sizeof(dp));
    printf("能取得最大价值为：%d\n", rec(0, w));
}

int main()
{
    int i = 0;

    printf("请输入物品数量：\n");
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        printf("输入第%d个物品的重量和价值:\n", i + 1);
        scanf("%d %d", &ww[i], &v[i]);
    }

    printf("要取物品重量：");
    scanf("%d", &w);

    solve();

    return 0;
}