首页 > 试题广场 >

牛牛的背包问题

[编程题]牛牛的背包问题
  • 热度指数:6167 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。

输入描述:
输入包括两行
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。
第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。


输出描述:
输出一个正整数, 表示牛牛一共有多少种零食放法。
示例1

输入

3 10
1 2 4

输出

8

说明

三种零食总体积小于10,于是每种零食有放入和不放入两种情况,一共有2*2*2 = 8种情况。

想了一下只能用dfs
然后算法如下
最开始的时候会超出运行时间 原因是未考虑 当所有零食的重量之和小于背包的容量的情况和任意一个零食的重量都大于背包的容量的情况。

#include <iostream>
long long int v[31];
int dfs(long long int w,long long int n){
    if(w < 0){
        return 0;
    }
    if(n <= 0 && w >= 0){
        return 1;
    }
    return dfs(w - v[n-1],n-1) + dfs(w,n-1);
}
int main(){
    long long int n,w,real_n;
    std::cin >> n >> w;
    real_n = n;
    long long int value;
    long long int sum = 0;
    int index = 0;
    for(int i=0;i<n;i++){
        std::cin >> value;
        if(value > w){
            real_n--;
            continue;
        }
        sum+=value;
        v[index] = value;
        index++;
    }    
    if(sum <=w){
        std::cout << (1 << real_n) << std::endl;
    }else{
        std::cout << dfs(w,real_n) << std::endl;
    }
    return 0;
}
编辑于 2018-09-16 22:24:07 回复(2)
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, count1 = 0;

ll a[40], w;

vector<ll> v;

void dfs1(int i, int t, ll now) {
    if(now > w) return;
    if(i == t) { v.push_back(now); return;}
    dfs1(i + 1, t, now + a[i]);
    dfs1(i + 1, t, now);
}

void dfs2(int i, ll now) {
    if(now > w) return;
    if(i == n) {
        count1 += upper_bound(v.begin(), v.end(), w - now) - v.begin();
        return;
    }
    dfs2(i + 1, now + a[i]);
    dfs2(i + 1, now);
}

int main()
{
    cin >> n >> w;
    for(int i = 0; i < n; i++) cin >> a[i];
    int t = n / 2;
    
    dfs1(0, t, 0);
    sort(v.begin(), v.end());
    dfs2(t, 0);
    cout << count1 << endl;
    return 0;
}

算法 : 折半枚举.
复杂度 : O(n * 2 ^ (n / 2)) (出题人数据没造好)

