题目

有 NN 种物品和一个容量是 VV 的背包。

第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

输入格式

第一行两个整数，N，VN，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000<N,V≤100 0<vi,wi,si≤1000<vi,wi,si≤100

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

xxxxxxxxxx
10

链接

多重背包

题解

先枚举体积的

朴素

​x
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int v[N], w[N], s[N];

int dp[N][N];


int main() {
    
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= V; ++j) {
            for (int k = 0; k <= s[i] && j >= k * v[i]; ++k) {
                dp[i][j] = max(dp[i][j]
                    , dp[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    } 
                                              
    
    cout << dp[n][V] << endl;
    
    return 0;
}

空间优化

xxxxxxxxxx
#include <iostream>


using namespace std;

int dp[120];

int main() {
    int N, V;
    cin >> N >> V;
    for (int v, s, w, i = 1; i <= N; ++i) {
        cin >> v >> w >> s;
        for (int j = V; j >= v; --j) {
            for (int k = 1; k <= s && k * v <= j; ++k) {
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
            }
        }
    }
    cout << dp[V] << endl;
    
    return 0;
}

先枚举每种物品的数量的

朴素

x
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int v[N], w[N], s[N];

int dp[N][N];


int main() {
    
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
    
    for (int i = 1; i <= n; ++i) {
        for (int k = 0; k <= s[i]; ++k) {
            for (int j = k*v[i]; j <= V; ++j) {
                /*
                至于先枚举物品数量再枚举体积：为啥这样写我暂时没有弄清楚
                按照01背包思路：
                    1、在体积不小于枚举物品的体积时：当前物品在选和不选取最大价值：即 j > v[i] : dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
                    2、在体积小于枚举物品的体积时，只有一种选择，即dp[i][j] = dp[i - 1][j]; 不能选
                
                在多重背包这里，表达成：
                因为先枚举的是物品数量，那么再枚举体积时，就不能利用i - 1层来更新第i层了，因为中间有个k，如果表示成三维状态，我觉得表达成dp[i][k][j] = dp[i][k - 1][j], ...
                if (j >= k*v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - k*v[i]] + k*w[i]);
                else dp[i][j] = dp[i][j];
                也就是下面2行
                */
                
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k*v[i]] + k*w[i]);
            }
        }
    } 

    cout << dp[n][V] << endl;
    
    return 0;
}

空间优化

xxxxxxxxxx
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int v[N], w[N], s[N];

int dp[N];


int main() {
    
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
    
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= s[i]; ++k) {
            for (int j = V; j >= v[i]; --j) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    } 
    cout << dp[V] << endl;
    return 0;
}

二进制优化

xxxxxxxxxx
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int v[N], w[N], s[N];

int dp[N];


int main() {
    
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
    
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; s[i]; s[i] -= k, k <<= 1) {
            k = min(k, s[i]);
            for (int j = V; j >= k * v[i]; --j) {
                dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}