(闫氏dp分析法)AcWing 2. 01背包问题

简介: (闫氏dp分析法)AcWing 2. 01背包问题

题目链接

2. 01背包问题 - AcWing题库

一些话

切入点

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

输出最大价值。

0<N,V≤1000

0<vi,wi≤1000

1.求解某种符合题意的方案,而且是要最优方案,符合dp特征

2.数据范围在1e3内,属于dp的范畴


流程

闫氏dp分析法


分析问题分为状态表示和状态计算两部分


1.状态表示,思考用1维还是2维来储存数据,此题有物品,空间和价值三种数据要储存,所以宜选用2维


          状态表示后又分为集合和属性两部分


       1.1集合:二维数组f[i][j]表示一个怎样的集合? 01背包中表示物品的选法


               考虑前i个物品的情况下,背包容积还剩j时的最优解


       1.2属性:二维数组f[i][j]储存的数据是什么属性 maxn?minn?数目?此题储存的是maxn


(状态表示部分往往是靠经验来写而不是自己想出来的)


2.状态计算:


       将集合划分成子集合,来一层一层获取


       划分的依据是:最后一个不同的节点,如此题是f[i][j]选不选i,选和不选是两种结果


       每层的选与不选可以将集合划分为两个子集,没有遗漏。(求数量时还有遵循不重复的原则)


       选i,[i-1][j-v[i]] + w[i];


       不选[i-1][j];


最后按照分析的结果枚举每一层,输出f[n][m];

套路

ac代码

// 11:01~11:08
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
// f[i][j],考虑前i件物品,背包容量j时的价值
const int N = 1e3 + 10;
int f[N][N];
int v[N],w[N];
int n,m;
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> v[i] >> w[i];
    }
    for(int i = 1;i <= n;i++){
        for(int j = 0;j <= m;j++){
            f[i][j] = f[i-1][j];
            if(v[i] <= j){
                f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);
                //在纠结这里为什么是f[i-1][j-v[i]] + w[i],
                // 会纠结的根本原因是没明白f[i][j]的含义,考虑前i件物品,背包还剩下j空间时的最优解
                // 因为能选的物品都考虑过后才可能得到一个最优解,所以只有上一层i的数值是正确的,所以只能用f[i-1]的值,不能用f[i]的值
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}
目录
相关文章
|
决策智能
【dp】背包问题
【dp】背包问题
348 2
|
27天前
|
算法 C++
【算法】DP背包问题(C/C++)
【算法】DP背包问题(C/C++)
动态规划之01背包问题和完全背包问题
动态规划之01背包问题和完全背包问题
|
12月前
01背包-动态规划
01背包-动态规划
44 0
|
人工智能 BI
动态规划(DP)——背包问题
动态规划(DP)——背包问题
|
人工智能
动态规划(DP)——线性DP
动态规划(DP)——线性DP
动态规划——01背包问题、完全背包问题
动态规划——01背包问题、完全背包问题
88 0