思考
既然是求具体方案,那就简单粗暴的把每个状态的方案保存下来吧!
C++ 代码
#include<iostream>
#include<vector>
using namespace std;
const int N=1001;
int v[N],w[N],n,V,f[N];
vector<int> ans[N];
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++) scanf("%d %d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=V;j>=v[i];j--)
{
if(f[j]<f[j-v[i]]+w[i])
{
ans[j]=ans[j-v[i]]; //复制方案
ans[j].push_back(i); //更新方案
f[j]=f[j-v[i]]+w[i];
}
else if(f[j]==f[j-v[i]]+w[i])
{
vector<int> b=ans[j-v[i]];b.push_back(i);
if(b<ans[j]) ans[j]=b; //更新方案
}
}
for(int i=0;i<ans[V].size();i++) //输出方案
cout<<ans[V][i]<<' ';
return 0;
}
请问b < ans[j]是什么,对比的是地址吗
对比的字典序..刚上网搜了下,第一次见到,nb, orz
Orz
orz!!!!
大佬太强了,y总的课没怎么看懂,看你代码直接看懂了,这对我来说绝对是最好的方法求方案
甚至只需要一维,真的tql
其实背包容量一维加方案一维就是两维了:-)。而且我这算法算是很暴力的了hh,用时是标程的10倍
挺不错!