算法设计：求将给定重量装进袋子的最低成本

2021年3月26日17:24:44 发表评论 863 次浏览

本文概述

给你一袋大小为W公斤的橘子，在数组成本[]中为你提供不同重量的橘子的包装袋成本，其中成本[i]基本上是每袋i公斤橘子的成本。cost[i] = -1表示一包橘子的"i"无法买到

找出购买W公斤橙子的最低总成本，如果不可能买到W公斤橙子，则打印-1。可以假设所有可用数据包类型都有无限的供应。

注意：数组从索引1开始。

例子：

Input  : W = 5, cost[] = {20, 10, 4, 50, 100}
Output : 14
We can choose two oranges to minimize cost. First 
orange of 2Kg and cost 10. Second orange of 3Kg
and cost 4. 

Input  : W = 5, cost[] = {1, 10, 4, 50, 100}
Output : 5
We can choose five oranges of weight 1 kg.

Input  : W = 5, cost[] = {1, 2, 3, 4, 5}
Output : 5
Costs of 1, 2, 3, 4 and 5 kg packets are 1, 2, 3, 4 and 5 Rs respectively. 
We choose packet of 5kg having cost 5 for minimum
cost to get 5Kg oranges.

Input  : W = 5, cost[] = {-1, -1, 4, 5, -1}
Output : -1
Packets of size 1, 2 and 5 kg are unavailable
because they have cost -1. Cost of 3 kg packet 
is 4 Rs and of 4 kg is 5 Rs. Here we have only 
weights 3 and 4 so by using these two we can  
not make exactly W kg weight, therefore answer 
is -1.

这个问题可以归结为无界背包问题。在cost数组中，我们首先忽略那些不可用的包;cost为-1，然后遍历cost数组并创建两个数组val[]用于存储' i ' kg数据包的成本，wt[]用于存储相应数据包的重量。假设成本[i] = 50，那么数据包的权重为i，成本为50。

算法：

  • 创建矩阵min_cost [n + 1] [W + 1], 其中n是橘子的不同加权小包的数量, W是袋子的最大容量。
  • 用INF(无穷大)初始化第0行, 用0初始化第0列。
  • 现在填充矩阵
    • 如果wt [i-1]> j, 则min_cost [i] [j] = min_cost [i-1] [j]；
    • 如果wt [i-1] <= j, 则min_cost [i] [j] = min(min_cost [i-1] [j], val [i-1] + min_cost [i] [j-wt [i-1 ]]);
  • 如果min_cost [n] [W] == INF, 则输出将为-1, 因为这意味着我们无法使用这些权重来制造权重W, 否则输出将为min_cost [n] [W].

C ++

// C++ program to find minimum cost to get exactly
// W Kg with given packets
#include<bits/stdc++.h>
#define INF 1000000
using namespace std;
 
// cost[] initial cost array including unavailable packet
// W capacity of bag
int MinimumCost( int cost[], int n, int W)
{
     // val[] and wt[] arrays
     // val[] array to store cost of 'i' kg packet of orange
     // wt[] array weight of packet of orange
     vector< int > val, wt;
 
     // traverse the original cost[] array and skip
     // unavailable packets and make val[] and wt[]
     // array. size variable tells the available number
     // of distinct weighted packets
     int size = 0;
     for ( int i=0; i<n; i++)
     {
         if (cost[i]!= -1)
         {
             val.push_back(cost[i]);
             wt.push_back(i+1);
             size++;
         }
     }
 
     n = size;
     int min_cost[n+1][W+1];
 
     // fill 0th row with infinity
     for ( int i=0; i<=W; i++)
         min_cost[0][i] = INF;
 
     // fill 0'th column with 0
     for ( int i=1; i<=n; i++)
         min_cost[i][0] = 0;
 
     // now check for each weight one by one and fill the
     // matrix according to the condition
     for ( int i=1; i<=n; i++)
     {
         for ( int j=1; j<=W; j++)
         {
             // wt[i-1]>j means capacity of bag is
             // less then weight of item
             if (wt[i-1] > j)
                 min_cost[i][j] = min_cost[i-1][j];
 
             // here we check we get minimum cost either
             // by including it or excluding it
             else
                 min_cost[i][j] = min(min_cost[i-1][j], min_cost[i][j-wt[i-1]] + val[i-1]);
         }
     }
 
     // exactly weight W can not be made by given weights
     return (min_cost[n][W]==INF)? -1: min_cost[n][W];
}
 
// Driver program to run the test case
int main()
{
     int cost[] = {1, 2, 3, 4, 5}, W = 5;
     int n = sizeof (cost)/ sizeof (cost[0]);
 
     cout << MinimumCost(cost, n, W);
     return 0;
}

Java

// Java Code for Minimum cost to
// fill given weight in a bag
import java.util.*;
 
class GFG {
     