编辑于 2018-06-09 15:05:53 回复(1)
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

        // 根据数据量的规模,选择用分治来处理
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int bag = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        long ways = ways(arr, bag);
        System.out.println(ways);
        sc.close();
    }

    public static long ways(int[] arr, int bag) {
        // process过程定义好,那么在当前函数中就应该这样调用:
        // arr  30
        // process(arr, 0, 14, 0, bag, map)
        // process(arr, 15, 29, 0, bag, map)
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0] <= bag ? 2 : 1;
        }
        // 分治算法
        int mid = (arr.length - 1) >> 1;
        TreeMap<Long, Long> lmap = new TreeMap<>();
        // 只从左侧选取得到的符合题意的方法数
        long ways = process(arr, 0, mid, 0, bag, lmap);
        TreeMap<Long, Long> rmap = new TreeMap<>();
        // 只从右侧选取得到的符合题意的方法数(和左侧的加起来)
        ways += process(arr, mid + 1, arr.length - 1, 0, bag, rmap);
        // 两张表lmap和rmap分别已经收集好左右两部分所有符合条件sum及其方法数
        // 此时把右侧表建立一个前缀和表出来
        TreeMap<Long, Long> rpre = new TreeMap<>();
        long pre = 0;
        for (Map.Entry<Long, Long> entry : rmap.entrySet()) {
            pre += entry.getValue();
            rpre.put(entry.getKey(), pre);
        }
        // 右侧的前缀和表已经建好
        // 接下来左侧严格按照表中每一个数据来和右侧符合条件的数据相结合
        for (Map.Entry<Long, Long> entry : lmap.entrySet()) {
            long lweight = entry.getKey();
            long lways = entry.getValue();
            // 左侧当前的零食大小是lweight,右侧在不超过bag的情况下最大的装载量是floor
            Long floor = rpre.floorKey(bag - lweight);// floorKey()方法意即找到小于等于该数且离他最近的那个数
            // 右侧只要零食大小不超过floor,都视为符合条件,找出他们的方法数
            if (floor != null) {
                long rways = rpre.get(floor);
                ways += lways * rways;
            }
        }
        return ways + 1;
    }

    // 从index出发,到end结束
    // 之前的选择,已经形成的累加和为sum
    // 零食[index...end]自由选择,出来的所有累加和不能超过bag,每一种累加和对应的方法数,填在map里
    // 最后不能什么货都没选(最后直接在总方法数上加1即可表示这种情况)
    // 举例:
    // [3,3,3,3]  bag=6
    //  0 1 2 3
    //  - - - -   0 -> (0 : 1)
    //  - - - $   3 -> (0 : 1) (3, 1)
    //  - - $ -   3 -> (0 : 1) (3, 2)
    public static long process(int[] arr, int index, int end, long sum, int bag, TreeMap<Long, Long> map) {
        if (sum > bag) {
            return 0;
        }
        // sum <= bag
        if (index > end) {
            if (sum != 0) {
                if (!map.containsKey(sum)) {
                    map.put(sum, 1L);
                } else {
                    map.put(sum, map.get(sum) + 1);
                }
                return 1;
            } else {
                // sum==0 说明什么都没选,这种情况不计数
                return 0;
            }
        }
        // sum < bag && index <= end(还有货)
        // 1) 不要当前index位置的货
        long ways = process(arr, index + 1, end, sum, bag, map);

        // 2) 要当前index位置的货
        ways += process(arr, index + 1, end, sum + arr[index], bag, map);
        return ways;
    }


}

发表于 2022-01-12 11:31:33 回复(0)
//AC
//坑1 long long数据类型
//坑2 dfs会超时,背包足够大时,单独处理
#include<iostream>
using namespace std;
long long a[35];
long long n,m;
long long cnt=0;
void dfs(int i,long long sum,int flag){
    if(sum<=m&&flag)
        cnt+=1;
    if(i>=n||sum>=m) {
        return;
    }
    dfs(i+1,sum,0);
    dfs(i+1,sum+a[i],1);
}
int main(){

    cin>>n>>m;
    long long sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum<=m){
        cout<<(1<<n)<<endl;
    }else{
        dfs(0,0,1);
        cout<<cnt<<endl;
    }
}
发表于 2019-09-11 14:57:58 回复(0)
#include<iostream>
#include<vector>
#include<map>

using namespace std;
map<pair<int,int>, int> used;

int findNum(const vector<int>& value, int Index, int C)
{
    //放完物品,容量剩余,证明有一种方法可以放
    if(Index < 0 && C >= 0)
        return 1;
    //背包内存不够,返回0
    if(C < 0)
        return 0;
    
    if (used.find(make_pair(Index, C)) != used.end())
        return used[make_pair(Index, C)];
    //不放入第i件物品
    int res = findNum(value, Index-1, C);
    //放入第i件物品
    res += findNum(value, Index-1, C-value[Index]);
    used[make_pair(Index,C)] = res;
    return res;
}

