大意不再赘述。
二维费用背包,注意题目的条件以及初始化的过程,详细的思路见于,P05:背包九讲,多多积累实现的技巧以及需要注意的地方。有时,“二维费用”的条件是以这样一种隐含的条件给出的:最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用,每个物品的件数费用均为1,可以付出的最大件数费用为M。换句话说,设f[v][m]表示付出费用为v、最多选m件时可得到的最大价值,则根据物品的类型,(01,完全,多重)用不同的方法循环更新,最终在f[0..V][0..M]中寻找答案。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <algorithm> using namespace std; const int MAXN = 1010; const int INF = 0x3f3f3f3f; int f[MAXN][MAXN]; int W[MAXN], V[MAXN]; int n, m, C; void init() { for(int i = 0; i <= C; i++) //二维背包怎么循环就怎么初始化 { for(int j = 0; j <= m; j++) { f[i][j] = -INF; } } f[0][0] = 0; } void dp() { init(); for(int i = 1; i <= n; i++) { for(int v = C; v >= V[i]; v--) { for(int u = m; u >= 1; u--) { f[v][u] = max(f[v][u], f[v-V[i]][u-1]+W[i]); //二维费用为1 } } } int ans = 0; for(int i = 1; i <= C; i++) ans = max(ans, f[i][m]); //怎么循环就怎么找最大值 if(ans < 0) printf("0\n"); else printf("%d\n", ans); } void read_case() { scanf("%d%d%d", &n, &m, &C); for(int i = 1; i <= n; i++) scanf("%d%d", &V[i], &W[i]); } void solve() { read_case(); dp(); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }