给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
[编程题]数字和为sum的方法数
这题没得说，看到sum的范围为1000就该dp了。。
#include <cstdio>
#include <algorithm>
#include <cstring>
long long dp[1002][1002];
int main()
{
int n;
int A[1002];
int sum;
while (scanf("%d %d", &n, &sum) != EOF)
{
for (int i = 0; i<n; i++)
scanf("%d", A + i);
for (int i = 0; i <= sum; i++)
dp[0][i] = 0;
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= A[i-1])
dp[i][j] += dp[i - 1][j - A[i-1]];
}
}
printf("%lld\n", dp[n][sum]);
}
return 0;
}
发表于 2017-08-08 20:58:02
回复(4)
动态规划算法。dp[i][j]代表用前i个数字凑到j最多有多少种方案。
dp[i][j]=dp[i-1][j]; //不用第i个数字能凑到j的最多情况
dp[j][j]+=dp[i-1][j-value[i]];
//用了i时，只需要看原来凑到j-value[i]的最多情况即可。并累加
dp[0]=1; //初始化，表示凑到0永远有1种方案。
按01背包的思路写循环即可。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int sum = in.nextInt();
int[] value = new int[n];
long[] dp = new long[sum + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
value[i] = in.nextInt();
for (int j = sum; j >= 0; j--) {
if (j >= value[i]) {
dp[j] += dp[j - value[i]];
}
}
}
System.out.println(dp[sum]);
}
}
发表于 2017-04-04 09:19:38
回复(3)
/*
给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
解：此题使用递归的遍历方法也可以解决，但是会超时
dp解决：
以每个物品作为横轴，以背包容量作为纵轴
0 1 2 3 4 5 6..........
0 1 0 0 0 0 0 0..........
5 1 0 0 0 0 1 0
其中1表示前n件物品放入容量为M的背包有1种方法，（5，0）表示重量为5的物品放入容量为0的背包的背包有1中方法，即不放入。0表示恰好放满背包的方法为0
当M>weight[i]时，dp[M]=dp[M]+dp[M-weight[i]];意义是：放入物品i和不放入物品i的方法总和
*/
import java.util.*;
public class Main{
public static long bag(int []weight,int n,int sum){
long dp[]=new long[sum+1];
dp[0]=1;
int i,j;
for(i=0;i<n;i++){
for(j=sum;j>=weight[i];j--){
dp[j]=dp[j-weight[i]]+dp[j];
}
}
return dp[sum];
}
public static void main(String args[]){
Scanner s=new Scanner(System.in);
int n=s.nextInt();
int sum=s.nextInt();
int i,j;
int arr[]=new int[n];
for(i=0;i<n;i++){
arr[i]=s.nextInt();
}
System.out.println(bag(arr,n,sum));
}
}
发表于 2017-01-26 11:29:55
回复(6)
最简单的是一维动态规划 0-1背包问题变种 求方法数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//常量区
const int maxn = 1e3 + 5;
int A[maxn], n, sum;
long long dp[maxn];
//main函数
int main(){
scanf("%d%d", &n, &sum);
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
dp[0] = 1;
for(int i = 1; i <= n; i++)
for(int j = sum; j >= A[i]; j--)
dp[j] = dp[j] + dp[j - A[i]];
printf("%lld\n", dp[sum]);
return 0;
}
/*
5 15
5 5 3 2 10
ans : 4
*/
编辑于 2018-09-17 21:31:01
回复(0)
python3代码， 动态规划
递推关系为
dp[i][j] = dp[i-1][j] + dp[i-1][j-A[i]]
其中i表示数组下标，j表示和为j，dp[i][j]表示前i个元素和为j的方案数
由于递推关系dp[i][j]只与i-1有关，因此空间复杂度可以优化为O(n)
每次的递推数组dp可以由自身得到，循环下标j从m往小循环
n, m = [int(i) for i in input().split()] a = list(map(int,input().split())) dp = [0 for i in range(m+1)] dp[0] = 1 for i in range(n): j = m while j>=a[i]: dp[j] += dp[j-a[i]] j -= 1 print(dp[m])
发表于 2017-10-28 15:47:38
回复(0)
# 最优化方案：时间复杂的O(n*sum), 空间复杂度(sum) n, sum = list(map(int,input().split())) A = list(map(int,input().split())) if sum == 0: print(1) else: s = [0 for _ in range(sum)] for i in range(n): if A[i] > sum: continue for j in range(sum-1-A[i], -1, -1): if s[j] > 0: s[j + A[i]] += s[j] s[A[i]-1] += 1 print(s[-1])
发表于 2017-09-28 11:36:39
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int m = cin.nextInt();
int arr[] = new int[n+1];
//代表你使用前i个数组组成j的最大组合数
long dp[][] = new long[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
arr[i] = cin.nextInt();
}
for (int i = 0; i < m; i++) {
dp[0][i] = 0;
}
//注意，你的dp[0][0]一定要是1，否则会出错
for (int i = 0; i < n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (arr[i] <= j) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println(dp[n][m]);
}
}
发表于 2017-09-06 02:34:18
回复(0)
// 这应该也算是一个动态规划的问题
// 假设dp[sum]表示部分数组和恰好为sum的方案数
// 因此 dp[sum] = dp[sum-num[1]] + ... dp[sum-num[n]]
// 所以要求dp[sum], 需要求所有的dp[0...sum-1]的方案数
// 实际编程的时候我们不这么计算
// 对于每一个num[i],我们更新所有的dp[0...sum],即，dp[k+num[i]] += dp[k]
// 表达的意思就是假设已经知道dp[k]的方案数，那么num[i]使dp[k+num[i]]增加的方案数肯定是再加上dp[k]的方案数。
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int sum = sc.nextInt();
int[] num = new int[n];
for(int i=0;i<n;i++){
num[i] = sc.nextInt();
}
long[] count = new long[sum+1];
count[0] = 1;
for(int i=0;i<n;i++){
if(num[i]<=sum){
for(int j=sum;j>=0;j--){
if(count[j]>0 && j+num[i]<=sum){
count[j+num[i]] += count[j];
}
}
}
}
System.out.println(count[sum]);
}
}
}
编辑于 2017-09-05 10:59:04
回复(1)
import java.util.*;
public class sumA {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while (input.hasNext()) {
int n = input.nextInt();
int m = input.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = input.nextInt();
}
long[][] dp = new long[n][m + 1];
dp[0][0] = 1;
if(arr[0] <= m) {
dp[0][arr[0]] = 1;
}
for(int i = 1; i < n; i++) {
for(int j = 0; j <= m; j++) {
if(j - arr[i] < 0) {
dp[i][j] += dp[i - 1][j];
}
else {
dp[i][j] += dp[i - 1][j - arr[i]] + dp[i - 1][j];
}
}
}
System.out.println(dp[n - 1][m]);
}
input.close();
}
}
发表于 2017-08-17 22:12:01
回复(2)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
long long dp[1005][1005];
int main()
{
using namespace std;
int n, sum;
while (cin >> n >> sum) {
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
for (int i = 0; i < sum; i++) {
dp[0][i] = 0;
}
for (int i = 0; i < n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (nums[i - 1] <= j) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[n][sum] << endl;
}
return 0;
}
参考优秀回答的二维dp解法
发表于 2017-06-22 11:05:27
回复(1)
#include <iostream>
using namespace std ;
long long dp[ 1001 ];
int w[ 1001 ];
bool islegal( int j)
{
if (j>= 0 ) return true ;
return false ;
}
int main()
{
int n,sum;
while ( cin >>n>>sum){
for ( int i= 1 ;i<=n;++i)
cin >> w [i];
//dp(j)=dp(j)+dp(j-w[i]) dp(0)=1
for ( int j= 0 ;j<=sum;++j)
if (j== 0 )
dp [j]= 1 ;
else dp [j]= 0 ;
for ( int i= 1 ;i<=n;++i)
{
for ( int j=sum;j>= 0 ;--j)
{
if ( islegal (j- w [i]))
dp [j] = dp [j]+ dp [j- w [i]];
}
}
cout << dp [sum]<< endl ;
}
return 0 ;
}
发表于 2017-01-28 19:00:41
回复(0)
要用long long才不溢出。。。。
#include <iostream>
using namespace std;
int main()
{
int nCount, nSum;
while (cin >> nCount >> nSum)
{
if (nCount < 1 || nCount > 1000 || nSum < 1 || nSum > 1000)
{
cout << 0 << endl;
continue;
}
int* pNums = new int[nCount];
long long** pDP = new long long*[nCount];
for (int i = 0; i < nCount; ++i)
pDP[i] = new long long[nSum + 1]();
for (int i = 0; i < nCount; ++i)
cin >> pNums[i];
if (nSum >= pNums[0])
++pDP[0][pNums[0]];
for (int i = 1; i < nCount; ++i)
{
for (int j = 1; j <= nSum; ++j)
{
if (j >= pNums[i])
pDP[i][j] = pDP[i - 1][j - pNums[i]] + pDP[i - 1][j];
else
pDP[i][j] = pDP[i - 1][j];
}
if (nSum >= pNums[i])
pDP[i][pNums[i]] = pDP[i - 1][pNums[i]] + 1;
}
cout << pDP[nCount - 1][nSum] << endl;
for (int i = 0; i < nCount; ++i)
delete[] pDP[i];
delete[] pNums;
}
}
发表于 2019-08-26 15:40:56
回复(0)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
int A[1024] = {0};
ll dp[1024] = {1};
int main()
{ int n, m; while (cin >> n >> m)
{
for(int i = 1;i <= n;i++)scanf("%d",&A[i]);
for(int i = 1;i <= n;i++)for(int j = m;j >= A[i];j--)
dp[j] += dp[j - A[i]];
cout << dp[m] << endl; } return 0;
}
编辑于 2019-07-07 21:57:36
回复(0)
动态规划
设m[i][j]是前i个数 和为j的的最大组合方案数
递归公式
1 j=0 //j-a[i]为0时,表示a[i]=j,组合数为1
0 j<0
0 i<1且j!=0
M[i][j]=M[i-1][j]+M[i-1][j-a[i]] //前i-1个 和为j的最大组合数 + 前i-1个 和为 j-a[i]的最大组合数
例如 n=7 sum=8
数据为:5 1 2 4 3 2 3
得到如下矩阵
(i\j) 0 1 2 3 4 5 6 7 8
0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 1 0 0 0
2 1 1 0 0 0 1 1 0 0
3 1 1 1 1 0 1 1 1 1
4 1 1 1 1 1 2 2 2 1
5 1 1 1 2 2 3 3 3 3
6 1 1 2 3 3 5 5 6 6
7 1 1 2 4 4 7 8 9 11
例如:m[7][9]=m[6][8]+m[6][8-3]=11
由于当前行只用到了上一行的数值,固可用二维数组存储
public static void main(String[] args)throws Exception{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
String[] strings=br.readLine().split("\\s");
int n=Integer.parseInt(strings[0]);
int sum=Integer.parseInt(strings[1]);
strings=br.readLine().split("\\s");
int[]data=new int[n];
for(int i=0;i<n;i++){
data[i]=Integer.valueOf(strings[i]);
}
dp(n,sum,data);
}
private static void dp(int n,int sum,int [] data){
long[][] m=new long[2][sum+1];
m[0][0]=1;//j=0
m[1][0]=1;//j=0
for(int i=1;i<=n;i++){
for(int j=1;j<=sum;j++){
if(j>=data[i-1]){
m[1][j]=m[0][j]+m[0][j-data[i-1]];
}else {
m[1][j]=m[0][j];
}
}
// System.out.println(Arrays.toString(m[0]));
for(int k=0;k<=sum;k++){
m[0][k]=m[1][k];
}
}
// System.out.println(Arrays.toString(m[0]));
System.out.println(m[0][sum]);
}
发表于 2018-12-08 18:46:44
回复(0)
Python3 solution
n, sum_wanted = map(int, input().split()) l = [0] + list(map(int, input().split())) res = [[1 if i == 0 else 0 for i in range(sum_wanted + 1)] for j in range(n + 1)] for i in range(1, n + 1): for j in range(1, sum_wanted + 1): if l[i] <= j: res[i][j] = res[i-1][j]+res[i-1][j-l[i]] else: res[i][j] = res[i-1][j] print(res[n][sum_wanted])
发表于 2018-08-01 12:55:40
回复(1)
常规DP，dp[sum][i] = dp[sum-num[i]][i-1]+dp[sum][i-1] i表示只考虑前i个数。
N,sum_x= map(int,input().split())
list_x = [int(x) for x in input().split()]
len_x = len(list_x)
ans = [[0 for i in range(N+1)] for j in range(sum_x+1)]
for i in range(N+1):
ans[0][i] = 1
for i in range(1,sum_x+1):
for j in range(1,N+1):
if i-list_x[j-1]<0:
ans[i][j] = ans[i][j-1]
else:
ans[i][j] = ans[i][j-1]+ans[i-list_x[j-1]][j-1]
print(ans[-1][-1])
发表于 2018-05-23 23:50:28
回复(0)
#include <iostream>
using namespace std;
int main()
{ long long dp[1003][1003]; int a[1003],n,sum; while(cin>>n>>sum) { for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<=sum;i++) dp[i][0] = 0; dp[0][0] = 1; for(int i=1;i<=n;i++) { for(int j=0;j<=sum;j++) { dp[i][j] = dp[i-1][j]; if(j >= a[i-1]) dp[i][j] += dp[i-1][j-a[i-1]]; } } cout<<dp[n][sum]<<endl; } return 0;
}
发表于 2018-01-15 00:19:28
回复(0)
import java.util.*;
class Main{
private static int[] twoSum(int n, int[] A，int sum){
Map(Integer, Integer) map = new HashMap<>();
for(int i =0; i<n; i++) {
map.put(A[i],i);
}
for(int i=0;i<n;i++) {
int result = sum - A[i];
if(map.containsKey(result) && map.get(result) !=i) {
return new int[]{A[i],i};
}
}
throw new IllegalArgumentException("不存在这样的方案");
}
}
发表于 2017-10-01 23:12:02
回复(3)
#include <iostream>
#include <vector>
using namespace std;
int main(){ int n,trg; while(cin>>n>>trg){ vector<int> a(n,0); vector<vector<long>> dp(n+1,vector<long> (trg+1,0)); for(int i=0;i<n+1;i++) dp[i][0]=1; for(int& t:a) cin>>t; for(int i=1;i<=n;i++){ for(int j=0;j<=trg;j++){ if(a[i-1]<=j){ dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i-1]]; }else{ dp[i][j]=dp[i-1][j]; } } } cout<<dp[n][trg]<<endl; } return 0;
}
发表于 2017-09-20 15:49:16
回复(0)
#Pass rate 20%, timeout
import sys
data=[]
for line in sys.stdin:
data.append([int(i) for i in line.strip('\n').split()])
num=data[0][0]
summ=data[0][1]
data=data[1]
data=[]
for line in sys.stdin:
data.append([int(i) for i in line.strip('\n').split()])
num=data[0][0]
summ=data[0][1]
data=data[1]
def find(data,summ):
count=0
if summ==0:
return 1
count=0
if summ==0:
return 1
if summ<0 or len(data)==0:
return 0
for i in range(len(data)):
count+=find(data[i+1:],summ-data[i])
return count
print(find(data,summ))
return 0
for i in range(len(data)):
count+=find(data[i+1:],summ-data[i])
return count
print(find(data,summ))
编辑于 2017-09-01 19:24:26
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-27 16:22:49 -
2023-01-02 22:21:25
-
2022-11-29 19:34:17 -
2022-11-13 12:49:12
-
2022-09-14 11:51:56
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
