算法设计（经典背包问题（允许重复物品）解析和代码实现） _动态规划

本文概述

C ++
Java
Python3
C#
的PHP

给定一个背包重量W和一组n个具有一定值vali和重量wti的物品，我们需要精确计算出可以弥补这个数量的最大数量。这与经典的背包问题不同，在这里我们可以无限制地使用一个物品的实例。
例子：

Input : W = 100 val[]= {1, 30} wt[] = {1, 50} Output : 100 There are many ways to fill knapsack. 1) 2 instances of 50 unit weight item. 2) 100 instances of 1 unit weight item. 3) 1 instance of 50 unit weight item and 50 instances of 1 unit weight items. We get maximum value with option 2.Input : W = 8 val[] = {10, 40, 50, 70} wt[]= {1, 3, 4, 5} Output : 110 We get maximum value with one unit of weight 5 and one unit of weight 3.

推荐：请在"
实践
首先, 在继续解决方案之前。
这是一个无穷无尽的背包问题, 因为我们可以使用任何资源的1个或多个实例。可以使用一个简单的1D数组, 例如dp [W + 1], 以便dp [i]存储可以使用所有项目和背包容量i达到的最大值。请注意, 此处我们使用的是1D数组, 这与我们使用2D数组的经典背包不同。在这里, 项目数量永远不会改变。我们总是有所有可用的物品。
我们可以使用以下公式递归计算dp []

dp[i] = 0 dp[i] = max(dp[i], dp[i-wt[j]] + val[j] where j varies from 0 to n-1 such that: wt[j] < = iresult = d[W]

以下是上述想法的实现。
C ++

// C++ program to find maximum achievable value // with a knapsack of weight W and multiple // instances allowed. #include< bits/stdc++.h> using namespace std; // Returns the maximum value with knapsack of // W capacity int unboundedKnapsack( int W, int n, int val[], int wt[]) { // dp[i] is going to store maximum value // with knapsack capacity i. int dp[W+1]; memset (dp, 0, sizeof dp); // Fill dp[] using above recursive formula for ( int i=0; i< =W; i++) for ( int j=0; j< n; j++) if (wt[j] < = i) dp[i] = max(dp[i], dp[i-wt[j]] + val[j]); return dp[W]; } // Driver program int main() { int W = 100; int val[] = {10, 30, 20}; int wt[] = {5, 10, 15}; int n = sizeof (val)/ sizeof (val[0]); cout < < unboundedKnapsack(W, n, val, wt); return 0; }

Java

// Java program to find maximum achievable // value with a knapsack of weight W and // multiple instances allowed. public class UboundedKnapsack {private static int max( int i, int j) { return (i > j) ? i : j; }// Returns the maximum value with knapsack // of W capacity private static int unboundedKnapsack( int W, int n, int [] val, int [] wt) {// dp[i] is going to store maximum value // with knapsack capacity i. int dp[] = new int [W + 1 ]; // Fill dp[] using above recursive formula for ( int i = 0 ; i < = W; i++){ for ( int j = 0 ; j < n; j++){ if (wt[j] < = i){ dp[i] = max(dp[i], dp[i - wt[j]] + val[j]); } } } return dp[W]; } // Driver program public static void main(String[] args) { int W = 100 ; int val[] = { 10 , 30 , 20 }; int wt[] = { 5 , 10 , 15 }; int n = val.length; System.out.println(unboundedKnapsack(W, n, val, wt)); } } // This code is contributed by Aditya Kumar

Python3

# Python3 program to find maximum # achievable value with a knapsack # of weight W and multiple instances allowed. # Returns the maximum value # with knapsack of W capacity def unboundedKnapsack(W, n, val, wt): # dp[i] is going to store maximum # value with knapsack capacity i. dp = [ 0 for i in range (W + 1 )] ans = 0 # Fill dp[] using above recursive formula for i in range (W + 1 ): for j in range (n): if (wt[j] < = i): dp[i] = max (dp[i], dp[i - wt[j]] + val[j]) return dp[W] # Driver program W = 100 val = [ 10 , 30 , 20 ] wt = [ 5 , 10 , 15 ] n = len (val) print (unboundedKnapsack(W, n, val, wt)) # This code is contributed by Anant Agarwal.

// C# program to find maximum achievable // value with a knapsack of weight W and // multiple instances allowed. using System; class UboundedKnapsack {private static int max( int i, int j) { return (i > j) ? i : j; }// Returns the maximum value // with knapsack of W capacity private static int unboundedKnapsack( int W, int n, int []val, int []wt) {// dp[i] is going to store maximum value // with knapsack capacity i. int []dp = new int [W + 1]; // Fill dp[] using above recursive formula for ( int i = 0; i < = W; i++){ for ( int j = 0; j < n; j++){ if (wt[j] < = i){ dp[i] = Math.Max(dp[i], dp[i - wt[j]] + val[j]); } } } return dp[W]; } // Driver program public static void Main() { int W = 100; int []val = {10, 30, 20}; int []wt = {5, 10, 15}; int n = val.Length; Console.WriteLine(unboundedKnapsack(W, n, val, wt)); } } // This code is contributed by vt_m.

的PHP

< ?php // PHP program to find maximum // achievable value with a // knapsack of weight W and // multiple instances allowed. // Returns the maximum value // with knapsack of W capacity function unboundedKnapsack( $W , $n , $val , $wt ) { // dp[i] is going to store // maximum value with // knapsack capacity i. for ( $i = 0; $i < = $W ; $i ++) $dp [ $i ] = 0; $ans = 0; // Fill dp[] using above // recursive formula for ( $i = 0; $i < = $W ; $i ++) for ( $j = 0; $j < $n ; $j ++) if ( $wt [ $j ] < = $i ) $dp [ $i ] = max( $dp [ $i ], $dp [ $i - $wt [ $j ]] + $val [ $j ]); return $dp [ $W ]; } // Driver Code $W = 100; $val = array (10, 30, 20); $wt = array (5, 10, 15); $n = count ( $val ); //sizeof($val)/sizeof($val[0]); echo unboundedKnapsack( $W , $n , $val , $wt ); // This code is contributed // by shiv_bhakt ?>

【算法设计（经典背包问题（允许重复物品）解析和代码实现）】输出如下：