动态规划(DP),0-1背包问题


题目链接:http://poj.org/problem?id=3624

1、p[i][j]表示,背包容量为j,从i,i+1,i+2,...,n的最优解。

2、递推公式

p[i][j]=max(p[i+1][j],p[i+1][j-w[i]]+v[i]);

#include <stdio.h>
#include <algorithm>
#include <string.h>
#define NUM 3410 //物品数量的上限
#define CAP 1300 //背包容量的上限

using namespace std;

int w[NUM];//物品的重量
int v[NUM];//物品的价值
int p[NUM][CAP];//p[i][j]表示背包容量为j时,可选物品为i,i+1,...n时的01背包问题的最优解
//题意就是求p[1][c];

//递推表达式即为p[i][j]=max(p[i+1][j],p[i+1][j-w[i]]+v[i]);
//下面递推求出p[1][c];
void knapsack(int c,int n)//c为背包容量,n为物品的数量
{
    //计算递推边界
    int jMax=min(w[n]-1,c);
    for(int j=0; j<=jMax; j++)
        p[n][j]=0;//第n个物品,这里都装不下
    for(int j=w[n]; j<=c; j++)
        p[n][j]=v[n];//第n个物品,这里都装得下
    //开始递推计算到p[2][c];
    for(int i=n-1; i>1; i--)
    {
        jMax=min(w[i]-1,c);
        for(int j=0; j<=jMax; j++)
            p[i][j]=p[i+1][j];//装不下
        for(int j=w[i]; j<=c; j++)
            p[i][j]=max(p[i+1][j],p[i+1][j-w[i]]+v[i]);
    }
    p[1][c]=p[2][c];
    if(c>=w[1])
        p[1][c]=max(p[1][c],p[2][c-w[1]]+v[1]);
}

void traceback(int c,int n,int x[])
{
    for(int i=1;i<n;i++)
    {
        if(p[i][c]==p[i+1][c])
            x[i]=0;
        else
        {
            x[i]=1;
            c=c-w[i];
        }
    }
    x[n]=(p[n][c])?1:0;
}

int main()
{
    int memory[NUM];
    int C,N;///C为容量,N为物品个数
    while(scanf("%d%d",&N,&C)!=EOF)
    {
        memset(p,0,sizeof(p));
        for(int i=1; i<=N; i++)
        {
            scanf("%d",&w[i]);
            scanf("%d",&v[i]);
        }
        knapsack(C,N);
        printf("%d\n",p[1][C]);
        traceback(C,N,memory);
        for(int i=1;i<=N;i++)
            printf("%d ",memory[i]);
        return 0;
    }
}

但是,很遗憾,Runtime Error

这里可以转化为一维DP

p[i]表示背包容量为i 时的最优解

memset(p,0,sizeof(p));

然后遍历所有物品,更新p

递推公式:

for(int i=1;i<=n;i++)
{
    for(int j=W;j>=1;j--)
    {
        if(j>w[i]&&p[j-w[i]]+val[i]>p[j])
            p[i]=p[j-w[i]]+val[i];
    }
}

Source Code

#include <stdio.h>
#include <string.h>
#define N 3500 ///物品数量上限
#define M 13000///背包容量上限

int w[N];///物品重量
int val[N];///物品价值
int p[M];///p[i]表示背包容量为i时的最优解
int n;///物品个数
int W;///背包容量

///求p[W];
void knapsack()
{
    int i,j;
    memset(p,0,sizeof(p));
    for(i=1;i<=n;i++)
    {
        for(j=W;j>=1;j--)
        {
            ///当前第i个物品装得下,而且比不装要优
            if(j>=w[i]&&p[j-w[i]]+val[i]>p[j])
                p[j]=p[j-w[i]]+val[i];
        }
    }
    return ;
}

int main()
{
    int i;
    while(scanf("%d%d",&n,&W)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d%d",&w[i],&val[i]);
        knapsack();
        printf("%d\n",p[W]);
    }
    return 0;
}

优质内容筛选与推荐>>
1、把一个逗号分隔的字符串转换为一个字符串数组
2、C# RabbitMQ
3、ViewPager循环滚动
4、发布流程考虑
5、使用rsync来快速删除大量文件


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn