首页 > 其他 > 详细

0-1背包

时间:2015-12-09 00:22:00      阅读:207      评论:0      收藏:0      [点我收藏+]

状态转移方程为 dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);

dp[i][j]表示i个物品放入容积为j的背包的最大价值量 ,dp[i-1][j]表示不放入物品i,dp[i-1][j-c[i]]+w[i]表示放入i 。

//状态转移方程为 dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1000
#define max(a,b) a>b?a:b
int dp[MAXSIZE][MAXSIZE];
int c[MAXSIZE],w[MAXSIZE];//物品大小和价值量数组

void printpath(int n,int v);
int main()
{

    int n,v;
    scanf("%d%d",&n,&v);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c[i],&w[i]);
    }

    for(int i=1;i<=n;i++)
        for(int j=c[i];j<=v;j++)
        {
            if(j>=c[i]) //剩余容积够
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]); // dp[i][j]表示i个物品放入容积为j的背包的最大价值量
                                                                //dp[i-1][j]表示不放入物品i,dp[i-1][j-c[i]]+w[i]表示放入i
            }
            else
                dp[i][j]=dp[i-1][j]; //容积不够,不能放入i
        }
    printf("%d\n",dp[n][v]);
    printpath(n,v); //递归输出
//    for(int i=n,j=v;i>0;i--)
//        if(dp[i][j]==dp[i-1][j-c[i]]+w[i])
//        {
//            j-=c[i];
//            printf("%d ",i);
//        }

    return 0;
}

void printpath(int n,int v)
{
    if(n>0&&v>=0)
    {

        if(dp[n][v]==dp[n-1][v-c[n]]+w[n])
        {

            printpath(n-1,v-c[n]);
            printf("%d ",n);
        }
        else
            printpath(--n,v);

    }

}

0-1背包

原文:http://www.cnblogs.com/YYFFstory/p/5031470.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!