int main()
{
    int n,w;
    while(cin>>n>>w)
    {
        vector<int> value(n);
        for(int i=0; i<n; i++)
            cin>>value[i];
        
        
        int res = findNum(value, n-1, w);
        cout<<res<<endl;
    }
    return 0;
}
发表于 2018-08-06 21:55:04 回复(0)
#include<bits/stdc++.h>
using namespace std;
long long n,w,v[50],ans=0;
long long Pow(long long a,long long b)    //快速幂
{
    long long r=1;
    while(b)
    {
        if(b&1)
            r*=a;
        a*=a;
        b>>=1;
    }
    return r;
}
void dfs(long long m,long long s)   //放m号,之前体积为s
{
    if(s>w)
        return ;
    if(m==n)
    {
        ans++;
        return ;
    }
    dfs(m+1,s+v[m]);    //下次放m+1号,之前体积为s+v[m]
    dfs(m+1,s);
    return ;
}
int main()
{
    long long i;
    long long sum=0;
    cin>>n>>w;    //数量和背包的容量
    for(i=0;i<n;i++)
    {
        cin>>v[i];
        sum+=v[i];
    }
    if(sum<=w)
        cout<<Pow(2,n)<<endl;
    else
    {
        dfs(0,0);   //下次放0号,之前体积为0
        cout<<ans<<endl;
    }
    return 0;
}
如果不用判断总数会80%答案正确,因为超时
这个代码算是比较简单的啦

发表于 2018-05-31 23:20:08 回复(1)
借鉴一下DFS
#include<bits/stdc++.h>
using namespace std;
long long v[40];
int n;
long long ans=0,w;
void dfs(int t,long long sum){
    ans++;
    if(t==n-1){
        return ;
    }
    for(int i=t+1;i<n;i++){
        if(sum+v[i]<=w){
            dfs(i,sum+v[i]);
        }
    }
}
int main(){
    //long long w;
    cin>>n>>w;
    long long sum=0;
    for(int i=0;i<n;i++){
        cin>>v[i];
        sum+=v[i];
    }
    if(sum<=w){
        ans=1<<n;//根据题目,0个也算进去,那就正好是左移n位
    }
    else{
        dfs(-1,0);
    }
    cout<<ans<<endl;
    return 0;
}

编辑于 2018-06-28 09:19:21 回复(0)
//单纯根据题意,加与不加分别一次判断
#include<bits/stdc++.h>
using namespace std;
 
int bag(const vector<int> &num,int beg,int m){
    if(beg==num.size()-1){
        if(m>num[beg])
            return 2;
        return 1;
    }
    if(m>=num[beg])//可以加上
        return bag(num,beg+1,m-num[beg])+bag(num,beg+1,m);//两类加与不加
    return bag(num,beg+1,m);//不能加
}
 
