UVA 624——CD【01背包 + 打印路径】

UVA 624——CD【01背包 + 打印路径】

​​题目传送门​​

题意:

有N个物品,每个物品一个重量,现在问你在重量不超过W的前提下,如何选物品可以使得装的物品尽量多,并且要按输入顺序输出被装入的物品,已经总重量sum.

分析：

基础的01背包，但是要打印路径。 dp[i - 1][j]表示在前i - 1件物品中选取若干物品放入容量为j背包所得到的最大的价值，dp[i - 1][j - w[i]] + v[i]表示前i - 1件物品中选取若干物品放入容量为j - w[i]背包所得到的最大的价值加上第i件物品的价值。这里同理，但是要记录选取的物品，觉得倒着过来就可以了。【注】 原网站Debug数据有问题，Debug数据对于大量重复情况处理不合题意！！！防坑~~~

AC代码：

#include #include #include using namespace std;const int MAXN = 130005;int dp[30][MAXN] , v[30];vector G;int main() { ios::sync_with_stdio(false); int V , n; while(cin >> V >> n) { G.clear(); for(int i = 1 ; i <= n ; i++) { cin >> v[i]; } memset(dp , 0 , sizeof(dp)); for(int i = 1 ; i <= n ; i++) { for(int j = 0 ; j <= V ; j++) { if(j < v[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j - v[i]] + v[i]); } } int i = n , j = V; while(i > 0 && j > 0) { if(j < v[i]) { i--; continue; } if(dp[i][j] == dp[i - 1][j - v[i]] + v[i]) { j -= v[i]; G.push_back(v[i]); } i--; } for(int i = G.size() - 1 ; i > 0 ; i--) { cout << G[i] << " "; } cout << G[0] << " sum:"; cout << dp[n][V] << endl; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。