完全背包

说明

最简单的入门DP问题

给出一个容积为V的背包,以及n个物品,每个物品可以装入背包任意次(可以为0次),问背包内物品的最大价值是多少

f[]表示背包容积

w[]表示物品价值 下标1~n

c[]表示物品体积 下标1~n

使用方法

  1. 输入w[],c[],n,V
  2. int ans = work();返回值即为最大价值

模版

const int maxv = 1005;
const int maxn = 105;
int f[maxv];
int w[maxn],c[maxn];
int n,V;
int work(){
    for (int i = 1; i <= n; ++i)
        for (int v = c[i]; v <= V; v++)
            f[v]=max(f[v],f[v-c[i]]+w[i]);
    return f[V];
}

results matching ""

    No results matching ""