0-1背包问题及字典序最小路径（输出放入的物品）

0-1背包问题 (15分)
N件物品，第i件物品的重量和价值分别为w​i和vi(1≤i≤N)，背包容量为W，选择部分物品装入背包，在物品总重量不超过背包容量的条件下，求装入的物品总价值最大的最优装法。

输入格式:

第一行给出正整数N(≤100)和W(≤1000)。接下来N行数据，每行给出两个正整数，第i行的数据对应第i件物品的重量wi
​​ 和价值vi(0<wi​​ ,v​i≤100)。

输出格式:

在第一行输出装入物品后获得的最大价值。在第二行输出最优装法，按从小到大的顺序依次输出装入背包的物品标号。如果有多种装法，则输出字典序最小的最优装法。数字间以空格分隔，且行首尾不得有多余空格。 注：序列X=<x1 , x2 ,…,xm>和Y=<y1,y2,…,yn>，字典序X<Y是指：(1) m<n且<x1 , x2 ,…,xm>=<y1,y2,…,ym>，或者(2) 存在1≤k≤min{m,n},<x1 , x2 ,…,xk-1>=<y1,y2,…,yk-1>

输入样例:
在这里给出一组输入。例如：
4 4
2 4
3 5
1 4
2 5
输出样例:
在这里给出相应的输出。例如：
9
1 4

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstring>
using namespace std;
int w[101][101];
int wei[101],val[101];
int main(){
int N,W;
cin>>N>>W;
for(int i = 1; i<= N ;i++){
cin>>wei[i]>>val[i];
}
fill(w[0],w[0]+101*101,0);
for(int i = N; i > 0; i--){
for(int j = 1; j <= W; j++){
if(wei[i] > j){
w[i][j] = w[i+1][j];
}else{
w[i][j] = max(w[i+1][j],w[i+1][j-wei[i]]+val[i]);
}
}
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= W; j++){
cout<<w[i][j]<<' ';
}
cout<<endl;
}
cout<<w[1][W]<<endl;
int j = W;
for (int i = 1; i <= N; ++i)
{
if(j >= wei[i]&&w[i][j] == w[i+1][j-wei[i]]+val[i]){
cout<<i<<' ';
j -= wei[i];
}
}
return 0;
}

最后

以上就是粗犷项链为你收集整理的0-1背包问题及字典序最小路径（输出放入的物品）的全部内容，希望文章能够帮你解决0-1背包问题及字典序最小路径（输出放入的物品）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。