     // cost[] initial cost array including
     // unavailable packet W capacity of bag
     public static int MinimumCost( int cost[], int n, int W)
     {
         // val[] and wt[] arrays
         // val[] array to store cost of 'i' kg
         // packet of orange wt[] array weight of
         // packet of orange
         Vector<Integer> val = new Vector<Integer>();
         Vector<Integer> wt = new Vector<Integer>();
      
         // traverse the original cost[] array and skip
         // unavailable packets and make val[] and wt[]
         // array. size variable tells the available
         // number of distinct weighted packets
         int size = 0 ;
         for ( int i = 0 ; i < n; i++)
         {
             if (cost[i] != - 1 )
             {
                 val.add(cost[i]);
                 wt.add(i + 1 );
                 size++;
             }
         }
      
         n = size;
         int min_cost[][] = new int [n+ 1 ][W+ 1 ];
      
         // fill 0th row with infinity
         for ( int i = 0 ; i <= W; i++)
             min_cost[ 0 ][i] = Integer.MAX_VALUE;
      
         // fill 0'th column with 0
         for ( int i = 1 ; i <= n; i++)
             min_cost[i][ 0 ] = 0 ;
      
         // now check for each weight one by one and
         // fill the matrix according to the condition
         for ( int i = 1 ; i <= n; i++)
         {
             for ( int j = 1 ; j <= W; j++)
             {
                 // wt[i-1]>j means capacity of bag is
                 // less then weight of item
                 if (wt.get(i- 1 ) > j)
                     min_cost[i][j] = min_cost[i- 1 ][j];
      
                 // here we check we get minimum cost
                 // either by including it or excluding
                 // it
                 else
                     min_cost[i][j] = Math.min(min_cost[i- 1 ][j], min_cost[i][j-wt.get(i- 1 )] +
                                               val.get(i- 1 ));
             }
         }
      
         // exactly weight W can not be made by
         // given weights
         return (min_cost[n][W] == Integer.MAX_VALUE)? - 1 :
                                         min_cost[n][W];
     }
     
     /* Driver program to test above function */
     public static void main(String[] args)
     {
          int cost[] = { 1 , 2 , 3 , 4 , 5 }, W = 5 ;
             int n = cost.length;
          
         System.out.println(MinimumCost(cost, n, W));
     }
}
// This code is contributed by Arnav Kr. Mandal.

Python 3

# Python program to find minimum cost to get exactly
# W Kg with given packets
 
INF = 1000000
 
# cost[] initial cost array including unavailable packet
# W capacity of bag
def MinimumCost(cost, n, W):
 
     # val[] and wt[] arrays
     # val[] array to store cost of 'i' kg packet of orange
     # wt[] array weight of packet of orange
     val = list ()
     wt = list ()
 
     # traverse the original cost[] array and skip
     # unavailable packets and make val[] and wt[]
     # array. size variable tells the available number
     # of distinct weighted packets.
     size = 0
     for i in range (n):
         if (cost[i] ! = - 1 ):
             val.append(cost[i])
             wt.append(i + 1 )
             size + = 1
 
     n = size
     min_cost = [[ 0 for i in range (W + 1 )] for j in range (n + 1 )]
 
     # fill 0th row with infinity
     for i in range (W + 1 ):
         min_cost[ 0 ][i] = INF
 
     # fill 0th column with 0
     for i in range ( 1 , n + 1 ):
         min_cost[i][ 0 ] = 0
 
     # now check for each weight one by one and fill the
     # matrix according to the condition
     for i in range ( 1 , n + 1 ):
         for j in range ( 1 , W + 1 ):
             # wt[i-1]>j means capacity of bag is
             # less than weight of item
             if (wt[i - 1 ] > j):
                 min_cost[i][j] = min_cost[i - 1 ][j]
 
             # here we check we get minimum cost either
             # by including it or excluding it
             else :
                 min_cost[i][j] = min (min_cost[i - 1 ][j], min_cost[i][j - wt[i - 1 ]] + val[i - 1 ])
 
     # exactly weight W can not be made by given weights
     if (min_cost[n][W] = = INF):
         return - 1
     else :
         return min_cost[n][W]
 
# Driver program to run the test case
cost = [ 1 , 2 , 3 , 4 , 5 ]
W = 5
n = len (cost)
 
print (MinimumCost(cost, n, W))
 
# This code is contributed by Soumen Ghosh.

C#

// C# Code for Minimum cost to
// fill given weight in a bag
 
using System;
using System.Collections.Generic;
 
class GFG {
     
