给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100)，价值为vi(vi<=100)，背包的容量为C(C<=1000)。
应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。

输入格式:#

本题目有多个测试样例共有n+2行输入：第一行T表示测试样例个数；第二行为n值和c值，表示n件物品和背包容量c；
接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。

输出格式:#

每一行输出对应样例的装入背包中物品的最大总价值。

输入样例:#

输出样例:#

解法#

每隔物品只有两种状态选择或者不选择，可以用记忆化数组来解决，用dp的做法，可以想象一个二维数组，纵坐标代表前i个物品，最多为n个，横坐标代表前j个容量，最多c个依次填入数据，每次填入有两种决策：

if 当前物品<=当前容量选择该物品放入背包比较与上一行数据相比取最大
不放入，继承上一行数据可以发现当前容量只与上一行数据有关，因此可得到以下代码

1
int n,c;
2

3
void solve() {
4
    cin>>n>>c;
5
    vector<vector<int>> dp(n+1,vector<int>(c+1,0));
6
    vector<int> wi(n+1,0);
7
    vector<int> vi(n+1,0);
8
    for(int i=1;i<=n;i++){
9
      cin>>wi[i]>>vi[i];
10
    }
11
    for(int i=1;i<=n;i++){
12
      for(int j=1;j<=c;j++){
13
        if(wi[i]<=j){
14
          dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi[i]]+vi[i]);
15
        }
16
        else{
17
          dp[i][j]=dp[i-1][j];
18
        }
19
      }
20
    }
21
    cout<<dp[n][c]<<'\n';
22
}

但是，当数据量增大的时候，用二维数组做记忆化会有爆内存(mle)的风险，因此改为滚动数组数组循环迭代，用两个一维数组(也就是当前情况和上一行的情况)不断更新，这样会大大减少内存占用

1
// 滚动数组版本
2
int n,c;
3
void solve() {
4
    cin>>n>>c;
5
    vector<int> dp(c+1,0);
6
    vector<int> wi(n+1,0);
7
    vector<int> vi(n+1,0);
8
    for(int i=1;i<=n;i++){
9
      cin>>wi[i]>>vi[i];
10
    }
11
    for(int i=1;i<=n;i++){
12
      vector<int> cur(c+1,0);
13
      for(int j=1;j<=c;j++){
14
        if(wi[i]<=j){
15
          cur[j]=max(dp[j],dp[j-wi[i]]+vi[i]);
16
        }
17
        else{
18
          cur[j]=dp[j];
19
        }
20
      }
21
      dp=cur;
22
    }
23
    cout<<dp[c]<<'\n';
24
}

此外如果逆向维护dp数组甚至可以优化掉一个数组

1
int n,c;
2
void solve() {
3
    cin>>n>>c;
4
    vector<int> dp(c+1,0);
5
    for(int i=1;i<=n;i++){
6
      int w,v;
7
      cin>>w>>v;
8
      for(int j=c;j>=w;j--){
9
        dp[j]=max(dp[j],dp[j-w]+v);
10
      }
11
    }
12
    cout<<dp[c]<<'\n';
13
}

三种方法各有优劣，按需使用，必要时做适当修改

真实的背包故事#

0-1背包问题是经典的动态规划问题，这个问题大多用这样的故事开场：一个小偷溜进了一家博物馆，博物馆里排列着N件珍稀古董，每件古董都有重量和价值，而小偷带来的背包有重量限制W。因此，小偷的目的就是要选择部分古董，使其总重量不超过W且总价值最大。这故事听上去就像小偷在逛超市一样能轻松自如地挑选，而真实的情况是小偷提心吊胆，尤其是每拿下一件古董，随时都有触动警报的危险，所以小偷想尽可能少带几件古董立马跑路，但他的职业“素养”又不允许他不把背包装满。你能帮他解决这个困境吗？

输入格式:#

第一行中给出2个整数值N和W, 其中1<N≤100表示古董的数量，1<W≤2000表示背包的重量限制。
接下来N行数据，每行两个正整数。第i行（1≤i≤N)的整数vi和wi分别表示第i件古董的价值和重量。
vi和wi的值均不超过2000。

输出格式:#

在一行中输出两个整数值，用空格分开。第一个整数表示装背包能获得的最大总价值，第二个整数表示在获得最大价值的条件下装入背包里的古董的最少数量。

输入样例:#

输出样例:#

1
6 1

解题代码#

1
int n,c;
2

3
void solve() {
4
    cin>>n>>c;
5
    vector<int> dpw(c+1,0);
6
    vector<int> dpn(c+1,0);
7
    for(int i=1;i<=n;i++){
8
      int w,v;cin>>w>>v;
9
      for(int j=c;j>=v;j--){
10
        if(dpw[j-v]+w>dpw[j]||(dpw[j-v]+w==dpw[j]&&dpn[j-v]+1<dpn[j])){
11
          dpw[j]=dpw[j-v]+w;
12
          dpn[j]=dpn[j-v]+1;
13
        }
14
      }
15
    }
16
    cout<<dpw[c]<<" "<<dpn[c];
17
}

