有?NN?種物品和一個容量是?VV?的背包，每種物品都有無限件可用。

第?ii?種物品的體積是?vivi，價值是?wiwi。

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
輸出最大價值。

輸入格式

第一行兩個整數，N，VN，V，用空格隔開，分別表示物品種數和背包容積。

接下來有?NN?行，每行兩個整數?vi,wivi,wi，用空格隔開，分別表示第?ii?種物品的體積和價值。

輸出格式

輸出一個整數，表示最大價值。

數據范圍

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

輸入樣例

4 5 1 2 2 4 3 4 4 5

輸出樣例：

10

思路：

dp[i]表示體積小于i的所有方案中的價值最大值

?

提交的代碼：

import java.util.Scanner;

public class Main {
public static void main(String[] args)
{
?? ?int m,n;
?? ?Scanner sc = new Scanner(System.in);
?? ?m = sc.nextInt();//物品數量
?? ?n = sc.nextInt();//背包容量
?? ?int i,j;
?? ?int dp[] = new int[n+1];
?? ?int weight[] = new int[m+1];
?? ?int value[] = new int[m+1];
?? ?for(i=1;i<=m;i++)
?? ?{
?? ??? ?weight[i] = sc.nextInt();
?? ??? ?value[i] = sc.nextInt();
?? ?}
?? ?for(i=1;i<=m;i++)
?? ?{
?? ??? ?for(j=weight[i];j<=n;j++)? //例如現在物品的體積為3，dp[3]=max(dp[3], dp[0]+value[i]),dp[6]=max(dp[6], dp[3]+value[i])

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//dp[9]=max(dp[9], dp[6]+value[i]),所以同一物品選取多次的情況已經考慮到了
?? ??? ?{

?? ??? ??? ?dp[j]=Math.max(dp[j], dp[j-weight[i]]+value[i]);
?? ??? ?}
?? ?}
?? ?System.out.println(dp[n]);
}
}
?

總結

以上是生活随笔為你收集整理的AcWing：3.完全背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。