     // cost[] initial cost array including
     // unavailable packet W capacity of bag
     public static int MinimumCost( int []cost, int n, int W)
     {
         // val[] and wt[] arrays
         // val[] array to store cost of 'i' kg
         // packet of orange wt[] array weight of
         // packet of orange
         List< int > val = new List< int >();
         List< int > wt = new List< int >();
     
         // traverse the original cost[] array and skip
         // unavailable packets and make val[] and wt[]
         // array. size variable tells the available
         // number of distinct weighted packets
         int size = 0;
         for ( int i = 0; i < n; i++)
         {
             if (cost[i] != -1)
             {
                 val.Add(cost[i]);
                 wt.Add(i + 1);
                 size++;
             }
         }
     
         n = size;
         int [, ]min_cost = new int [n+1, W+1];
     
         // fill 0th row with infinity
         for ( int i = 0; i <= W; i++)
             min_cost[0, i] = int .MaxValue;
     
         // fill 0'th column with 0
         for ( int i = 1; i <= n; i++)
             min_cost[i, 0] = 0;
     
         // now check for each weight one by one and
         // fill the matrix according to the condition
         for ( int i = 1; i <= n; i++)
         {
             for ( int j = 1; j <= W; j++)
             {
                 // wt[i-1]>j means capacity of bag is
                 // less then weight of item
                 if (wt[i-1] > j)
                     min_cost[i, j] = min_cost[i-1, j];
     
                 // here we check we get minimum cost
                 // either by including it or excluding
                 // it
                 else
                     min_cost[i, j] = Math.Min(min_cost[i-1, j], min_cost[i, j-wt[i-1]] + val[i-1]);
             }
         }
     
         // exactly weight W can not be made by
         // given weights
         return (min_cost[n, W] == int .MaxValue )? -1: min_cost[n, W];
     }
     
     /* Driver program to test above function */
     public static void Main()
     {
             int []cost = {1, 2, 3, 4, 5};
             int W = 5;
             int n = cost.Length;
         
             Console.WriteLine(MinimumCost(cost, n, W));
     }
}
// This code is contributed by Ryuga

的PHP

<?php
// PHP program to find minimum cost to
// get exactly W Kg with given packets
$INF = 1000000;
 
// cost[] initial cost array including
// unavailable packet W capacity of bag
function MinimumCost(& $cost , $n , $W )
{
     global $INF ;
     
     // val[] and wt[] arrays
     // val[] array to store cost of 'i'
     // kg packet of orange
     // wt[] array weight of packet of orange
     $val = array ();
     $wt = array ();
 
     // traverse the original cost[] array
     // and skip unavailable packets and
     // make val[] and wt[] array. size
     // variable tells the available number
     // of distinct weighted packets
     $size = 0;
     for ( $i = 0; $i < $n ; $i ++)
     {
         if ( $cost [ $i ] != -1)
         {
             array_push ( $val , $cost [ $i ]);
             array_push ( $wt , $i + 1);
             $size ++;
         }
     }
 
     $n = $size ;
     $min_cost = array_fill (0, $n + 1, array_fill (0, $W + 1, NULL));
 
     // fill 0th row with infinity
     for ( $i = 0; $i <= $W ; $i ++)
         $min_cost [0][ $i ] = $INF ;
 
     // fill 0'th column with 0
     for ( $i = 1; $i <= $n ; $i ++)
         $min_cost [ $i ][0] = 0;
 
     // now check for each weight one by
     // one and fill the matrix according
     // to the condition
     for ( $i = 1; $i <= $n ; $i ++)
     {
         for ( $j = 1; $j <= $W ; $j ++)
         {
             // wt[i-1]>j means capacity of bag
             // is less then weight of item
             if ( $wt [ $i - 1] > $j )
                 $min_cost [ $i ][ $j ] = $min_cost [ $i - 1][ $j ];
 
             // here we check we get minimum
             // cost either by including it
             // or excluding it
             else
                 $min_cost [ $i ][ $j ] = min( $min_cost [ $i - 1][ $j ], $min_cost [ $i ][ $j - $wt [ $i - 1]] +
                                                            $val [ $i - 1]);
         }
     }
 
     // exactly weight W can not be made
     // by given weights
     if ( $min_cost [ $n ][ $W ] == $INF )
             return -1;
     else
         return $min_cost [ $n ][ $W ];
}
 
// Driver Code
$cost = array (1, 2, 3, 4, 5);
$W = 5;
$n = sizeof( $cost );
echo MinimumCost( $cost , $n , $W );
 
// This code is contributed by ita_c
?>

输出如下：

5

空间优化解决方案

空间优化解如果我们仔细看一下这个问题，我们可能会注意到这是一个变化的棒材切割问题。这里我们要做的不是最大化，而是最小化。

CPP

// C++ program to find minimum cost to
// get exactly W Kg with given packets
#include<bits/stdc++.h>
using namespace std;
 
/* Returns the best obtainable price for
    a rod of length n and price[] as prices
    of different pieces */
int minCost( int cost[], int n)
{
    int dp[n+1];
    dp[0] = 0;
   
    // Build the table val[] in bottom up
    // manner and return the last entry
    // from the table
    for ( int i = 1; i<=n; i++)
    {
        int min_cost = INT_MAX;
        for ( int j = 0; j < i; j++)
          min_cost = min(min_cost, cost[j] + dp[i-j-1]);
        dp[i] = min_cost;
    }
   
    return dp[n];
}
 
/* Driver program to test above functions */
int main()
{
    int cost[] = {20, 10, 4, 50, 100};
    int W = sizeof (cost)/ sizeof (cost[0]);
    cout << minCost(cost, W);
    return 0;
}

输出如下：

14

本文作者：

沙尚克·米什拉(古鲁)

本文由lsbin团队审阅。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: