ACM：动态规划，物品无限的背包问题（完全背包问题）

本文主要是介绍ACM：动态规划，物品无限的背包问题（完全背包问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：有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：动态规划，物品无限的背包问题（完全背包问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---