問題 J: 天平

時間限制:?1 Sec??內存限制:?128 MB
提交:?36??解決:?9
[提交][狀態][討論版][命題人:admin]

題目描述

天平的右端放著一件重量為w的物品。現在有n個重量已知的砝碼，只允許在左端放砝碼的前提下，能否通過砝碼判斷出物品的重量。

(注:這里假設當天平的兩端重量不同時天平就會向重的一端傾斜到底!)

輸入

輸入包含兩行，第一行包含兩個整數w(1<=w<=1000)和n(1<=n<=1000)，w表示物品的重量，n表示砝碼的數量。

第二行包含n個整數，x1x2...xn(1 ≤ xi ≤ 1000)，表示每個砝碼的重量。

輸出

如果能夠用天平判斷出物品的重量，輸出Yes。

如果不能，輸出No。

樣例輸入

3 2 1 25 3 3 4 4

樣例輸出

Yes No


解析：
分為兩種情況，1、正好裝滿w 2、能夠裝滿w-1 和 w+1 那么就可以判斷出w的是多少

01背包加一個判斷即可 就是在要裝當前背包容量j時 要判斷一下 j-W[i]是否存在，把dp[0]初始化為1 那么就可以保證這個背包是由固定的
重量組成的最大值
我真是蠢啊。。。。

#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <cmath> #include <algorithm> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn = 10010, INF = 0x7fffffff; int A[maxn], dp[maxn]; int main() {int w, n;cin>> w >> n;mem(dp, 0);dp[0] = 1;for(int i=0; i<n; i++){cin>> A[i];for(int j=w+1; j>=A[i]; j--)if(dp[j-A[i]]) dp[j] = 1;}if(dp[w])cout<< "Yes" <<endl;else if(dp[w-1] && dp[w+1])cout<< "Yes" <<endl;elsecout<< "No" <<endl;return 0; }

?

?

轉載于:https://www.cnblogs.com/WTSRUVF/p/9220319.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的QAU 18校赛 J题 天平（01背包 判断能否装满）的全部內容，希望文章能夠幫你解決所遇到的問題。

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