int main(void){
    int n,w;
    while(cin>>n>>w){
        long long sum = 0;
        vector<int> v(n);
        for(int i=0;i<n;i++){
            cin>>v[i];
            sum += v[i];
        }
        if(sum<=w)
            cout<<(1<<n)<<endl;
        else
            cout<<bag(v,0,w)<<endl;
    }
}
发表于 2018-08-18 21:47:52 回复(0)
import java.util.Map;
import java.util.TreeMap;
import java.util.Scanner;
/**
 * 当动态规划时间复杂度超时了
 * 给定数组长度又很小
 * 把数组分治,分成两块,分别求值,再整合
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int bag = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        long ans = main(arr,bag);
        System.out.print(ans);
    }

    public static long main(int[] arr,int bag) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int mid = (arr.length-1) >> 1;
        //分别得到两区域方法数及有序表
        TreeMap<Long, Long> lMap = new TreeMap<>();
        long ways = process(arr,0,mid-1,bag,0,lMap);
        TreeMap<Long, Long> rMap = new TreeMap<>();
        ways += process(arr,mid,arr.length-1,bag,0,rMap);
        //把一半区域的有序表处理成前缀和有序表
        TreeMap<Long, Long> bTempMap = new TreeMap<>();
        long preSum = 0;
        for (Map.Entry<Long,Long> entry:rMap.entrySet()){
            preSum +=  entry.getValue();
            bTempMap.put(entry.getKey(),preSum);
        }
        //计算两区域整合后的方法数-一个区域对另外一个区域严格依赖
        for (Map.Entry<Long, Long> entry : lMap.entrySet()) {
            long lweight = entry.getKey();
            long lways = entry.getValue();
            Long floor = bTempMap.floorKey(bag - lweight);
            if (floor != null) {
                long rways = bTempMap.get(floor);
                ways += lways * rways;
            }
        }
        return ways + 1;
    }

    public static long process(int[] arr, int index, int end, long bag,
                               long sum, TreeMap<Long, Long> map) {
        if (sum > bag) {
            return 0;
        }
        if (index > end) {
            if (sum == 0) {//人为去除啥都不选的方法
                return 0;
            } else {
                if (!map.containsKey(sum)) {
                    map.put(sum, 1L);
                } else {
                    map.put(sum, map.get(sum) + 1);
                }
                return 1;
            }
        }
        long ways = process(arr, index + 1, end, bag, sum, map);
        ways += process(arr, index + 1, end, bag, sum + arr[index], map);
        return ways;
    }
}
发表于 2022-09-06 17:08:19 回复(0)
思路是分而治之,参考了左神实现,这里为了简化代码并没有手动实现有序表,可自行将map替换。
Map.prototype.floorKey = function(key) {
	let map = this;
	let ans = null;
	for(let k of map.keys()) {
		if(k > key) {
			break;
		} else {
			ans = k;
		}
	}
	return ans;
}
// 根据数据量描述,2^30>10^8,采用分而治之的思路
function ways(arr, bag) {
	let len = arr.length;
	if(arr == null || len == 0) {
		return 0;
	}
	if(len == 1) {
		return arr[0] <= bag ? 2: 1;
	}
	let mid = (len - 1) >> 1;
	let lmap = new Map();
	let ways = process(arr, 0, 0, mid, bag, lmap);
	let rmap = new Map();
	ways += process(arr, mid + 1, 0, len - 1, bag, rmap);
	// 对rmap进行手动排序,以模拟TreeMap,这里先不用手动实现有序表,太冗长
	rmap = new Map([...rmap.entries()].sort((a, b) => a[0] - b[0]));
	let rpre = new Map();
	let pre = 0;
	for(let [key, value] of rmap.entries()) {
		pre += value;
		rpre.set(key, pre); // 方法前缀和map
	}
	for(let [lweight, lways] of lmap.entries()) {
		let floor = rpre.floorKey(bag - lweight);
		if(floor != null) {
			let rways = rpre.get(floor);
			ways += lways * rways;
		}
	}
	return ways + 1; // process中没考虑都不选的情况,所以方法加1
}
function process(arr, index, w, end, bag, map) {
	if(w > bag) {
		return 0;
	}
	if(index > end) {
		if(w != 0) {
			if(!map.has(w)) {
				map.set(w, 1);
			} else {
				map.set(w, map.get(w) + 1);
			}
			return 1;
		} else {
			return 0;
		}
	} else {
		let ways = process(arr, index + 1, w, end, bag, map);
		ways += process(arr, index + 1, w + arr[index], end, bag, map);
		return ways;
	}
}
// 牛客js-v8 处理输入输出
let line1 = readline();
let line2 = readline();
let [n, w] = line1.split(' ').map(x => +x);
let v = line2.split(' ').map(x => +x);
let res = ways(v, w);
print(res);

发表于 2022-05-31 15:41:16 回复(0)
整体思路来自左程云老师的算法体系课。根据数据量猜解法。
自己使用了改写有序表简化了分治后的运算逻辑。但改写有序表的代码量也不少。-_-||

由于零食体积过大,使用动态规划肯定超时,但零食数量较小。分治后左右分别动态规划不会超时。

采用分治思想。
将arr分为左右两部分。
左右分别暴力枚举所有选择方法,
使用map收集所有方法的背包容量。(每种方法的背包容量都是不同的,超出w的就不要收集了)

定义ans收集答案。
遍历左侧结果集 
    当前背包容量为left 
    从右侧结果集种查出小于等于w-left的方法数funCount
    ans累加上funCount
返回ans
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int bag = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        long ways = ways(arr, bag);
        System.out.println(ways);
        sc.close();
    }

    /**
     * 分治统计有多少种零食的拿法。
     */
    private static long ways(int[] arr, int bag) {
        int N = arr.length;
        int mid = arr.length-1 >> 1;
        SBTSet<Long> leftSet = new SBTSet<>();
        process(arr, bag, 0, mid, 0L,leftSet);
        SBTSet<Long> rightSet = new SBTSet<>();
        process(arr, bag, mid+1, arr.length-1, 0L, rightSet);

        int ans = 0;
        for (int i = 0; i < leftSet.size(); i++) {
            Long leftWeight = leftSet.getIndexKey(i);
            ans += rightSet.lessEqualsCount(bag - leftWeight);
        }
        return ans;
    }

    /**
     * 当前来到i位置,背包内放入了preSum体积的零食,
     * 将i..end的所有选择后的体积放入set,但要求总体积不能超过bag
     * 如果当前来到end+1位置,set添加preSum后返回。
     * 尝试不拿当前位置零食,递归调用(i+1, preSum)
     * 如果arr[i]+preSum<=bag, 递归调用(i+1, preSum+arr[i])
     */
    private static void process(int[] arr, int bag, int i, int end, Long preSum, SBTSet<Long> set) {
        if(i == end+1){
            set.put(preSum);
            return;
        }
        process(arr, bag, i+1,end, preSum, set);
        if(arr[i]+preSum<=bag){
            process(arr, bag, i+1,end, preSum+arr[i], set);
        }
    }

    public static class SBTNode<K extends Comparable<K>>{
        public K key;
        public int all;
        public int size;
        public SBTNode l;
        public SBTNode r;
        public SBTNode(K k){
            key = k;
            size = 1;
            all = 1;
        }
    }

    public static class SBTSet<K extends Comparable<K>>{
        private SBTNode<K> root;

        public int size(){
            return getAll(root);
        }

        /**
         * 放入一个数据。
         */
        public void put(K key){
            root = add(root, key);
        }

        /**
         * 在cur树上新增节点,值为key。
         */
        private SBTNode<K> add(SBTNode<K> cur, K key) {
            if(cur==null) return new SBTNode<>(key);
            cur.all++;
            if(key.compareTo(cur.key)==0) return cur;
            if(key.compareTo(cur.key)<0){
                cur.l = add(cur.l, key);
            }else {
                cur.r = add(cur.r, key);
            }
            cur.size = getSize(cur.l)+getSize(cur.r)+1;
            return maintain(cur);
        }

        /**
         * 调整cur节点的平衡性并返回新节点。
         *
         */
        private SBTNode<K> maintain(SBTNode<K> cur) {
            int ls = getSize(cur.l);
            int lls = 0;
            int lrs = 0;
            if(cur.l != null){
                lls = getSize(cur.l.l);
                lrs = getSize(cur.l.r);
            }
            int rs = getSize(cur.r);
            int rrs = 0;
            int rls = 0;
            if(cur.r != null){
                rrs = getSize(cur.r.r);
                rls = getSize(cur.r.l);
            }

            if(lls>rs){
                cur = rightRotate(cur);
                cur.r = maintain(cur.r);
                cur = maintain(cur);
            }else if(lrs>rs){
                cur.l = leftRotate(cur.l);
                cur = rightRotate(cur);
                cur.l = maintain(cur.l);
                cur.r= maintain(cur.r);
                cur = maintain(cur);
            }else if(rrs>ls){
                cur = leftRotate(cur);
                cur.l = maintain(cur.l);
                cur = maintain(cur);
            }else if(rls>ls){
                cur.r = rightRotate(cur.r);
                cur = leftRotate(cur);
                cur.l = maintain(cur.l);
                cur.r = maintain(cur.r);
                cur = maintain(cur);
            }

            return cur;
        }

        /**
         * 左旋
         */
        private SBTNode<K> leftRotate(SBTNode<K> cur) {
            int same = cur.all - getAll(cur.l) - getAll(cur.r);
            SBTNode<K> right = cur.r;
            cur.r = right.l;
            right.l = cur;
            right.size = cur.size;
            cur.size = getSize(cur.l)+getSize(cur.r)+1;
            right.all = cur.all;
            cur.all = getAll(cur.l)+getAll(cur.r)+same;
            return right;
        }

        private int getAll(SBTNode<K> cur) {
            return cur==null?0:cur.all;
        }

        /**
         * 右旋
         */
        private SBTNode<K> rightRotate(SBTNode<K> cur) {
            int same = cur.all - getAll(cur.l) - getAll(cur.r);
            SBTNode left = cur.l;
            cur.l = left.r;
            left.r = cur;
            left.size = cur.size;
            cur.size = getSize(cur.l)+getSize(cur.r)+1;
            left.all = cur.all;
            cur.all = getAll(cur.l)+getAll(cur.r)+same;
            return left;
        }

        private int getSize(SBTNode cur) {
            return cur==null?0:cur.size;
        }

        /**
         * 返回小于等于指定值的个数。
         * 从root开始向下滑。
         * 等于返回答案。
         * 向右滑收集答案。
         * 向左滑不收集。
         */
        public int lessEqualsCount(K key){
            SBTNode<K> cur = root;
            int ans = 0;
            while (cur!=null){
                if(key.compareTo(cur.key)==0) return ans+cur.all-getAll(cur.r);
                if(key.compareTo(cur.key)<0){
                    cur = cur.l;
                }else {
                    ans += cur.all-getAll(cur.r);
                    cur = cur.r;
                }
            }
            return ans;
        }

        /**
         * 返回排序后位于指定位置的key
         * 检查key是否超出集合范围。
         * 从root向下滑。
         * 如果小于左树all范围,来到左树找。
         * 如果大于等于cur.all-右树.all,去右树找。
         * 否则,返回当前值。
         */
        public K getIndexKey(int index){
            if(index<0 || index>=getAll(root)) throw new RuntimeException("out of range");
            return getIndex(root, index).key;
        }

        /**
         * 返回cur树上的第k个节点。
         */
        private SBTNode<K> getIndex(SBTNode<K> cur, int index){
            if(index<getAll(cur.l)){
                return getIndex(cur.l, index);
            }else if(index >= cur.all-getAll(cur.r)){
                return getIndex(cur.r, index-(cur.all-getAll(cur.r)));
            }else {
                return cur;
            }
        }
    }
}


