阿里巴巴之多重背包问题

题目描述：

你是阿里巴巴的一名工程师，正在开发一个电商平台的推荐系统。在这个系统中，你需要根据用户的需求，将一组商品推荐给用户。这些商品有不同的重量和价值，而用户的需求也有一定的容量限制。你需要在用户的背包容量限制下，选择一定数量的商品，使得这些商品的总价值最大化。

具体描述如下：

• 你有一个背包，背包的最大容量为 W。
• 你有 n 种商品，每种商品的数量是有限的，每种商品有 c[i] 个。
• 每种商品 i 有一个重量 w[i] 和一个价值 v[i]。
• 你需要在不超过背包容量 W 的情况下，选择一些商品，使得选择的商品的总价值最大。

输入格式：

• 第一行包含两个整数 n 和 W，分别表示商品的种类数和背包的最大容量。
• 接下来 n 行，每行包含三个整数 w[i]、v[i] 和 c[i]，分别表示第 i 种商品的重量、价值和数量。

输出格式：

• 输出一个整数，表示在不超过背包容量 W 的情况下，能够获得的最大总价值。

示例：

输入：

10 3
2 3 3
3 4 2
4 5 1
 

输出：

14

解释：

在这个示例中，你有3种商品，背包的容量是10。你可以选择如下商品组合来获得最大价值：

• 选择3个重量为2、价值为3的商品，总重量为6，总价值为9。
• 选择2个重量为3、价值为4的商品，总重量为6，总价值为8。
• 选择1个重量为4、价值为5的商品，总重量为4，总价值为5。

总重量为6 + 6 + 4 = 16（超过了背包容量），但可以适当调整，最终可以获得最大总价值为14。

提示：

• 你可以使用动态规划方法来解决这个问题。用二维数组 dp[i][j] 表示前 i 种商品在容量 j 的情况下的最大总价值。
• 每个商品的数量有限，可以通过将每种商品拆分成若干个“01背包”问题来处理。

程序：

#include<bits/stdc++.h>
using namespace std;
int a[1001][3],dp[10001]; 
int main(){
	int w,n;
	cin>>w>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	}
	for (int i=1;i<=n;i++){
		for(int j=1;j<=a[i][2];j++){
			for(int k=w;k>=a[i][0];k--){
				dp[k]=max(dp[k],dp[k-a[i][0]]+a[i][1]);
			}
		}
	} 
	cout<<dp[w];
	return 0;
}

这个程序的目的是解决一个多重背包问题。下面是对这个程序的详细解读：

代码解析

#include<bits/stdc++.h>
using namespace std;

int a[1001][3], dp[10001]; 

int main() {
    int w, n;
    cin >> w >> n;
    
    // 读取每种商品的重量、价值和数量
    for(int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    
    // 动态规划处理
    for (int i = 1; i <= n; i++) {
        // 对于第 i 种商品，处理它的每一个实例
        for(int j = 1; j <= a[i][2]; j++) {
            // 从背包容量的最大值向下遍历，避免重复计算
            for(int k = w; k >= a[i][0]; k--) {
                dp[k] = max(dp[k], dp[k - a[i][0]] + a[i][1]);
            }
        }
    }
    
    // 输出背包容量为 w 时的最大价值
    cout << dp[w];
    return 0;
}

主要步骤

1. 输入读取:

   • w 是背包的最大容量。
   • n 是商品的种类数。
   • a[i][0] 表示第 i 种商品的重量。
   • a[i][1] 表示第 i 种商品的价值。
   • a[i][2] 表示第 i 种商品的数量。

2. 初始化动态规划数组:

   • dp 数组的索引表示背包的容量，dp[k] 表示在容量 k 的情况下可以获得的最大总价值。
   • 初始状态下，dp 数组所有元素默认为0。

3. 动态规划过程:

   • 对于每种商品，通过将每个商品的数量视为多次单独处理，来更新 dp 数组。
   • 内层循环从 w 向下遍历到商品的重量，避免在更新 dp 时重复计算。
   • 对于每个容量 k，检查是否选择当前商品会带来更大的价值。

4. 输出结果:

   • 输出 dp[w]，即背包容量为 w 时可以获得的最大价值。

关键点

• 背包容量遍历的方向: 内层循环 for(int k = w; k >= a[i][0]; k--) 从背包容量的最大值向下遍历，这样可以避免在同一轮中重复计算（即不将某一物品多次计入背包中）。

• 商品实例处理: 外层 for(int j = 1; j <= a[i][2]; j++) 用来处理每种商品的每个实例，使得每种商品的数量限制被正确考虑。

• 时间复杂度: 该算法的时间复杂度为 O(n×w×m)，其中 m 是商品的数量（所有商品实例之和）。对于较大的 w 和 n，可能需要优化处理或使用更高效的算法。

这个程序在处理多重背包问题时是一个经典的动态规划解法，通过仔细处理每种商品的数量和容量限制，保证了最终能计算出最大价值。