企业官网建设流程全解析

题目：12. 背包问题求具体方案

题目描述

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

第 i 件物品的体积是v i v_ivi​，价值是w i w_iwi​。

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

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

输入格式

第一行两个整数，N NN，V VV，用空格隔开，分别表示物品数量和背包容积。

接下来有N NN行，每行两个整数v i v_ivi​,w i w_iwi​，用空格隔开，分别表示第i ii件物品的体积和价值。

输出格式

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是1 … N 1…N1…N。

数据范围

0 < N , V ≤ 1000 0<N,V≤10000<N,V≤1000

0 < v i , w i ≤ 1000 0<v_i,w_i≤10000<vi​,wi​≤1000

时空限制

1s / 64MB

输入样例

4 5 1 2 2 4 3 4 4 6

输出样例

1 4

代码1

用一个二维数组记录每次的选择

#include<bits/stdc++.h>usingnamespacestd;constintN=1000+10;intn,V,v[N],w[N],f[N][N];boolg[N][N];intmain(){cin>>n>>V;for(inti=1;i<=n;i++)cin>>v[i]>>w[i];for(inti=n;i>=1;i--)for(intj=0;j<=V;j++){f[i][j]=f[i+1][j];if(v[i]<=j){inttmp=f[i+1][j-v[i]]+w[i];if(tmp>=f[i][j]){//因为字典序最小,所以尽可能选择i小的,这里取到等于f[i][j]=tmp;g[i][j]=true;}}}for(inti=1,j=V;i<=n;i++)if(g[i][j]){cout<<i<<" ";j-=v[i];}return0;}

代码

#include<iostream>usingnamespacestd;constintMaxN=1000+10,MaxV=1000+10;intN,V,v[MaxN],w[MaxN],f[MaxN][MaxV];intmain(){cin>>N>>V;for(inti=1;i<=N;i++){cin>>v[i]>>w[i];}for(inti=N;i>=1;i--){for(intj=0;j<=V;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[1][V]是最大价值intj=V;for(inti=1;i<=N;i++){if(v[i]<=j&&f[i][j]==f[i+1][j-v[i]]+w[i]){cout<<i<<" ";j-=v[i];}}return0;}

结果