背包问题（包括路径统计）

码蹄集OJ-赶deadline

#include<bits/stdc++.h> 
using namespace std;
const int N=1e4+1;
int n,T;
int v[N],w[N],dp[N],path[N][N],cnt[N];
int main( )
{cin>>n>>T;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=T;j>=w[i];j--){if(dp[j-w[i]]+v[i]>dp[j]){dp[j]=dp[j-w[i]]+v[i];path[i][j]=1;}}}cout<<dp[T]<<endl;int i=n;int j=T;int ans=0;while(i>=1&&j){if(path[i][j]){cnt[ans++]=i;j-=w[i];}i--;}for(int i=ans-1;i>=0;i--){cout<<cnt[i]<<" ";}return 0;
}

01背包问题，将时间看作背包能装的最大重量，将重要度看作物品价值。这道题需要额外统计出取的物品的路径，所以不能直接得取与不取之间的最大值，需要在取物品时将路径数组path变为1，这样数组中值为一的就是选取的物。接下来遍历重量与价值，将取得物的编号统计在cnt数组中，最后遍历cnt数组。