发表于 2022-03-09 16:51:30 回复(0)
#python
#思路:大于背包的过滤掉,背包很大的时候直接求幂,其他情况dfs
N,W = map(int,input().split())
nums = list(map(int,input().split()))
def judgge(x):
    return x<=W
nums = list(filter(judgge,nums))
N = len(nums)

total = sum(nums)
count = 0
def dfs(t,sum):
    global count
    if sum>W:
        return
    if t==N:
        count+=1
        return
    dfs(t+1,sum+nums[t])
    dfs(t + 1, sum)
    return



if total<=W:
    print(2**N)
else:
    dfs(0,0)# 第i号物品,当前重量
    print(count)

发表于 2020-08-05 15:02:54 回复(0)
发现自己就是个彩笔,没任何对数据范围的概念,int的范围是2*10^9的靠右一点,题目的v+w最大可以取到3*10^9,这就可能越界,所以我的算法就错了,只能改成减法不能用加法,害 这个数据范围 害
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n=sc.nextInt();
		int w=sc.nextInt();
		int[] v=new int[n+1];
		for(int i=1;i<=n;i++) {
			v[i]=sc.nextInt();
		}
		//初始化
		int[][] dp=new int[n+1][w+1] ;
//		for(int i=0;i<n+1;i++) {
//			for(int j=0;j<w+1;j++) {
//				dp[i][j]=1;
//			}
//		}
        int res=0;
		dp[1][w]=1;
		for(int i=0;i<=w;i++) {
			if(i==w-v[1]) {
				dp[1][i]=1;
			}
		}
        if(n==1){
            if(v[1]<=w){
                System.out.println(2);
            }else{
                System.out.println(1);
            }
            return ;
        }else{
            for(int i=2;i<=n;i++) {
			for(int k=0;k<=w;k++) {
				dp[i][k]=dp[i-1][k]+(k+v[i]<=w?dp[i-1][v[i]+k]:0);
                //我估计就是这个v[i]+k  导致越界了
			}
		}
//		for(int i=1;i<=n;i++) {
//			for(int k=0;k<=w;k++) {
//				System.out.print(dp[i][k]+" ");
//			}
//			System.out.println();
//		}
		
		for(int i=0;i<=w;i++) {
			res+=dp[n][i];
		}
		System.out.println(res);
        }
		
	}
}



发表于 2020-07-16 11:38:43 回复(1)
// 枚举前n/2个物品的组合,按体积排好序
// 枚举后n/2个物品的组合,在排好序的组合里面二分查找
// 总复杂度O(n/2*2^(n/2))
#include <bits/stdc++.h> using namespace std; int v[35]; int main() {     int n, w;     scanf("%d%d", &n, &w);     for (int i = 0; i < n; i++)         scanf("%d", v + i);     int ans = 0;     int lcnt = n / 2, rcnt = n - n / 2;     vector<long long> sorted;     for (int s = 0; s < (1 << lcnt); s++)     {         long long cur = 0;         for (int i = 0; i < lcnt; i++)             if (s >> i & 1)                 cur += v[i];         sorted.push_back(cur);     }     sort(sorted.begin(), sorted.end());     for (int s = 0; s < (1 << rcnt); s++)     {         long long cur = 0;         for (int i = 0; i < rcnt; i++)             if (s >> i & 1)                 cur += v[lcnt + i];         cout << cur << endl;         ans += upper_bound(sorted.begin(), sorted.end(), w - cur) - sorted.begin();     }     printf("%d", ans);     return 0; }
发表于 2019-02-12 15:02:37 回复(0)
#include <iostream>
#include <fstream>

using namespace std;

