[编程题]多重背包
参考了很多大佬的Java和c++代码，前端狗的JavaScript版本来了！
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
// Write your code here
const arr1 = (await readline()).split(" ");
const capacity = parseInt(arr1[0]);
const n = parseInt(arr1[1]);
const amounts = [];
const weights = [];
const values = [];
for (let i = 0; i < n; i++) {
let tokens = (await readline()).split(" ");
amounts.push(parseInt(tokens[0]));
weights.push(parseInt(tokens[1]));
values.push(parseInt(tokens[2]));
}
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < n; i++) {
if (weights[i] >= capacity) {
zero_oneBP(1);
}
let k = 1;
while (k <= amounts[i]) {
zero_oneBP(k);
amounts[i] -= k;
k = k * 2;
}
if (amounts[i] > 0) zero_oneBP(amounts[i]);
function zero_oneBP(k) {
for (
let remain_v = capacity;
remain_v >= k * weights[i];
remain_v--
) {
let temp = k * values[i] + dp[remain_v - k * weights[i]];
dp[remain_v] = Math.max(temp, dp[remain_v]);
}
}
}
console.log(dp[capacity]);
})();
发表于 2023-03-19 22:41:12
回复(0)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int v = sc.nextInt();
int m = sc.nextInt();
int []num = new int[m];
int []vArr = new int[m];
int []value = new int[m];
for(int i=0;i<m;i++){
num[i] = sc.nextInt();
vArr[i] = sc.nextInt();
value[i] = sc.nextInt();
}
int [] dp = new int[v+1];
for(int i=0;i<m;i++){
if(num[i]*vArr[i]>=v){
for(int j=vArr[i];j<=v;j++){
dp[j] = Math.max(dp[j],dp[j-vArr[i]]+value[i]);
}
}else{
int k=1;
int temp=num[i];
while(k<temp){
int v_tmp =k*vArr[i];
for(int j=v; j>=v_tmp;j--){
dp[j] = Math.max(dp[j],dp[j-v_tmp]+k*value[i]);
}
temp -=k;
k*=2;
}
for(int j=v; j>=temp*vArr[i];j--){
dp[j] = Math.max(dp[j],dp[j-temp*vArr[i]]+temp*value[i]);
}
}
}
System.out.println(dp[v]);
}
} 中间对数量进行了判断，当用不完的时候相当于完全背包，就用完全背包去解。毕竟完全背包这边不用拆分，时间上会短点。然后01背包用了二进制优化
发表于 2021-06-23 21:59:23
回复(0)
//多重背包拆成01背包，以及优化为1维
# include <iostream>
# include <vector># include <algorithm>
using namespace std;
struct Pair
{
int v;
int w;
};
int main(void)
{
int i;
int j;
int n;
int V;
cin >> V >> n;
if (n == 0 || V == 0)
return 0;
int v;
int w;
int s;
vector<struct Pair> good;
struct Pair * temp;
for (i = 1; i <= n; i++)
{
cin >> s >> v >> w;
//需要把s[i]拆成 log(s[i]) + 1(如果剩余) 份
for (j = 1; j <= s; s-= j, j *= 2) //二进制拆法
{
temp = new Pair();
temp->v = v * j; //体积
temp->w = w * j; //价值
good.push_back(*temp);
}
if (s != 0)
{
temp = new Pair();
temp->v = v * s; //体积
temp->w = w * s; //价值
good.push_back(*temp);
}
}
//需要拆成一份一份，然后放到数组中，最后变成一个01背包问题，选和不选两种选择
n = good.size();
vector<int> f(V + 1, 0); //体积还是不变，只是物品的数量变多了
for (i = 1; i <= n; i++) //需要优化为1维，否则内存会超
{
for (j = V; j >= good[i - 1].v; j--)
{
if (good[i - 1].v <= j)
f[j] = max(f[j], f[j - good[i - 1].v] + good[i - 1].w);
}
}
cout << f[V] << endl;
return 0;
}
编辑于 2020-08-15 21:32:36
回复(0)
好奇怪，我的自测用例和在acwing的多重背包练习中能ac，提交之后无法通过。。。
w,n = map(int,input().split()) try: goods = [] while n: n-=1 goods.append(list(map(int,input().split()))) n = len(goods) new_goods= [] for i in range(n): for j in range(goods[i][0]): new_goods.append([goods[i][1],goods[i][2]])#体积，价值 #goods.clear() n = len(new_goods) #重新定义总数量 #01 背包 dp = [0]*(w+1) #第i个物品总容量为j时最大价值 for i in range(1,n+1): for j in range(w,new_goods[i-1][0]-1,-1): dp[j] = max(dp[j],dp[j-new_goods[i-1][0]]+new_goods[i-1][1]) print(dp[-1]) except: pass
编辑于 2020-08-05 15:49:44
回复(0)
/*
第一行两个整数V和m。
接下来m行，每行3个整数，表示第i种物品的数量、体积和价值。
V≤104, m≤500V\leq10^4,\ m≤500V≤104, m≤500，个数、体积、价值不超过1000。
*/
#include<iostream>
(720)#include<vector>
using namespace std;
int main() {
int V, M; //体积为V 有m种物品
cin >> V >> M;
vector<std::pair<int, int>> goods; //物品的体积 物品的价值
for (int i = 0; i < M; ++i) {
int num, v, value;
cin >> num >> v >> value;
int n = 1; //物品分块的数量
while (n <= num) { // n应当小于1
goods.push_back({n * v, n * value});
num -= n;
n <<= 1;
}
if (num != 0)
goods.push_back({num * v, num * value});
}
// dp[i][v]//选择第i次后 体积为v时的最大价值
vector<int> dp(V + 1, 0);
for (int i = 1; i <= goods.size(); ++i) {
for (int j = V; j > 0; --j) {
if (j >= goods[i - 1].first)
dp[j] = max(dp[j], dp[j - goods[i - 1].first] + goods[i - 1].second);
}
}
cout << dp.back() << endl;
return 0;
}
发表于 2020-04-24 18:53:34
回复(0)
//ac多重背包转换01背包
//如何拆分？10个可以拆封成 1 2 4 还剩3个
//不管怎么样，拆分后可以还原（0-10）每一种情况
#include <iostream>
using namespace std;struct E{
int w; //体积
int v; //重量
}lis[20005];
int dp[20005];
int Max(int a,int b){
return a>b?a:b;
}
int main(){
int n,m;
int k,p,h;
cin>>n>>m;
int index = 0; //拆分后物品总数
for(int i=1;i<=m;i++){
cin>>k>>p>>h; //数量\体积\重量
int c = 1;
while(k-c>0){ //拆分
k -= c;
lis[++index].w = c*p;
lis[index].v = c*h;
c*= 2;
}
lis[++index].w = p*k; //补充不足指数的差值
lis[index].v = h*k;
}
for(int i=1;i<=index;i++){ //0-1背包
for(int j=n;j>=lis[i].w;j--)
dp[j]=Max(dp[j],dp[j-lis[i].w]+lis[i].v);
}
cout<<dp[n]<<endl;
return 0;
}
发表于 2019-09-11 16:02:30
回复(0)
#include <bits/stdc++.h>
using namespace std;
struct item
{
int w;
int v;
} l[10000];
int dp[10001];
int main()
{
int maxv, n;
while (cin >> maxv >> n)
{
int cnt = 0;
for (int i = 0; i < n; i++)
{
int v, w, k;
cin >> k >> w >> v;
int temp = 1;
while (k - temp > 0)
{
k -= temp;
l[++cnt].w = temp * w;
l[cnt].v = temp * v;
temp *= 2;
}
l[++cnt].w = w * k;
l[cnt].v = v * k;
}
for (int i = 0; i <= maxv; i++)
{
dp[i] = 0;
}
for (int i = 1; i <= cnt; i++)
{
for (int j = maxv; j >= l[i].w; j--)
{
dp[j] = max(dp[j], dp[j - l[i].w] + l[i].v);
}
}
cout << dp[maxv];
}
return 0;
}
发表于 2019-09-08 21:11:25
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int total = sc.nextInt();
int n = sc.nextInt();
int num[] = new int[n];
int m[] = new int[n];
int v[] = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
m[i] = sc.nextInt();
v[i] = sc.nextInt();
// System.out.println('s');
}
long[] dp = new long[total + 1];
// for (int i = 1; i * c[i] < total && i <= b[i]; i++) {
// dp[0][i * c[i]] = i * d[i];
//}
for (int i = 0; i < n; i++) {
int t=Math.min(total/m[i],num[i]);//取数量最大值
for (int k = 1;t>0;k<<=1) {//数量二进制分组
if(k>t)k=t;
t-=k;
for (int j =total; j>=k*m[i]; j--) {
dp[j] = Math.max(dp[j - k*m[i]] + k*v[i], dp[j]);
}
}
}
System.out.println(dp[total]);
}
}
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int total = sc.nextInt();
int n = sc.nextInt();
int num[] = new int[n];
int m[] = new int[n];
int v[] = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
m[i] = sc.nextInt();
v[i] = sc.nextInt();
// System.out.println('s');
}
long[] dp = new long[total + 1];
// for (int i = 1; i * c[i] < total && i <= b[i]; i++) {
// dp[0][i * c[i]] = i * d[i];
//}
for (int i = 0; i < n; i++) {
int t=Math.min(total/m[i],num[i]);//取数量最大值
for (int k = 1;t>0;k<<=1) {//数量二进制分组
if(k>t)k=t;
t-=k;
for (int j =total; j>=k*m[i]; j--) {
dp[j] = Math.max(dp[j - k*m[i]] + k*v[i], dp[j]);
}
}
}
System.out.println(dp[total]);
}
}
发表于 2019-08-11 11:19:50
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int V;
void zeroonepack(vector<int> &result, vector<int> v, vector<int> value, int i)
{
for (int j = V; j >= v[i]; --j)
j < v[i] ? result[j] = result[j] : result[j] = max(result[j], result[j - v[i]] + value[i]);//放不下第i个物体
return;
}
int main()
{
int n, temp1, temp2, temp3, k = 1;//背包体积V，n组数
cin >> V >> n;
vector<int> num(n + 1, 0),v(1, 0), value(1, 0), result(V + 1, 0);/*v是物体体积，value是物体价值。result[i]表示前i个物品，
放到v中最大价值,需要初始化为0。如果需要刚好放满背包，除了第0个元素，其他要初始化为负无穷。v和value只申请一个是因为第0个要为0*/
for (int i = 1; i <= n; ++i)
{
cin >> temp1 >> temp2 >> temp3;
num[i] = temp1;
while (k < num[i])//未进入循环的时候，即等于原num[i]-2^k+1
{
v.push_back(k*temp2);
value.push_back(k*temp3);
num[i] -= k;
k = k * 2;
}
v.push_back(num[i] * temp2);
value.push_back(num[i] * temp3);//补差值
k=1;
}
for (int i = 1; i <= v.size(); ++i)//二进制优化01背包后，有v.size()个物品
zeroonepack(result, v, value, i);
cout << result[V] << endl;
return 0;
}
发表于 2019-08-05 20:09:28
回复(0)
/*** @author: karlmical* @date: 20190805**/#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>#include <string>#include <sstream>#include <string.h>using namespace std;const int MAXV = int(1e4) + 5;const int MAXN = 1000 + 1;int dp[MAXV];int capacity[MAXN], vol[MAXN], value[MAXN];void zeroone_knapsack(int limit, int i, int k){const int w = k * vol[i];for (int j = limit; j >= w; j--){int nv = dp[j - w] + k * value[i];if (nv > dp[j]){dp[j] = nv;}}}int multi_knapsack(int n, int limit){//initmemset(dp, 0, sizeof(int) * (n + 1));for (int i = 1; i <= n; i++){if (vol[i] * capacity[i] >= limit){for (int j = vol[i]; j <= limit; j++){int nv = dp[j - vol[i]] + value[i];if (nv > dp[j]){dp[j] = nv;}}}else{int k = 1, res = capacity[i];while (k < res){zeroone_knapsack(limit, i, k);res -= k;k <<= 1;}zeroone_knapsack(limit, i, res);}}return dp[limit];}int main(){int v, m;cin >> v >> m;for (int i = 1; i <= m; i++){cin >> capacity[i] >> vol[i] >> value[i];}cout << multi_knapsack(m, v);return 0;}
编辑于 2019-08-05 15:04:31
回复(1)
import java.util.Arrays; import java.util.Scanner; import java.util.ArrayList; /** * @Classname BeiBao_01 * @Description 有N中类型的商品,每一个有自己的体积w[i],价值v[i],容量是V,求最大的价值W * 注意:这是一个01背包问题,每一件商品只有1个,多重背包转换为01背包 * @Date 19-6-9 下午7:34 * @Created by mao<tianmao818@qq.com> */ public class Main { public static void main(String[] args){ Scanner sc=new Scanner(System.in); while (sc.hasNext()){ int W=sc.nextInt(); //容量 int N=sc.nextInt(); //代价 ArrayList<Integer> w=new ArrayList<>(); //价值 ArrayList<Integer> v=new ArrayList<>(); for(int i=0;i<N;i++){ //数量 int a=sc.nextInt(); //体积 int b=sc.nextInt(); //价值 int c=sc.nextInt(); for(int k=0;k<a;k++){ w.add(b); v.add(c); } } N=w.size(); int[] f=new int[W+1]; for (int i=0;i<N;i++){ for(int j=W;j>=w.get(i);j--){ //前i个商品对应不同容器的最大价值 f[j]=Math.max(f[j],f[j-w.get(i)]+v.get(i)); } } System.out.println(f[W]); } } }
发表于 2019-06-09 21:12:15
回复(2)
问题信息
通过挑战的用户
-
2023-03-11 22:56:10 -
2023-03-09 13:20:46
-
2023-03-06 22:45:18 -
2023-02-17 14:06:07 -
2023-02-14 22:51:14
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-84873384 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
