本文概述

• C ++
• Java
• Python 3
• C#
• 的PHP
• CPP

给你一袋大小为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团队审阅。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  猫鼻支传染人类吗
• 

  雅阁跟crv哪个省油 crv和广汽本田雅阁哪个省油
• 

  那些在柔软时光中的一一遇见（七）
• 

  玉露中间长了一根芽怎么处理 玉露中间长了一根芽怎么处理掉
• 

  初中平方根的计算公式 平方根怎么算出来
• 

  C++变量和基本类型详解
• 

  蓝莓酱怎么熬
• 

  保险种类有哪些 中国十大保险公司排名
• 

  车窗防晒帘哪种好 汽车防晒帘用哪种材质比较好
• 

  武汉海宁皮革城奥莱店在哪里？
• 

  软件设计师10-面向对象-设计模式
• 

  但微颔之的之是什么意思 但微颔之原文
• 

  Redis|Redis 回顾(上)
• 

  海尔空调外机滋滋响怎么回事像漏气,常见的有这些因素
• 

  早鸟报｜字节跳动宣布正式起诉特朗普；TFBOYS网易云音乐演唱会打破世界纪录；周立齐快手吸粉百万后入驻B站
• 

  病毒性脑炎饮食保健注意事项 病毒性脑炎饮食保健
• 

  爱普生350打印机废墨满
• 

  前列腺增生|尿频尿急就一定是前列腺增生？这6大谣言别再信了，看清楚以免再踩坑
• 

  spss二次回归分析
• 

  桌面app下载，有什么好用的电脑壁纸软件

• JavaScript基本语法介绍和用法指南
• 算法设计（第n个卡塔兰数算法实现）
• 在jQuery中如何检查元素是否隐藏（）
• jQuery如何使用ajaxError()方法（代码示例）
• 背景效果（CSS背景属性用法示例）
• PHP如何使用Ds PriorityQueue copy()函数（示例）
• Express.js req.protocol属性的用法介绍
• U盘万能驱动_本文教您U盘驱动
• acer bios设置,本文教您宏碁笔记本怎样bios设置U盘打开