//0-1背包,对每个物体只有两种结果,取或者不取
//给定n个包,第i个包的话费为c[i],价值为w[i]
//求在给定重量k范围内可以容纳的最大价值为多少
//用一维替代二位的状态转移方程,优化空间复杂度
//例题链接:http://poj.org/problem?id=3624
#include <stdio.h>
#define N 3410
#define M 12885
#define max(a,b) ((a)>(b)?(a):(b))

int c[N],w[N],dp[M],f[N][M];

//dp[j]表示重量为j的最大价值
//dp[j]=max(dp[j],dp[j-w[i]]+c[i])

//0-1背包空间优化前
//f[i][j]表示前i件物品可以组成的重量j的最大价值
//f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i] (j>=w[i])
//f[i][j]=f[i-1][j]                         (j<w[i])
//时间复杂度为O(V*n)
void solve1(){
    int i,j,k,n;
    scanf(“%d%d”,&k,&n);
    for(i=1;i<=n;i++)
        scanf(“%d%d”,&c[i],&w[i]);
    for(i=1;i<=n;i++)
        for(j=0;j<=k;j++)       //顺序
            if(j>=c[i])
                f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
            else
                f[i][j]=f[i-1][j];
    printf(“%d\n”,f[n][k]);
}

//0-1背包空间优化后
//时间复杂度仍为O(V*n)
/*
ZeroOnePack(cost,value){
    for(v=V;v>=cost;v–)
        dp[j]=max(dp[j],dp[j-cost]+value);
}
*/
void solve2(int n,int V){
    int i,j;
    for(i=1;i<=n;i++)
        scanf(“%d%d”,&c[i],&w[i]);//花费、价值
    for(i=1;i<=n;i++)
        for(j=V;j>=c[i];j–)      //逆序(因为:每一次dp[j]都要在dp[j-c[i]]的基础上添加,如果顺序,就会同一件物品添加多次,这也是完全背包要学的)
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
    printf(“%d\n”,dp[V]);
}
int main(){
int n,k;
while(scanf(“%d%d”,&n,&k)!=EOF)
solve2(n,k);
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation