474 一和零
給你一個二進制字符串數組 strs 和兩個整數 m 和 n 。
請你找出并返回 strs 的最大子集的長度，該子集中 最多 有 m 個 0 和 n 個 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
輸入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
輸出：4
解釋：最多有 5 個 0 和 3 個 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他滿足題意但較小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不滿足題意，因為它含 4 個 1 ，大于 n 的值 3 。
示例 2：
輸入：strs = ["10", "0", "1"], m = 1, n = 1
輸出：2
解釋：最大的子集是 {"0", "1"} ，所以答案是 2 。
01背包問題
1、確定dp數組含義
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
2、初始化為0
3、確定遞推公式
因為物品的重量有了兩個維度,所以用滾動數組解題，這里用二維數組。
注意：滾動數組雙重for循環，必須先遍歷物品，再遍歷背包，同時背包要倒序遍歷。
01背包遞推公式dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
這里轉化一下，01的個數相當于weight[i]，value就是字符串本身的個數1
int max(int a,int b){return a>b?a:b;
}
int findMaxForm(char** strs, int strsSize, int m, int n) {int dp[m+1][n+1]={};//最多有i個0 j個1的最大子集大小int cnt0,cnt1=0,i,j,k;for(i=0;i<strsSize;i++){char *s=strs[i];int len=strlen(s);cnt0=0,cnt1=0;for(j=0;j<len;j++){if(s[j]=='0')cnt0++;else cnt1++;}for(j=m;j>=cnt0;j--){//先遍歷物品，再遍歷背包容量for(k=n;k>=cnt1;k--){//倒序遍歷，避免被覆蓋dp[j][k]=max(dp[j][k],dp[j-cnt0][k-cnt1]+1);}}}return dp[m][n];
}完全背包
攜帶研究材料（第七期模擬筆試）
題目描述
小明是一位科學家，他需要參加一場重要的國際科學大會，以展示自己的最新研究成果。他需要帶一些研究材料，但是他的行李箱空間有限。這些研究材料包括實驗設備、文獻資料和實驗樣本等等，它們各自占據不同的重量，并且具有不同的價值。
小明的行李箱所能承擔的總重量是有限的，問小明應該如何抉擇，才能攜帶最大價值的研究材料，每種研究材料可以選擇無數次，并且可以重復選擇。
輸入描述
第一行包含兩個整數，n，v，分別表示研究材料的種類和行李所能承擔的總重量?
接下來包含 n 行，每行兩個整數 wi 和 vi，代表第 i 種研究材料的重量和價值
輸出描述
輸出一個整數，表示最大價值。
輸入示例
4 5
1 2
2 4
3 4
4 5輸出示例
10提示信息
第一種材料選擇五次，可以達到最大值。
二維數組會越界，采用一維數組
完全背包與01背包不同點:物品可以重復取多次
1、二維數組情況
（1）dp[i][j]表示[0,i]物品重量為j可重復選的最大價值
?（2）初始化
? ? dp[0][j]=dp[0][j-w[0]]+v[0]
（3）遞推公式
? ?dp[i][j]=dp[i-1][j];//不放物品i
? ?dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
? 這里是dp[i][j-w[i]]+v[i]，與01背包不同，dp[i-1][j-w[i]]+v[i]
2、一維數組
（1）dp[j]表示物品重量為j可重復選的最大價值
?（2）初始化
? ? dp[j]=dp[j-w[0]]+v[0]
與01背包不同，01背包初始化為01即可
（3）遞推公式
dp[j]=max(dp[j],dp[j-w[i]+v[i])
這里與01背包相同
#include<stdio.h>
#define N 10005
#define ll long long
ll max(ll a,ll b){return a>b?a:b;
}
ll w[N]={},v[N]={};
ll dp[N]={};
int main(){int n,m,i,j;scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%lld%lld",&w[i],&v[i]);}//dp[i][j]表示[0,i]物品重量為j可重復選的最大價值for(j=w[0];j<=m;j++){if(j>=w[0])dp[j]=dp[j-w[0]]+v[0];}for(i=1;i<n;i++){for(j=m;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}printf("%lld",dp[m]);return 0;
}518 零錢兌換
給你一個整數數組?coins?表示不同面額的硬幣，另給一個整數?amount?表示總金額。
請你計算并返回可以湊成總金額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回?0?。
假設每一種面額的硬幣有無限個。?
題目數據保證結果符合 32 位帶符號整數。
示例 1：
輸入：amount = 5, coins = [1, 2, 5] 輸出：4 解釋：有四種方式可以湊成總金額： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2：
輸入：amount = 3, coins = [2] 輸出：0 解釋：只用面額 2 的硬幣不能湊成總金額 3 。
示例 3：
輸入：amount = 10, coins = [10]
輸出：1
因為題目數據保證結果符合 32 位帶符號整數。所以要用INT_MAX防止數組越界
一維數組
1、dp[j]表示裝滿j錢的方法數
2、初始化dp[0]=1
3、確定動規方程
二維dp 遞推公式：?dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]
壓縮成一維：dp[j] += dp[j - coins[i]]
int change(int amount, int* coins, int coinsSize) {int dp[amount + 1];//dp[j]表示湊滿j錢的方法memset(dp, 0, sizeof (dp));dp[0] = 1;for(int i = 0; i < coinsSize; i++){for(int j = coins[i]; j <= amount; j++){if (dp[j] < INT_MAX - dp[j - coins[i]])dp[j] += dp[j - coins[i]];//防止相加數據超過int}}return dp[amount];
}
