背包问题1(01背包)

N件物品,没见有重量Wi,价值Vi;选其中几件放入容量为M的背包中,求价值的最值。——经典背包问题
背包问题分三类:
1.01背包:每件物品仅一件,可以不将背包装满(要么取0件要么1件)
2.完全背包:每件物品无限件,可以不将背包装满。
3.多重背包:每件物品可一定数量件,可不将背包装满。
此片详解01背包。
建一个N*(M+1)的数组dp[N][M],物品从第一个开始遍历依次装入背包。
行下标从0到N - 1,表示从第一种物品装到底N - 1中物品,列从0到M,表示包中物品重量从0到M。

关键公式:dp [ i ] [ j ] = max / min ( dp [ i - 1 ] [ j ] , dp[ i - 1 ] [ j - W[ i ] ] + V [ i ] ) ;

这个公式什么意思呢?max/min是根据题目不同选择采取最大或最小值。主要是看()中的部分。dp[i - 1][ j ]指包内重量为j,但是包中不包含第i种物品。dp[i - 1][j - w[ i ]] + v[ i ]指的是包内装有第i种物品,那么这种情况下,包内总重量为j的情况下前i - 1中物品的重量就应该是j减去当前物品的重量,物品价值就应该是前i - 1种物品的总价值加上当前物品的价值,那么最大或最小价值就是包内装当前物品和不装当前物品两种情况中的最值。

典例:http://acm.hdu.edu.cn/showproblem.php?pid=2602
题意:可理解为背包问题,一共n样物品各有其重量w[ i ]和价值v[ i ],给出背包容量m求出背包所容最大的价值。
分析:每件物品放入或不放入背包,若不放入背包,则dp[ i ] [ j ]的值即为dp[ i - 1 ] [ j ]。若是放入背包,则需要在当重量为 j - w[ i ] 的基础上加入物品 i,价值也应是在dp[ i ] [ j - w [ i ] ] 的值上再加上物品 i 的价值v [ i ] ,其价值即为dp[ i - 1 ] [ j - w[ i ] ]+ v[ i ] 。再取两个之中的较大者即得到最优解。
代码实现:

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int w[1005],v[1005],dp[1005][1005];
int main()
{
    int T,n,m;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        //注意先输入价值!因为这个WA好几次
        for(int i=1;i<=n;i++)
            cin>>v[i];
        for(int i=1;i<=n;i++)
            cin>>w[i];
        memset(dp,0,sizeof(dp));//dp数组初始化
        for(int i=1;i<=n;i++)   //物品从第一个开始遍历
        {
            for(int j=0;j<=m;j++)//质量从0开始,数据有重量为0,价值不为零的情况
            {
                //能装下w[i]时,比较dp[i-1][j]和dp[i-1][j-w[i]]+v[i]
                if(w[i]<=j) {dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}
                //装不下则dp[i][j]=dp[i-1][j]
                else dp[i][j]=dp[i-1][j];
            }
        }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}

相关例题:hdu 1203 2159 2955 1171 2191

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 207,248评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,681评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,443评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,475评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,458评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,185评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,451评论 3 401
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,112评论 0 261
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,609评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,083评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,163评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,803评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,357评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,357评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,590评论 1 261
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,636评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,925评论 2 344

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,724评论 0 33
  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 13,626评论 0 89
  • --饺子 八月份了。 八月份福建的天气依旧是不要命的湿。也不知道是不是年龄的问题,近几年从椅子上起来骨头都会发出“...
    瞻尔阅读 925评论 0 1
  • 我先前所看的版本,是商务印书馆的汉译世界学术名著丛书,何兆武所译的《社会契约论》。这个版本我看的非常艰难,不知是...
    力牧阅读 395评论 0 0
  • 去年的三月和今年的三月莫名的相似,又是变动的季节,因为电脑操作好点被调到护理部帮忙,这一帮就没在回去,在...
    风飞雪阅读 361评论 0 0