1.最典型，最基本的dp问题

2.背包的每个容量就是“状态”

  • 01背包(最基础的背包问题):

  • 有N件物品和一个容量为V的背包。第I件物品的费用是c[i]，价值是w[i]。

  • 求解将哪些物品装入背包可使价值总和最大。

  • 问题特点:每种物品仅有一件，可以选择放或不放;

  • 思考:在每个物品都有可能被选中的前提下，如何构造“子问题”?

  • 无序变有序的方法:依次考虑前1、前2、前3…前i个物品;

  • 状态定义:f[i][v]表示前i件物品放入一个容量为v的背包可以获得

  • 的最大价值。

3.0-1背包问题优化

  • 1背包问题伪代码如下:

  • for i = 1 to n //所有物品;

  • for j = V to v[i] //思考:为何没必要循环到0?

  • dp[j] = max(dp[j - v[i]] + w[i],dp[j]);

  • 空间成功优化到一维V。因为j小于v[i]时已经不满足条件。

  • 整个代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int dp[1001], w[1000],c[1000];
int main()
int num,n, V, i j;
scanf("%d",&num);
while(num--){
	scanf("%d %d", &n, &V) //输入物品n个，背包容量为V
    for (i=0; i<n; i++) scanf("%d",&w[i]); //输入物品价值
	for (i=0; i<n; i++) scanf("%d",&c[i]); //输入物品体积
	memset(dp, 0, sizeof(dp));//dp数组初始化
	for (i=0; i<n; i++ )
	for(j=V; j>=c[i]; j--)
	dp[j] = max(dp[j], dp[j-c[i]] + w[i]);
	printf("%d\n", dp[V]);
}```

优化后的代码是按逆序遍历数组，可以避免同一物品被拿多次。

4.完全背包

  • 完全背包特点:一种物品可以取无数个

  • 可否转化成01背包问题?

  • 朴素的转化方式是?

  • 回忆01背包为何要对容量按照逆序循环?

  • 和01背包类似,不过就是正着写（因为正着写可能会有同个物品重复拿取的情况，而完全背包符合这种特点）

  • 深度思考:这类能不能达到的问题应该怎么实现?

5.多重背包

  • 多重背包特点:
    一种物品有C个，既不是固定的1，也不是无数个，是可以被分的

  • 优化的方法:
    运用二进制，进行物品拆分,转化成01背包
    比如:13余相同的物品可分成4组(1,2,4,6)
    用这4组可以组成任意一个113之间的数!
    原理:一个数总可以用2    k表示
    而且总和等于13.所以不会组成超过13的数
    所以可将一种有C个的物品拆分成:
    1,2,4,…,2(k-1),C-(2k-1)
    然后进行01背包

  • 优化部分的参考代码

    int t =1;
while(x=t){
    v[cnt]= a*t;
    c[cnt++]= b*t;
    x-= t
    t<<= 1:
if(x){
    v[cnt]= a*x,
    c[cnt++]= b*x;
  }```

6.二维费用背包

二维费用背包问题
对于每件物品，具有两种不同的费用，选择这件物品必须同时付
出这两种代价;对于每种代价都有一个可付出的最大值(比如，
背包容量、最大承重)，求怎样选择物品可以得到最大的价值。
设第i件物品所需的两种代价分别为a[i]和b[i]，两种代价可付
出的最大值(比如体积和重量)分别为V和U，物品的价值为w[i]。
对应算法:费用加了一维，只需状态也加一维即可!
设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的
最大价值，状态转移方程则为:
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}