NOWCODER 小M和天平（动态规划DP）

链接：https://ac.nowcoder.com/acm/problem/13586
来源：牛客网

题意：

小M想知道某件物品的重量，但是摆在他面前的只有一个天平（没有游标）和一堆石子，石子可以放左边也可以放右边。他现在知道每个石子的重量。问能不能根据上述条件，能不能测出所问的重量。

题解：

  根据输入描述，石头数量n（1<=n<=100）,每个石头重量wi（1<=wi<=100）,也就是说，最大能称量$100*100=1e4$范围的物品，超过这个范围肯定称量不了了,输出“NO”即可

if(dp[i-1][j]) {
	dp[i][j]=1;//如果i-1个石头能把重量为j的物品称量出来，那么i个石头也能 
	dp[i][j+wi[i]]=1;//多了一个石头的重量为wi[i]，若是物品的另一边放入石头，则能称量的物体重量+wi[i] 
	dp[i][abs(j-wi[i])]=1;//若是把wi[i]的石头放在物品这一边，则能称量的物体重量就要-wi[j] 
	//要考虑j-wi[i]<0的情况，也就是加进去的石头比物品还要重，那么可称量的物品重量就为负值了，
	//这个时候就要交换一下两边的石头，结果就是abs(j-wi[i])
}

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=110,maxwi=1e4+10;
int n,wi[maxn],dp[maxn][maxwi],m,k;
int main() {
	while(cin>>n) {
		for(int i=1; i<=n; i++) cin>>wi[i];
		memset(dp, 0, sizeof(dp));
		dp[0][0]=1;
		for(int i=1; i<=n; i++) {
			for(int j=0; j<=10000; j++) {
				if(dp[i-1][j]) {
					dp[i][j]=1;
					dp[i][j+wi[i]]=1;
					dp[i][abs(j-wi[i])]=1;
				}
			}
		}
		cin>>m;
		while(m--) {
			cin>>k;
			if(k<=10000 && dp[n][k]) cout<<"YES\n";
			else cout<<"NO\n";
		}
	}
}

本文地址：https://blog.csdn.net/cat_hate_fish/article/details/107625425