dp-01背包&&完全背包

dp

：動态規劃，動态規劃中遞推式的求解方法不是動态規劃的本質。動态規劃的本質，是對問題 狀态的定義和 狀态轉移方程的定義。

## 何為01背包問題

給定n個物品，用兩個數組來表示這n個物品的大小和價值。背包容量為m。求在不重複裝入物品的情況下、最多能裝入背包的總價值是多少。

## 何為完全背包問題

給定n個物品，用兩個數組來表示這n個物品的大小和價值。背包容量為m。可以重複裝入物品的情況下、最多能裝入背包的總價值是多少。

01背包問題求解

參數說明

n為物品的種類數。

m為背包的容量

wight[]數組表示為物品重量。

value[]數組表示物品價值。

dp[][]為自定義dp數組。

定義dp數組

我們定義dp數組dp[i][j],i表示有i種物品可供我們選擇，j表示背包的容量。

dp[i][j]表示我們在i個物品中選擇并填充j容量背包所能得到的最大價值。

初始狀态： 顯然dp[0][j]=0; 因為無可選的物品，背包容量再大。價值都為0.

轉移方程:

從dp[i][j-1]到dp[i][j]有兩種狀态，我們取最優狀态（價值量最大的那種狀态）。這兩種狀态為：1.取不了物品，這時候dp[i][j]=dp[i][j-1];

2.可以取物品，如果取物品，背包總價值為dp[i][j]=dp[i-1][j-wight[i]]+value[i];

如果不取物品，背包總價值為dp[i][j]=dp[i][j-1];我們用總價值來判斷取不取物品dp[i][j]=max(dp[i][j-1],dp[i-1][j-wight[i]]+value[i]);

得到轉移方程就可以做題了

這題來自Lintcode，01背包問題

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &A, vector<int> &V) {
        // write your code here
    int n=A.size();
    int dp[101][1001];
	for (int i = 1; i <=n; i++) {
		for (int j = 1; j <= m; j++) {
			if (j < A[i-1]) {
				dp[i][j] = dp[i - 1][j];
			}
			else{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - A[i-1]] + V[i-1]);
			}
		}
	}
        return dp[n][m];
    }
};
           

我們還可以進一步對dp數組進行簡化，使用一維dp數組。

轉移方程

1.不能取物品,由dp[i][j]=dp[i-1][j]->dp[j]=dp[j];

2.能取物品，不取：由dp[i][j]=dp[i-1][j]->dp[j]=dp[j];

取：由dp[i][j]=dp[i-1][j-wight[i]]+value[i]->dp[j]=dp[j-wight[i]]+value[i];

最優為dp[j]=max(dp[j],dp[j-wight[i]]+value[i]);

還是這題，我們的代碼可以簡化為：

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &A, vector<int> &V) {
        // write your code here
    int n = A.size();
	int *dp = new int[m + 1]();
	for (int i = 0; i < n; i++) {
		for (int j=m;j>=1;j--){
			if (j>=A[i]) dp[j] = max(dp[j],dp[j-A[i]]+V[i]);
		}
	}
    return dp[m];
    }
};
           

完全背包

和01背包的轉移方程一樣，隻是在周遊的時候從前向後周遊即可重複使用物品。代碼如下：

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &A, vector<int> &V) {
        // write your code here
    int n = A.size();
	int *dp = new int[m + 1]();
	for (int i = 0; i < n; i++) {
		for (int j=1;j<=m;j++){
			if (j>=A[i]) dp[j] = max(dp[j],dp[j-A[i]]+V[i]);
		}
	}
    return dp[m];
    }
};
           

因為從前向後周遊，後面的值可以多次在前面的值基礎上增加相同物品，而從後向前周遊，每個值都不能在前面的基礎上增加相同的物品