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

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

## 本文概述

``````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.``````

• 创建矩阵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[i] = INF;

// fill 0'th column with 0
for ( int i=1; i<=n; i++)
min_cost[i] = 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);

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 )
{
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)
{
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 [ \$i ] = \$INF ;

// fill 0'th column with 0
for ( \$i = 1; \$i <= \$n ; \$i ++)
\$min_cost [ \$i ] = 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;

// 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);
cout << minCost(cost, W);
return 0;
}``````

``14`` 