资产包打包

0,1背包为题动态规划的详细解析原博客地址(https://blog.csdn.net/mu399/article/details/7722810)
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

首先要明确这张表是至底向上，从左到右生成的。

为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。

对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。

同理，c2=0，b2=3,a2=6。

对于承重为8的背包，a8=15,是怎么得出的呢？

根据01背包的状态转换方程，需要考察两个值，

一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi；

在这里，

f[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值

f[i-1,j-Wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值

f[i-1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6

由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a应该放入承重为8的背包

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = bf.readLine().split(",");
        int m = Integer.parseInt(strs[0]);//可容纳的资产 条
        int n = Integer.parseInt(strs[1]);//资产种类
        String[] sp1 = strs[2].split(" ");
        String[] sp2 = strs[3].split(" ");
        int[] kinds = new int[n];
        int[] prices = new int[n];
        for (int i = 0; i < sp1.length; i++) {
            kinds[i] = Integer.parseInt(sp1[i]);
            prices[i] = Integer.parseInt(sp2[i]);
        }
        //动态规划
        int[][] dp = new int[n + 1][m + 1];//dp[i][j]，资产种类为i，背包重量为j
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //放入第i个种类的物品，该背包的剩余重量比i类物品的重量大或者相等
                //dp[i - 1][j] 为背包重量为j,不放入第i个物品的最大价值，
                // 和放入第i个物品时候的价值+前面i-1类中背包容量为j-
                /**
                 * dp[i - 1][j] 为背包重量为j,不放入第i个物品的最大价值
                 * dp[i - 1][j - kinds[i - 1]] + prices[i - 1] 为放入第i个物品+前i-1个物品中背包容量为j-i物品的重量的最大值
                 */
                if (j - kinds[i - 1] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - kinds[i - 1]] + prices[i - 1]);
                }else {//该类物品的重量大于背包的剩余重量了，装不下
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

/*
0-1背包问题，考虑动态规划，
设dp[n][m]为用前n件物品占用m空间，可以获得的最大价值。
其最大价值等于1、2最大值：1、不选最后一件物品所获价值，2、选择最后一件物品所获价值
dp[n][m] = max(dp[n-1][j],dp[n-1][j-t]+v) ，t为n物品占用空间，v为n物品价值。
*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
//    freopen("input.txt", "r", stdin);
    int m, n, i, j;
    char c;
    cin >> m >> c >> n >> c;
    int t[n + 1], v[n + 1];
    for(i = 1; i <= n; i++) cin >> t[i];
    cin >> c;
    for(i = 1; i <= n; i++) cin >> v[i];

    int dp[n + 1][m + 1];
    memset(dp, 0, sizeof(dp));
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if(t[i] <= j) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - t[i]] + v[i]);
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    cin>>m;getchar();cin>>n;getchar();
    int zl[n+1],vl[n+1];
    for(int i=1;i<=n;i++)    cin>>zl[i];
    getchar();
    for(int i=1;i<=n;i++)    cin>>vl[i];
    int f[n+1][m+1];
    memset(f, 0, sizeof(f));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<zl[i];j++)
        {
            f[i][j]=f[i-1][j];
        }
        for(int j=zl[i];j<=m;j++)
        {
            f[i][j]=max(f[i-1][j],f[i-1][j-zl[i]]+vl[i]);
        }
    }
    cout<<f[n][m]<<endl;
}

记忆化搜索

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(",");
        int capacity = Integer.parseInt(params[0]);
        int types = Integer.parseInt(params[1]);
        String[] strs = params[2].split(" ");
        int[] limits = new int[types];
        for(int i = 0; i < types; i++){
            limits[i] = Integer.parseInt(strs[i]);
        }
        strs = params[3].split(" ");
        int[] values = new int[types];
        for(int i = 0; i < types; i++){
            values[i] = Integer.parseInt(strs[i]);
        }
        int[][] dp = new int[types][capacity + 1];
        System.out.println(dfs(0, limits, values, capacity, dp));
    }
    
    private static int dfs(int index, int[] limits, int[] values, int rest, int[][] dp) {
        if(index == values.length || rest <= 0){
            return 0;      // 到头了或当前资产拿不了了
        }
        if(dp[index][rest] > 0){
            return dp[index][rest];
        }
        // 不选当前的资产
        int p1 = dfs(index + 1, limits, values, rest, dp);
        // 选当前的资产
        int p2 = 0;
        if(rest >= limits[index])
            p2 = values[index] + dfs(index + 1, limits, values, rest - limits[index], dp);
        dp[index][rest] = Math.max(p1, p2);
        return dp[index][rest];
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(",");
        int capacity = Integer.parseInt(params[0]);
        int types = Integer.parseInt(params[1]);
        String[] strs = params[2].split(" ");
        int[] limits = new int[types];
        for(int i = 0; i < types; i++){
            limits[i] = Integer.parseInt(strs[i]);
        }
        strs = params[3].split(" ");
        int[] values = new int[types];
        for(int i = 0; i < types; i++){
            values[i] = Integer.parseInt(strs[i]);
        }
        int[] dp = new int[capacity + 1];
        for(int index = 0; index < types; index++){
            for(int rest = capacity; rest >= limits[index]; rest--){
                dp[rest] = Math.max(dp[rest], values[index] + dp[rest - limits[index]]);
            }
        }
        System.out.println(dp[capacity]);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int m,n;
    char c;
    cin>>m>>c>>n>>c;
    int w[n+1], v[n+1];
    for(int i=1;i<=n;i++)
        cin>>v[i];
    cin>>c;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            dp[i][j] = dp[i-1][j];
            if(j>=v[i])
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]]+w[i]);
        }
    cout<<dp[n][m]<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main(){
    int m,n;
    scanf("%d,%d,",&m,&n);
    vector<int> num(n,0),value(n,0);
    vector<vector<int>> dp(n,vector<int>(m+1,0));
    for(int i=0;i<n;i++)
        cin>>num[i];
    cin.ignore();
    for(int i=0;i<n;i++)
        cin>>value[i];
    for(int j=0;j<=m;j++)
        if(j>=num[0])
            dp[0][j]=value[0];
    for(int i=1;i<n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(j>=num[i])
                dp[i][j]=max(dp[i][j],dp[i-1][j-num[i]]+value[i]);
        }
    }
    cout<<dp[n-1][m];
    return 0;
}

01背包 处理好边界就行了

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

int package01(const int & total,vector<int>&weight,vector<int>&value) {

    vector<vector<int>>dp(weight.size()+1,vector<int>(total+1,0));
    for (int i = 1;i < weight.size();++i) {
        for (int j = 1;j <= total ;++j) {

            if (weight[i] <=j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[weight.size()-1][total];
}
int main() {
    int total, number;
    char c;
    cin >> total >>c >> number>>c;


    vector<int>weight(number + 1, 0),values(number+1,0);
    for (unsigned int i = 0;i < number;++i) {
        cin >> weight[i + 1];

    }

    cin >> c;
    for (unsigned int i = 0;i < number;++i) {
        cin >> values[i + 1];

    }

    cout << package01(total,weight,values);
    system("pause");
    return 0;
}

#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <stack>
#include <map>
#include <list>
#include <ctime>
#include <queue>
#include <unordered_map>
#include <unordered_set>

class Solution {
public:
    //递归+剪枝
    int dfs(int total, size_t index, vector<int>& cost, vector<int>& values, vector<vector<int>>& record) {
        if (total < 0) {
            return -1;
        }
        if (index == cost.size()) {
            return 0;
        }
        if (record[total][index] != -1) {
            return record[total][index];
        }
        int unuse = dfs(total, index + 1, cost, values, record);
        int use = dfs(total - cost[index], index + 1, cost, values, record);
        if (use != -1) {
            use += values[index];
        }
        record[total][index] = max(use, unuse);
        return record[total][index];
    }
    
    int getMaxMoney(int total, vector<int>& cost, vector<int>& values) {
        vector<vector<int>> record(total + 1, vector<int>(cost.size(), -1));
        return dfs(total, 0, cost, values, record);
    }
    
    //动态规划
    int getMaxMoneyDp(int total, vector<int>& costs, vector<int>& values) {
        int n = costs.size();
        vector<vector<int>> dp(n + 1, vector<int>(total + 1, 0));
        for (int index = n - 1; index >= 0; index--) {
            for (int rest = 0; rest <= total; rest++) {
                int unuse = dp[index + 1][rest];
                int use = rest - costs[index] < 0 ? -1 : dp[index + 1][rest - costs[index]];
                if (use != -1) {
                    use += values[index];
                }
                dp[index][rest] = max(use, unuse);
            }
        }
        return dp[0][total];
    }
};

int main() {
    char temp;
    int total;
    int nums;
    cin >> total >> temp >> nums >> temp;
    vector<int> cost(nums);
    for (int i = 0; i < nums; i++) {
        cin >> cost[i];
    }
    cin >> temp;
    vector<int> values(nums);
    for (int i = 0; i < nums; i++) {
        cin >> values[i];
    }
    cout << Solution().getMaxMoneyDp(total, cost, values) << endl;
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		while(in.hasNext()) {
			String[] s=in.nextLine().split(",");
			int capacity=Integer.valueOf(s[0]);
			int num=Integer.valueOf(s[1]);
			List<int[]> items=new ArrayList<>();
			String[] w = s[2].split(" ");//重量
			String[] v = s[3].split(" ");//价值
			for(int i=0;i<w.length;i++) {
				int[] item=new int[2];
				item[0]=Integer.valueOf(w[i]);
				item[1]=Integer.valueOf(v[i]);
				items.add(item);
			}
			
			int res = maxValueByXiaomi(capacity, items);
			System.out.println(res);
		}
	}
	//小米资产打包
	//总量m=12,种类n=3,重量w分别为4,5,7,价值v分别为500,600,800
	public static int maxValueByXiaomi(int capacity,List<int[]> items) {
		int n=items.size();
		int[][] dp=new int[n+1][capacity+1];//初始化0行0列方便dp
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=capacity;j++) {
				dp[i][j]=(items.get(i-1)[0]>j)?
						dp[i-1][j]:Math.max(dp[i-1][j], dp[i-1][j-items.get(i-1)[0]]+items.get(i-1)[1]);
			}
		}
		return dp[n][capacity];
	}
}

#include <iostream>
(720)#include <vector>
#include <cmath>
using namespace std;
int main(){
    int n,m;
    char c;
    cin>>n>>c>>m>>c;
    int *space=new int[m+1],*value=new int[m+1];
    for (int i=1;i<=m;i++) cin>>space[i];
    cin>>c;
    for (int i=1;i<=m;i++) cin>>value[i];
    vector<vector<int>> dp(m+1,vector<int>(n+1));
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            dp[i][j]=max(dp[i-1][j],j>=space[i]?dp[i-1][j-space[i]]+value[i]:0);
    cout<<dp[m][n];
}

// code2:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main(){
    int n,m;
    char c;
    cin>>n>>c>>m>>c;
    int *space=new int[m],*value=new int[m];
    for (int i=0;i<m;i++) cin>>space[i];
    cin>>c;
    for (int i=0;i<m;i++) cin>>value[i];
    int *ans=new int[n+1];
    for (int i=0;i<m;i++)
        for (int j=n;j>=space[i];j--){
            ans[j]=max(ans[j],ans[j-space[i]]+value[i]);
        }
   cout<<ans[n];
}

import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] strs = line.split(",");
        int c = Integer.parseInt(strs[0]);
        int n = Integer.parseInt(strs[1]);
        String[] wStr = strs[2].split(" ");
        String[] vStr = strs[3].split(" ");
        int[] weights = new int[n];
        int[] values = new int[n];
        for(int i=0;i<n;i++){
            weights[i] = Integer.parseInt(wStr[i]);
            values[i] = Integer.parseInt(vStr[i]);
        }
        int[][] dp = new int[n+1][c+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=c;j++){
                if(j>=weights[i-1]){
                    dp[i][j] = Math.max(dp[i-1][j-weights[i-1]]+values[i-1],dp[i-1][j]);
                }else
                    dp[i][j] = dp[i-1][j];
            }
        }
        System.out.println(dp[n][c]);
        
    }
}

# 动态规划
space, cls, sizes, values = input().split(",")
space = int(space)
cls = int(cls)
sizes = list(map(int, sizes.strip().split(" ")))
values = list(map(int, values.strip().split(" ")))
dp = [[0]*(space+1) for i in range(cls+1)]
for i in range(1, cls+1):
    size = sizes[i-1]
    value = values[i-1]
    for j in range(0, space+1):
        if j >= size:
            dp[i][j] = max(dp[i-1][j-size]+value, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][-1])

total,label,number,value = input().split(',')
number = list(map(int,number.split()))
value = list(map(int,value.split()))
#print(value)
dp = [0]*(int(total)+1)
for i in range(int(label)): # i是种类数
    for j in range(len(dp)-1,number[i]-1,-1): #j是number[i]到最大总量之间的数值
        dp[j] = max(dp[j],dp[j-number[i]]+value[i])
print(dp[-1])