題目鏈接：http://115.159.40.116/problem_show.php?pid=5767

題目描述

有N種物品各一個，問是否能夠湊成Mkg裝到背包中。

輸入

第一行一個整數T（T<=1000）測試數據組數，每組第一行為（1<N<=1000）,M(1<m<=1000)兩個正整數,第二行N個整數代表N種物品的質量Gi（小于1000）。

輸出

可以湊成輸出“Y”，否則輸出“N”

樣例輸入

2 3 5 1 2 3 3 7 1 2 3

樣例輸出

Y N

<span style="font-size:18px;">#include<cstdio> #include<cstring> #include<iostream> #define M 1000+10 using namespace std;int main(){int t;scanf("%d",&t);while(t--){int n,m,s=0,dp[M],v[M]; memset(dp,0,sizeof(dp));scanf("%d%d",&n, &m);for(int i=0; i<n; ++i){scanf("%d",&v[i]);s+=v[i];}if(s==m) printf("Y\n");else if(s<m) printf("N\n");else{for(int i=0; i<n; ++i){ for(int j=m; j>=v[i]; --j){ //保證能放下該物品 dp[j]=max(dp[j], dp[j-v[i]]+v[i]); /*確定的容量下，該物品放與不放 ，哪個能使容量最大 */}}if(dp[m]==m) printf("Y\n");else printf("N\n");}//printf("%d\n",dp[m]);}return 0; }</span>

另一種解決方案（高效率），以當前點為起點，選擇加還是不加，搜索：

<span style="font-size:12px;">#include <iostream> #include<cstdio> using namespace std; int pack[1005],m; bool ok;void dfs(int i, int sum){if(ok) return ;if(i<1) return ;if(sum==m){ok=true;return;}if(sum>m) return;dfs(i-1,sum+pack[i]);dfs(i-1,sum); }int main(){int t,n;scanf("%d",&t);while(t--){scanf("%d%d",&n, &m);for(int i=1; i<=n; ++i){scanf("%d",&pack[i]);}ok=false;dfs(n,0);if(ok)printf("Y\n");elseprintf("N\n");}return 0; }</span><span style="font-size: 24.5px;"> </span>

總結

以上是生活随笔為你收集整理的NYOJ 5767 装背包的全部內容，希望文章能夠幫你解決所遇到的問題。

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