1
int findMaxForm(vector<string>& strs, int m, int n) {
2
    vector<int> w0,w1;
3
    for(auto s:strs){
4
      int u0=0,u1=0;
5
      for(char c:s){
6
        if(c=='0') u0++;
7
        else u1++;
8
    }
9
    w0.push_back(u0);
10
    w1.push_back(u1);
11
  }
12
  int l=strs.size();
13
  vector<vector<int>> dp(m+1,vector<int>(n+1,0));
14
  for(int i=0;i<l;i++){
15
    for(int j=m;j>=0;j--){
16
      for(int k=n;k>=0;k--){
17
        if(j>=w0[i]&&k>=w1[i]){
18
          dp[j][k]=max(dp[j][k],dp[j-w0[i]][k-w1[i]]+1);
19
        }
20
      }
21
    }
22
  }
23
  return dp[m][n];
24
}

879. 盈利计划 #

记忆化搜索解

1
int dp[105][105][105];
2
int mod = 1e9+7;
3
int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) {
4
  int l=g.size();
5
  memset(dp,-1,sizeof(dp));
6
  auto mems = [&](auto&& self,int i,int j,int k)->int{
7
    if(j<=0) return k<=0?1:0;
8
    if(i==l) return k<=0?1:0;
9
    if(dp[i][j][k]!=-1) return dp[i][j][k];
10
    if(j>=g[i]){
11
      dp[i][j][k]=(self(self,i+1,j,k)+self(self,i+1,j-g[i],max(0,k-p[i])))%mod;
12
    }
13
    else{
14
      dp[i][j][k]=self(self,i+1,j,k)%mod;
15
    }
16
    return dp[i][j][k]%mod;
17
  };
18
  return mems(mems,0,n,m);
19
}

完全背包#

B2174 完全背包 - 洛谷 #

P1616 疯狂的采药 - 洛谷 #

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5

6
const int N = 51;
7
const int MAXN = 1e9;
8

9
const ll MOD = 1e9+7;
10
const ll INF = 4e18;
11

12

13
struct drag{
14
  ll t,w;
15
};
16
int n,m,ans;
17

18
void solve() {
19
    cin>>n>>m;
20
  vector<drag> arr(m+1,{0,0});
21
  vector<ll> dp(n+1,0);
22
  for(int i=1;i<=m;i++){
23
    cin>>arr[i].t>>arr[i].w;
24
  }
25
  for(int i=1;i<=m;i++){
26
    for(int j=1;j<=n;j++){
27
      if(arr[i].t<=j){
28
        dp[j]=max(dp[j],dp[j-arr[i].t]+arr[i].w);
29
      }
30
    }
31
  }
32
  cout<<dp[n];
33
}
34

35
int main(){
36
  ios::sync_with_stdio(0);
37
  cin.tie(0),cout.tie(0);
38
  int T=1;
39
  // cin>>T;
40
    while(T--){
41
      solve();
42
    }
43
  return 0;
44
}

多重背包#

B2173 多重背包 - 洛谷 #

在数据量不大的情况下可以看成c重01背包朴素算法

1
int n,v;
2

3
void solve(){
4
  cin>>n>>v;
5
  vector<int> a(n),b(n),c(n);
6
  vector<ll> dp(v+1,0);
7
  ll w=0;
8
  for(int i=0;i<n;i++){
9
    cin>>a[i]>>b[i]>>c[i];
10
  }
11
  for(int i=0;i<n;i++){
12
    for(int k=0;k<c[i];k++)
13
    for(int j=v;j>=a[i];j--){
14
      dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
15
      w=max(w,dp[j]);
16
    }
17
  }
18
  cout<<w;
19
}

P1776 宝物筛选 - 洛谷 #

但是数据量增大后上述写法效率不高，此时可以使用二进制优化个数

1
int n,v;
2
void solve(){
3
  cin>>n>>v;
4
  vector<int> a,b;
5
  vector<ll> dp(v+1,0);
6
  ll va,w,m;
7
  for(int i=0;i<n;i++){
8
    cin>>va>>w>>m;
9
    for(int k=1;k<=m;k<<=1){
10
      a.push_back(va*k);
11
      b.push_back(w*k);
12
      m-=k;
13
    }
14
    if(m){
15
      a.push_back(va*m);
16
      b.push_back(w*m);
17
    }
18
  }
19
  int len=a.size();
20
  for(int i=0;i<=len;i++){
21
    for(int j=v;j>=b[i];j--){
22
      dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
23
    }
24
  }
25
  cout<<dp[v];
26
}

P10973 Coins - 洛谷 #

1
int n,m;
2
vector<int> a,c,dp;
3
vector<pair<int,int>> b;
4

