题目:有n种物品,每种物品都有无限件可用。第i种物品的体积是vi,重量是wi。选一些物品装到一个容量为C的背包中,使得背包内物品在总体积不超过C的前提下重量尽量大。
分析,完全背包问题,相对于上上篇文章的硬币问题,只是由DAG上的无权图变成了这里的DAG上的带权图!
输出最后满足体积不超过背包容量的条件下,背包中的最大重量。
代码:
#include <iostream> #include <string> using namespace std; const int MAXN = 10000;int n, S, V[MAXN], d[MAXN], vis[MAXN], W[MAXN]; const int INF = 100000000; int dpmax(int S) { if(vis[S]) return d[S]; vis[S] = 1; int &ans = d[S]; ans = -1 << 30; for(int i = 1; i <= n; ++i) { if(S >= V[i]) ans = max(ans, dpmax(S - V[i]) + W[i]); } return ans; } int main() { memset(vis, 0, sizeof(vis)); cin >> n >> S; for(int i = 1; i <= n; ++i) { cin >> V[i] >> W[i]; } cout << dpmax(S) << endl; return 0; }
ACM:动态规划,物品无限的背包问题(完全背包问题),布布扣,bubuko.com
原文:http://blog.csdn.net/u010470972/article/details/30115389