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

本文概述

• 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] <= i

result = 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#

// 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
?>

输出如下： 

300