int sum = 0;
int res =0;
bool *marked;
int n , m;

 void getCount(int * v , int w, int d){
        if (v[d] + sum > w) {
            return;
        }
        marked[d] = true;
        res++;
        sum += v[d];
        for (int i = d; i < n; ++i) {
            if (!marked[i]) {
                getCount(v, w, i);
            }
        }
        sum -= v[d];
        marked[d] = false;
}

int main(){
    
    cin>>n>>m;
    int * arr = new int[n];
    marked = new bool[n];
    for(int i = 0;i<n;++i){
        int temp ;
        cin>>temp;
        arr[i] = temp;
        marked[i]= false;
    }    
    for(int i = 0; i <n;++i){
        getCount(arr, m, i);
    }
    printf("%d",res+1);
}
发表于 2018-07-19 20:26:17 回复(0)
这个Hint做得不太好啊。
发表于 2018-07-06 11:57:06 回复(0)
package test;

import java.util.Scanner;
import java.io.*;
public class test{
    static int n=0;
    static long[] v=new long[40];
    static long ans=0;
    static long w;
     
         public static void dfs( int t ,long sum) {
        
                if(sum>w)
                {
                    return ;
                }
                /*    else
                {
                    ans++;
                }*/
            /* if(sum<w&&sum+v[t]>w)
                {
                    ans++;
                    return ;
                }*/
                if(t==n)
                {
                    ans++;
                    return ;
                }
                
                dfs(t+1,(sum+v[t]));
                
                dfs(t+1,sum);
            
                
            }             
    
    public static void main (String[] args){
        Scanner scanner = new Scanner(System.in);
         n = scanner.nextInt();
         w = scanner.nextLong();
        long sum=0;
        
        for(int j=0;j<n;j++)
        {
            v[j]= scanner.nextLong();
            sum+=v[j];
        }
        if(sum<=w)
        {
            ans=1<<n;
        }
        else
        {
            dfs(0,0);
        }
        System.out.print(ans);
    }
    
}
发表于 2018-06-13 16:00:16 回复(0)