重量最小的背包

kuarbcqp  于 2021-06-30  发布在  Java
关注(0)|答案(2)|浏览(321)

背包问题的这种变化需要最小的重量。目标是最小化成本,同时至少达到最小重量。
例如,我们有6个项目的重量 {1, 1, 1, 5, 13, 3} 和成本 {1, 1, 1, 5, 10, 12} . 假设最小重量为15。
最佳解决方案是 {1, 2, 5} 总共15磅,12美元。
我应该如何尽可能有效地实现这个算法?贪婪的选择不起作用,所以我应该修改原始的动态规划解决方案来适应这个问题吗?如果是,怎么做?
如果有关系的话,我打算用java来写这个。

xzlaal3s

xzlaal3s1#

minCost[i] 表示背包容量的最小值 i 我能坚持住, costs[i] 表示第i项的成本,以及 weights[i] 表示第i项的重量。然后,对于每一个我, minVal[i] 是最小值 minVal[i - weights[j]] + costs[j] 对所有人 j 从1到项目数。
那么,答案就是 minCost 从最小权重到最大权重范围内的数组。

final int[] weights = {1, 1, 1, 5, 13, 3}, costs = {1, 1, 1, 5, 10, 12};
final int minWeight = 15;
int maxWeight = 0;
for(final int weight: weights){
    maxWeight += weight;
}
final int[] minCost = new int[maxWeight + 1];
for(int i = 1; i <= maxWeight; i++){
    minCost[i] = Integer.MAX_VALUE;
}
for(int i = 0; i < weights.length; i++){
    for(int j = maxWeight; j >= weights[i]; j--){
        if(minCost[j - weights[i]] != Integer.MAX_VALUE){
            minCost[j] = Math.min(minCost[j], minCost[j - weights[i]] + costs[i]);
        }
    }
}
int answer = Integer.MAX_VALUE;
for(int i = minWeight; i <= maxWeight; i++){
    answer = Math.min(answer, minCost[i]);
}
System.out.println(answer);

演示

egmofgnx

egmofgnx2#

让我们定义函数f(i,j),它给出了从第一个i+1个项目(0,1…i)中选择项目的最小成本,其中这些项目的权重之和正好等于j,那么获得至少权重(minw=15)的最小成本将如下计算:

min(f(i,j)) where  i=0,1...n-1, j=minW,minW+1,.... maxW 
- n is the number of items 
- minW=15 in your case
- maxW is the maximum possible sum of all the given weights

您可以参考以下c++代码(非常类似于java):

const int maxW = 100;//the maximum weight, a problem constraint
    const int maxN = 100;//the maximum number of items, a problem constraint

    int n = 6; //input
    int w[maxN] = { 1, 1, 1, 5, 13, 3 };//the weights(should be read as an input)
    int c[maxN] = { 1, 1, 1, 5, 10, 12 };//the costs(should be read as an input)

    int f[maxN][maxW];
    for (int i = 0; i < maxN; i++)
        for (int j = 0; j < maxW; j++)
            f[i][j] = 1000000;//some big value

    int minW = 15;//the minimum weight(should be read as an input)

    int result = 1000000;

    f[0][w[0]] = c[0];//initialization
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < maxW; j++) {

            f[i][j] = f[i - 1][j];//don't pick the i-th item

            if (j - w[i] >= 0) {//pick the i-th item if possible
                if (f[i][j] > f[i - 1][j - w[i]] + c[i])
                    f[i][j] = f[i - 1][j - w[i]] + c[i];
            }

            if (j >= minW and f[i][j] < result) {
                result = f[i][j];//store the minimum cost when the weight is >= minW
            }
        }
    }
    cout << result << endl;//print the result(12 in this case)

相关问题