5
void solve(int n,int m){
6
  a.resize(n);
7
  c.resize(n);
8
  dp.assign(m+1,0);
9
  b.clear();
10
  for(int i=0;i<n;i++){
11
    cin>>a[i];
12
  }
13
  for(int i=0;i<n;i++){
14
    cin>>c[i];
15
  }
16
  for(int i=0;i<n;i++){
17
    for(int j=1;j<=c[i];j<<=1){
18
      b.push_back({a[i]*j,j});
19
      c[i]-=j;
20
    }
21
    if(c[i]){
22
      b.push_back({a[i]*c[i],c[i]});
23
    }
24
  }
25
  int len=b.size(),res=0;
26
  for(int i=0;i<len;i++){
27
    for(int j=m;j>=b[i].first;j--){
28
      if(dp[j]<j){
29
        dp[j]=max(dp[j],dp[j-b[i].first]+b[i].first);
30
        if(dp[j]==j&&j>0) {
31
          res++;
32
        }
33
      }
34

35
    }
36
  }
37
  cout<<res<<"\n";
38
}

分组背包#

P1757 通天之分组背包 - 洛谷 #

1
int n,m;
2
vector<int> ag[101],bg[101];
3
unordered_map<int,int> idx;
4

5
void solve(){
6
  cin>>m>>n;
7
  int a,b,c,tar,g=0;
8
  for(int i=0;i<n;i++){
9
    cin>>a>>b>>c;
10
    if(idx.count(c)==0){
11
      tar=idx[c]=++g;
12
    }
13
    else{
14
      tar=idx[c];
15
    }
16
    ag[tar].push_back(a);
17
    bg[tar].push_back(b);
18
  }
19
  vector<vector<ll>> dp(g+1,vector<ll>(m+1));
20
  for(int i=1;i<=g;i++){
21
    for(int j=0;j<=m;j++){
22
      dp[i][j]=dp[i-1][j];
23
      int len=ag[i].size();
24
      for(int k=0;k<len;k++){
25
        if(ag[i][k]<=j)
26
        dp[i][j]=max(dp[i][j],dp[i-1][j-ag[i][k]]+bg[i][k]);
27
      }
28
    }
29
  }
30
  cout<<dp[g][m];
31
}

换维dp#

常出现在背包dp的问题中，当数据量异常，原本作为容量的数据很大而原本作为状态的数据很小的时候就得想到换维，如以下例题：

Knapsack 2 - AtCoder dp_e - Virtual Judge #

这道题与常规01背包不同的是它的重量数据很大，原本以重量为大小设置的dp背包开不了那么大，那么此时要换一种思维，以价格大小开背包

1
const ll INF = 2e18;
2

3
ll n,m;
4

5
struct gd{
6
  int v;
7
  ll w;
8
};
9

10
void solve(){
11
  cin>>n>>m;
12
  vector<gd> gds(n);
13
  int zv=0,ans=0,len=0;
14
  for(int i=0;i<n;i++){
15
    cin>>gds[i].w>>gds[i].v;
16
    zv+=gds[i].v;
17
  }
18
  vector<ll> dp(zv+1,INF);
19
  dp[0]=0;
20
  for(int i=0;i<n;i++){
21
    len+=gds[i].v;
22
    for(int j=len;j>0;j--){
23
      if(j<=gds[i].v){
24
        dp[j]=min(dp[j],gds[i].w);
25
      }
26
      else{
27
        dp[j]=min(dp[j],dp[j-gds[i].v]+gds[i].w);
28
      }
29
      if(ans<j&&dp[j]<=m){
30
        ans=j;
31
      }
32
    }
33
  }
34
  cout<<ans;
35
}

如果这篇文章对你有帮助，欢迎分享给更多人！

动态规划-背包dp

https://blog.hydrodyio.xyz/posts/动态规划-背包dp/

作者

Hydroiody

发布于

2026-07-28

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

动态规划-线性dp

ACK 2026 暑假第一次集训

Welcome!

文章更新热度

01背包#

例题#

输入格式:#

输出格式:#

输入样例:#

输出样例:#

解法#

真实的背包故事#

输入格式:#

输出格式:#

输入样例:#

输出样例:#

解题代码#

其他例题#

P1049 [NOIP 2001 普及组] 装箱问题 - 洛谷 #

P1164 小 A 点菜 - 洛谷 #

二维01背包 #

879. 盈利计划 #

完全背包#

B2174 完全背包 - 洛谷 #

P1616 疯狂的采药 - 洛谷 #

多重背包#

B2173 多重背包 - 洛谷 #

P1776 宝物筛选 - 洛谷 #

P10973 Coins - 洛谷 #

分组背包#

P1757 通天之分组背包 - 洛谷 #

换维dp#

Knapsack 2 - AtCoder dp_e - Virtual Judge #

目录