动态规划(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;
}