字数

1117 字

阅读时间

6 分钟

• 完全背包问题和01背包问题的状态表示方法是一样的

flowchart LR
A[动态规划] --> B["状态表示f[i,j]"]
A[动态规划] --> C[状态计算]
B["状态表示f[i,j]"] --> D["集合：所有只考虑前i个物品，且总体积不大于j的所有选法"]
B["状态表示f[i,j]"] --> E["属性：Max"]
C[状态计算] --> F[集合的划分]

一、01背包问题

1.例题题目

有 $N$ 件物品和一个容量为 $N$ 的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，装入的物品总价值最大。 「0-1 背包」是较为简单的动态规划问题，也是其余背包问题的基础。 动态规划是不断决策求最优解的过程，「0-1 背包」即是不断对第$i$个物品的做出决策，「0-1」正好代表不选与选两种决定。

2.解法

1）朴素01背包写法

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    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 = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

2）01背包的一维优化

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int v[N], w[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    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 = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << endl;
    return 0;
}

二、完全背包问题

1. 例题题目

2.解法

1）朴素完全背包写法

#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int f[N][N], v[N], w[N];
// f[i][j]代表前i个物品，一共j的背包体积，最多能拿到的最大价值

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 ++ )
            for(int k = 0; k * v[i] <= j; k ++ ) 
	//一共最多可选k个，从0个开始选，直到选完k个，比较所有取值的f值，以求出最大获利
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                //求出每一个 f[i][j]
    cout << f[n][m] << endl;
    return 0;
}

2）完全背包优化

• 思路如下：
  • f[i, j]找规律：
    • f[i, j] = max(f[i - 1，j]，f[i - 1, j - v] + w, f[i - 1, j - 2v] + 2w, ......)
    • f[i, j - v] = max ( f[i - 1, j - v], f[i - 1, j - 2v] + w, f[i - 1, j - 3v] + 2w, ......)
      • 所以可以总结规律为：f[i , j] = max(f[i, j], f[i, j - v] + w)

#include<iostream>

using namespace std;
  
const int N = 1010;
  
int n, m;
int f[N][N], v[N], w[N];
// f[i][j]代表前i个物品，一共j的背包体积，最多能拿到的最大价值
  
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 (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
	return 0;
}

3）完全背包一维优化

#include<iostream>
using namespace std;
  
const int N = 1010;
  
int n, m;
int f[N], v[N], w[N];
  
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 = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
	return 0;
}

三、多重背包问题

多重背包

四、分组背包问题

例题

分组背包

状态转移规律

• 优化成一维转移方程要特别注意这点
• 如果是从上一层状态转移，就从大到小来枚举体积
• 如果是这一层的状态进行转移，就从小到大来枚举体积
• 因为进行状态转移要保证转移的状态不会在转移过程中发生变化，比如：从上一层转移状态，就必须保证转移时上一层状态不能被改变，所以要从大到小来转移

贡献者

freeway348

文件历史

最后编辑于 大约 1 个月前查看完整历史

01996-OS