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

2021年3月12日14:04:02 发表评论 788 次浏览

## 本文概述

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

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