题目描述
给定物品数量和背包的最大容积(体积),求背包能装下的体积下的最大价值的最小字典序是多少(好绕啊:(
思路
dbq,我的思路垃圾,所以代码垃圾
这题和背包问题求方案数 很像所以假设和那题一样需要两个数组,那么这两个数组就是
f[i] 存放体积为i的情况下,背包的最大价值
vector[HTML_REMOVED] p[i] 存放价值最大,体积为i的情况下 的最小字典序
分为两种情况
当前的价值能够更新之前的价值(比之前的价值大)
更新价值,将当前的p的字典序更新
当前的价值和之前的价值一致
比较哪个的字典序比较小,如果之前的字典序比较小那就不需要更新,否则就将当前的p 给清空(clear),然后将p[j-v]
入队,最后将i
入队。
dbq啊 语言组织能力又差(有问题,欢迎留言啊),代码又垃圾( ; ; )
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1010;
int n,m,v,w;
int f[N];
vector<int> p[N];
int main(void){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v>>w;
for(int j=m;j>=v;j--){
int value=f[j-v]+w;
if(value>f[j]){
f[j]=value;
p[j].clear();
for(int k=0;k<p[j-v].size();k++)
p[j].push_back(p[j-v][k]);
p[j].push_back(i);
}else if(value==f[j]){
for(int k=0;k<p[j-v].size();k++){
if(p[j-v][k]<p[j][k]){
p[j].clear();
for(int k=0;k<p[j-v].size();k++)
p[j].push_back(p[j-v][k]);
p[j].push_back(i);
break;
}else if(p[j-v][k]>p[j][k])
break;
}
}
}
}
for(int i=0;i<p[m].size();i++)
cout<<p[m][i]<<' ';
cout<<endl;
return 0;
}
你是怎么忍受这样的代码的😂
QAQ丑习惯了 就不在乎了(我只要缩进规范就行了