第八重关：泛化物品

本文主要是介绍第八重关：泛化物品，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

泛化物品是一种思想：

    1）考虑到这样一件物品，它并没有固定的费用和价值，但是它的价值随着你分配给它的费用而变化。

    2）在背包容量为 V 的背包问题中，泛化物品是一个定义域为中的整数的函数 H，当分配给它费用为 v 时，能够的到的价值是H(v)。

    3）泛化物品就是一个数组，给它一个 v，得到相应的 H 值。

题目：HDU 1712（题意非常简洁）

#include<iostream>
#include<cstring>
using namespace std;
const int max_N = 101;int MAX (const int x, const int y)
{if (x > y) return x;else return y;
}int main()
{int N, M;while (cin>> N>> M){if (N == 0 && M == 0) break;int A[max_N][max_N];for (int i = 1; i <= N; i++){for (int j = 1; j <= M; j++){cin>> A[i][j];} }int *dp = new int[max_N+1];for (int i = 0; i <= max_N; i++){dp[i] = 0;}for (int i = 1; i <= N; i++){for (int j = M; j >= 0; j--){for (int k = 1; k <= M; k++){if (j - k >= 0){dp[j] = MAX(dp[j], dp[j - k] + A[i][k]);}}}}cout<< dp[M]<< endl;delete[] dp;}return 0;
} 

 

这篇关于第八重关：泛化物品的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---