首页 > 试题广场 >

牛牛的背包问题

[编程题]牛牛的背包问题
  • 热度指数:165 时间限制: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种情况。
_, w = input("").split()
w = int(w)
arr = [int(i) for i in input("").split()]

from functools import lru_cache

@lru_cache()
def process(ind, rest):
    if rest < 0:
        return 0
    if ind == len(arr):
        return 1
    return process(ind + 1, rest) + process(ind + 1, rest - arr[ind])

print(process(0, w))


发表于 2022-10-17 14:22:57 回复(0)
python 回溯解法, 80%通过,超时? 难道所有语言用的一个时间限制?还是我写的有错误?有没有大佬帮忙看一下?。
这种题最好先画一下遍历树,我们知道通过递归就能遍历整棵树(也就是查看到所有的情况)。但是有些情况是我们不需要的(剪枝条件:零食体积大于背包容量),所以我们排除这些情况就能得到所有符合条件的情况。(可以去leetcode上看看有关回溯的题型)。


def main():
    # get input 
    n, w = map(int, input().split())
    v = list(map(int, input().split()))
    assert len(v) == n, "invalid input !"
    
    # 当全部零食都能装下,也就是不需要剪枝,那么递归耗时太大,可以直接用公式计算
    if sum(v) <= w: 
        print(2 ** n)
        return
    
    # backtrack function
    global cnt
    cnt = 0
    def backtrack(s=0, res=[]):
        if sum(res[:]) <= w:
            global cnt
            cnt += 1
        for i in range(s,n):
            res.append(v[i])
            backtrack(i+1, res)
            res.pop()
    # get ans
    backtrack()
    print(cnt)
    
                
if __name__ == "__main__":
    main()


发表于 2020-08-07 10:34:17 回复(0)

a = input().split(' ')
b = input().split(' ')

n = int(a[0])
w = int(a[1])
v = list(map(int, b))
v = sorted(v)

alls = 1
crrw = 0
i = 0


def count(i):
    global crrw,alls

    if i >= n or i<0:
        return
    else:
        if crrw + v[i] <= w: 
            crrw += v[i]
            alls += 1
            count(i+1)
            crrw -= v[i]
            count(i+1)

count(0)
print(alls)

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为80.00%
发表于 2020-04-08 19:21:32 回复(0)
深度优先搜索,数组排序后,从小于等于背包容量的第一种零食开始,往前推,尽可能放下最多零食,当放不下后,返回上一步,但一开始只能通过80%测试用例,后来发现当所有零食总和都小于背包容量时计算了2^n次,该情况应该单独考虑
#include<iostream>
#include<algorithm>
using namespace std;
void count(long long int v[], int& res, long long int w, int right);
int main(){
    int n;
    long long int w;
    cin>>n>>w;
    long long int v[n];
    for(int i=0;i<n;i++) cin>>v[i];
    int res=1;
    sort(v,v+n);
    long long int sum = 0;
    for(int i=0;i<n;i++) sum += v[i];
    if(sum<=w) res = pow(2,n);
    else count(v,res,w,n);
    cout<<res<<endl;
    
}
void count(long long int v[], int& res, long long int w, int right){
    //int pos = right;
    //while(v[pos]>w) pos--;
    int pos = upper_bound(v,v+right,w) - v;
    pos--;
    
    for(int i=pos;i>=0;i--){
        res++;
        if(i-1>=0 && w-v[i]>0) count(v,res,w-v[i],i);
    }
}


编辑于 2020-03-14 11:08:59 回复(0)