NC54710. 背包问题
描述
输入描述
第一行两个整数，表示物品的数量和总体积需求。
接下来行，每行两个整数
，表示第
种物品的体积和价值。保证所有物品总体积不小于
。
。保证所有物品总体积不小于
输出描述
输出一个整数，表示答案。
示例1
输入:
3 6 2 5 3 4 4 3
输出:
7
说明:
选择第2和第3个物品。示例2
输入:
6 10 2 4 3 4 4 5 5 11 6 10 7 11
输出:
15
说明:
选择第3和第5个物品，或者第2和第6个物品。pypy3(pypy3.6.1) 解法, 执行用时: 73ms, 内存消耗: 19624K, 提交时间: 2021-04-17 11:17:51
N, V = map(int, input().split())
f = []
v = [0]
w = [0]
max_w = 0
for i in range(1, N + 1):
a, b = map(int, input().split())
max_w += b
v.append(a)
w.append(b)
f = [0] * (max_w + 1)
for i in range(1, N + 1):
for j in range(max_w, w[i] - 1, -1):
f[j] = max(f[j], f[j - w[i]] + v[i])
for i in range(len(f)):
if f[i] >= V:
print(i)
break
Python3(3.5.2) 解法, 执行用时: 1573ms, 内存消耗: 4420K, 提交时间: 2019-12-14 23:42:08
n, V = [int(x) for x in input().split()]
v = []
w = []
for i in range(n):
vi, wi =[int(x) for x in input().split()]
v.append(vi)
w.append(wi)
ws = sum(w)
f = [0 for i in range(ws+1)]
tmp = 0
for vi, wi in zip(v,w):
tmp += wi
for j in range(tmp, wi-1, -1):
f[j] = max(f[j], f[j-wi]+vi)
ans = 0
while f[ans] < V:
ans += 1
print(ans)
C++(clang++ 11.0.1) 解法, 执行用时: 242ms, 内存消耗: 4360K, 提交时间: 2023-07-08 17:15:46
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N=202;
int n,V;
vector<int>dp(1000000,INF);
int v[N],w[N];
void solve()
{
for(int i=1;i<=n;i++)
for(int j=V;j>=0;j--)
dp[j]=min(dp[j],dp[max(0,j-v[i])]+w[i]);
}
int main()
{
cin>>n>>V;
dp[0]=0;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
solve();
cout<<dp[V]<<endl;
}