多重背包

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]);
    }
}

/*
第一行两个整数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;
}

#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;
}

#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;
}

	
	

		/** 
	

	

		 * @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) 
	

	

		{ 
	

	

		 //init 
	

	

		 memset(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; 
	

	

		} 
	

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]);
        }
    }
}