問題 E: 序列操作Ⅰ
時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB
[提交][狀態(tài)][討論版]
題目描述
給定長(zhǎng)度為 N 的正整數(shù)序列 A_1, A_2, A_3,…, A_N, 從中選出若干個(gè)數(shù)，使它們的和是 M，求有多少種選擇方案。

輸入
第一行是兩個(gè)數(shù)字，表示 N 和 M。(N,M<1000)

輸出
一個(gè)數(shù)字，表示和為 M 的組合的個(gè)數(shù)。

樣例輸入

4 4 1 1 2 2

樣例輸出

3

提示
/*
很基礎(chǔ)的01背包，畫二維表就很容易得出狀態(tài)轉(zhuǎn)移方程。
要記住一開始要用最直觀的方法寫，
即不要一開始就用滾動(dòng)數(shù)組空間優(yōu)化，
要常規(guī)寫法寫好沒有錯(cuò)誤了再進(jìn)行空間優(yōu)化，
這樣解題才不容易出錯(cuò)，思路也更清晰。
*/
開始最直觀寫法：

#include <bits/stdc++.h> using namespace std; const int maxn = 1e3+5; int a[maxn]; int dp[maxn][maxn]; int main() {int n,m;cin>>n>>m;for(int i = 1; i <= n; i++){cin>>a[i];}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(j-a[i]==0){dp[i][j] = dp[i-1][j] + 1;}else if(j-a[i]<0){dp[i][j] = dp[i-1][j];}else{dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]];}}}cout<<dp[n][m]<<endl;return 0; }

滾動(dòng)數(shù)組空間優(yōu)化及常數(shù)優(yōu)化：

#include <bits/stdc++.h> using namespace std; const int maxn = 1e3+5; int a[maxn]; int dp[maxn]; int main() {int n,m;cin>>n>>m;for(int i = 1; i <= n; i++){cin>>a[i];}for(int i = 1; i <= n; i++){for(int j = m; j >= a[i]; j--){dp[j]+=(j-a[i]==0?1:dp[j-a[i]]);}}cout<<dp[m]<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的问题 E: 序列操作Ⅰ（01背包）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。