NYOJ - 1221 - 找数达人（01背包）

题目描述

   小明最近做出了一道题：如何在一组数中寻找三个数,这三个数的和等于一给出的定值m，洋洋得意。于是小华不乐意了，小华说，你能找找在一组数字中是否有n个数,使得这n个数的和等于一给定的定值m吗？0 < 数字大小 <= 10002. 0 < 序列中数字个数 <= 10003. 0 <= m <=1000输入多组数据，每组两行，第一行为序列内容，第二行为m的值。
输出如能找到，输出Yes，否则，输出No。
样例输入1 3 4 551 3 4 5 92
样例输出YesNo

题目思路：

要凑的数字为背包容量，给定的序列内容既是物品的重量又是价值。

题目代码：

二维数组：

#include <cstdio> 
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
/* 01背包问题 dp[i][j] 表示前i个物品 放入容量为j的背包中的最大重量 */ 
int n, m, a[1005];
int dp[1005][1005];
string s;
int main(){while(getline(cin,s)){memset(a, 0, sizeof(a));memset(dp, 0, sizeof(dp));int j = 1;for(int i = 0; i < s.length(); i++){int temp = 0;while(s[i] >= '0' && s[i] <='9'){temp = temp*10 + s[i]-'0';i++;}a[j++] = temp;}scanf("%d",&m); getchar();int flag = 0;for(int i = 1; i < j; i++)for(int k = 0; k <= m; k++){dp[i][k] = (i == 1 ? 0 : dp[i-1][k]);if(k >= a[i]){          dp[i][k] = max(dp[i][k], dp[i-1][k-a[i]]+a[i]);if(dp[i][k] == m) flag = 1;                   }                   }   if(flag)puts("Yes");elseputs("No");}return 0;
}

一维数组：

#include <cstdio> 
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
/* 01背包问题 dp[i] 表示容量为i的背包中能放物体的最大重量 */ 
int n, m, a[1005];
int dp[1005];
string s;
int main(){while(getline(cin,s)){memset(a, 0, sizeof(a));memset(dp, 0,sizeof(dp));int j = 0;for(int i = 0; i < s.length(); i++){int temp = 0;while(s[i] >= '0' && s[i] <='9'){temp = temp*10 + s[i]-'0';i++;}a[j++] = temp;}scanf("%d",&m); getchar();int flag = 0;for(int i = 0; i < j; i++)for(int k = m; k >= 0; k--){if(k >= a[i]){          dp[k] = max(dp[k], dp[k-a[i]]+a[i]);if(dp[k] == m) {flag = 1;}}       }if(flag)puts("Yes");elseputs("No");}return 0;
}