對使用倒序的一維數組解決01背包問題的理解 -开发者知识库

對使用倒序的一維數組解決01背包問題的理解 -开发者知识库,第1张

對使用倒序的一維數組解決0/1背包問題的理解

大略的題目:

   N個物品的價值,從這些物品中選出一些(可能全選)並裝入容積為V的背包,求背包中的物品的最大價值。

輸入: V,N, 接下來第一行是各個物品的體積v,第二行是各個物品的價值w。

輸出: 背包能裝入的物品的最大價值。

要想理解這個問題,可以使用表格來說明、使用二維數組的解法來做對比。

 

測試數據:

9  3
5  3  4
3  5  4

 

首先看二維數組代碼(已經明白了就跳過):

 

對使用倒序的一維數組解決01背包問題的理解 -开发者知识库,第2张 View Code
 1 # include <stdio.h>
2 # include <string.h>
3 # define max(a, b) a>b ? a : b //宏替換
4
5 int dp[1010][1010], w[1010], v[1010]; //dp是動態規划的簡寫,dp[i][j]代表前i個元素裝進容量為j的背包的最優解
6
7 int main () {
8 int V, N;
9 while (scanf("%d %d", &V, &N) == 2) {
10 int i;
11 for (i = 1; i <= N; i)
12 scanf("%d", &v[i]); //輸入N個物品的體積
13 for (i = 1; i <= N; i)
14 scanf("%d", &w[i]); //輸入N個物品的價值
15 memset(dp, 0, sizeof(dp)); //將dp的元素全部初始化為0
16 int j;
17 for (i = 1; i <= N; i) {
18 for (j = 0; j <= V; j) {
19 if (j >= v[i]) {//循環到第i次時,只有容積大於第i個物品的體積才可能裝下第i個物品
20 //即dp[i-1][j-v[i]] w[i] > dp[i-1][j] 才可能成立,此時比較大小才有意義
21 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] w[i]); /****狀態轉移方程****/
22 //dp[i-1][j-v[i]] w[i] 表示前i-1個物品裝入容積恰好等於他們的體積之和的背包的最優解再加上第i個物品的價值
23 //其實也就是前i個物品裝入容積為j的背包(不一定是恰好)
24 } else {
25 dp[i][j] = dp[i-1][j];//否則裝不下第i個物品,所以dp[i][j]等於前i-1個物品裝入j的背包的最優解
26 }
27 if (j == 0) continue;//打印dp表格
28 printf("]", dp[i][j]);//打印dp表格
29 }
30 putchar(10);//打印dp表格
31 }
32 printf("%d\n", dp[N][V]);//輸出前N個物品裝入容積為V的背包的最優解
33 }
34
35 return 0;
36 }

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复