求解背包具体方案

描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

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

输出 字典序最小的方案。这里的字典序是指:所选物品的编号所构成的序列。物品的编号范围是 1…N。

思路

  • 用二维记录01背包。为了保证答案字典序最小,dp时从n到1反向推,获取方案数时正向扫描。
  • 从f[][m]往回推,如果f[i][m]==f[i+1][m-v[i]]+w[i]的话说明选了第i个物品
  • 此题需要做边界判定

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repd(i,a,b) for(register int i=a;i>=b;--i)
const int N=1e3+10;
int f[N][N],n,m;
int v[N],w[N];
int main(){
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%d%d",&v[i],&w[i]);
repd(i,n,1){
rep(j,0,m){
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]);
}
}
int vol=m;
rep(i,1,n){
//最后一个物品n的状态不是由n+1推来的
if(vol>=v[i] && i==n) {
printf("%d ",n);
break;
}
if(vol<=0) break;
//要保证vol-v[i]不会越界
if(vol-v[i]>=0 && f[i][vol] == f[i+1][vol-v[i]] + w[i]){
printf("%d ",i);
vol-=v[i];
}
}
return 0;
}
Donate comment here