题目
 
https://leetcode.com/problems/shopping-offers/
 
 
题解
 
类似题目有：leetcode 474. Ones and Zeroes | 474. 一和零（双约束背包问题）
 
本题实质上是一个多约束（n<6）的背包问题，求解目标是，在背包刚好装满的情况下，希望让总的 price 最小。物品可以使用无限次。
 
参考左神体系班学习班第19节：剪贴纸问题（实际上没参考它，只是想到有这么个题）
 
 
 
给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
 arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
 返回需要至少多少张贴纸可以完成这个任务。
 例子：str= “babac”，arr = {“ba”,“c”,“abcd”}
 ba + ba + c 3 abcd + abcd 2 abcd+ba 2
 所以本题返回2
 
 
由于一些物品是以组合的形式给出的，所以我们先将 list 嵌套 list 转化成数组，方便索引查找。
 然后，因为物品可以单独购买。为了统一方便，我们将可以单独购买的物品也转化成组合的形式，只不过让它们的系数都为 1。
 
如下图所示，前两行分别是单独购买 A 物品、单独购买 B 的价格，后两行是 AB 物品组合购买的价格。
 
 然后就是经典的 暴力递归 -> 傻缓存了。本题应该是无法转化成 dp 的，因为它的状态太多了，详见 dp map 中的 key，我的处理方式是将状态压缩成了字符串。后来看题解发现，hashmap 可以直接用 list 作为 key。
 
还有，我这个效率超级低，（应该是我为了避免回溯而copy的数组开销比较大），删掉 import 的头文件的话，会超时（这又是 leetcode 的蜜汁特性，带头文件的话运行速度快一些），带着头文件可以 AC。
 
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    int M; // 套餐总数
    int N; // 物品总数

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        N = price.size();
        M = special.size() + price.size();

        // 数组化 套餐列表
        int[][] sp = new int[M][N + 1];
        for (int i = 0; i < special.size(); i++) {
            List<Integer> list = special.get(i);
            for (int j = 0; j < N + 1; j++) {
                sp[i][j] = list.get(j);
            }
        }
        for (int i = special.size(), j = 0; i < M; i++, j++) {
            sp[i][j] = 1;
            sp[i][N] = price.get(j);
        }

        // 数组化 购物清单
        int[] need = new int[N];
        for (int i = 0; i < N; i++) {
            need[i] = needs.get(i);
        }
        
        Map<String, Integer> dp = new HashMap<>();
        return process(sp, need, 0, dp);
    }

    // 多约束背包问题
    // 物品列表在special中。当前可选择的物品在cur位置，还剩余needs要买的情况下，至少需要多少cost
    public int process(int[][] special, int[] needs, int cur, Map<String, Integer> dp) {
        // 查缓存
        StringBuilder key = new StringBuilder();
        for (int n : needs) { // 状态压缩成字符串
            key.append(n).append(":");
        }
        key.append(cur);
        if (dp.containsKey(key.toString())) return dp.get(key.toString());

        if (allZero(needs)) {
            dp.put(key.toString(), 0);
            return 0;
        }

        int minCost = Integer.MAX_VALUE;
        for (int p = cur; p < M; p++) { // 当前购买special[p]套餐
            for (int count = 0; canBuy(special, needs, count, p); count++) { // 购买count件p套餐
                int[] newNeeds = buy(special, needs, count, p);
                int newCost = process(special, newNeeds, p + 1, dp);
                if (newCost != Integer.MAX_VALUE) {
                    minCost = Math.min(minCost, count * special[p][N + 1 - 1] + newCost);
                }
            }
        }
        // 缓存
        dp.put(key.toString(), minCost);

        return minCost;
    }

    // 当前状态下，如果继续买count件p物品，是否买了不需要的
    public boolean canBuy(int[][] special, int[] needs, int count, int p) {
        for (int k = 0; k < N; k++) {
            if (needs[k] - count * special[p][k] < 0) return false;
        }
        return true;
    }

    public int[] buy(int[][] special, int[] needs, int count, int p) {
        int[] newNeeds = new int[N];
        for (int k = 0; k < N; k++) {
            newNeeds[k] = needs[k] - count * special[p][k];
        }
        return newNeeds;
    }

    public boolean allZero(int[] needs) {
        for (int n : needs) {
            if (n != 0) return false;
        }
        return true;
    }

}
 

 
悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
 
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
 
Total Submission(s): 12417 Accepted Submission(s): 5250
 
Problem Description
 
急！灾区的食物依然短缺！
 
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
 
请问：你用有限的资金最多能采购多少公斤粮食呢？
 
后记：
 
人生是一个充满了变数的生命过程，天灾、人祸、病痛是我们生命历程中不可预知的威胁。
 
月有阴晴圆缺，人有旦夕祸福，未来对于我们而言是一个未知数。那么，我们要做的就应该是珍惜现在，感恩生活——
 
感谢父母，他们给予我们生命，抚养我们成人；
 
感谢老师，他们授给我们知识，教我们做人
 
感谢朋友，他们让我们感受到世界的温暖；
 
感谢对手，他们令我们不断进取、努力。
 
同样，我们也要感谢痛苦与艰辛带给我们的财富～
 
Input
 
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
 
Output
 
对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。
 
Sample Input
 
1
 
8 2
 
2 100 4
 
4 100 2
 
Sample Output
 
400
 
#include#include
 
#define MAXN 110
 
#define MAXM 110
 
using namespacestd;struct GOODS{ intprice, weight, quantity; };
 
GOODS goods[MAXN];//行代表第i种，列代表还有j元钱
 
int n, m;//种类，钱
 
intdp[MAXN][MAXM];intmain()
 
{intt;
 
cin>>t;while (t--){
 
cin>> m >>n;for (int i = 1; i <= n; i++){
 
cin>> goods[i].price >> goods[i].weight >>goods[i].quantity;
 
}
 
memset(dp,0, sizeof(dp));for (int i = 1; i <= n; i++){for (int j = 0; j <= m; j++){for (int k = 0; k <= goods[i].quantity&&k*goods[i].price <= j; k++){
 
dp[i][j]= max(dp[i][j], dp[i-1][j - k*goods[i].price] + k*goods[i].weight);//好好想想为什么这里不是dp[i-1][j]
 
}
 
}
 
}
 
cout<< dp[n][m] <
 
}return 0;
 
}
 
因为是多背包，可能在第j种的时候已经选了s个，并且s

dp——多约束背包
 
一、题目描述
 
题目
 
N件物品和一个容量是 V的背包，背包能承受的最大重量是 M。每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。输出最大价值。
 
输入格式
 
第一行三个整数，N，V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。
 
输出格式
 
输出一个整数，表示最大价值。
 
输入样例
 
4 5 6
 1 2 3
 2 4 4
 3 4 5
 4 5 6
 
输出样例
 
8
 
数据范围
 
0<N≤100，0<V<1000, 0<M≤1000, vi,mi,wi都小于10000
 
二、解题思路
 
因为题目是最优子结构问题，所以可以采用动态规划来做。
 
【数学建模】
 
令dp[i][j][k]表示：前i个物品，当背包体积为j，背包能承受的重量为k，时的可以获得的最多的价值。
 
【状态方程】
 
因为这种背包每种物品只能拿一个，所以可以看成一种类似于01背包的背包问题。所以状态方程也可以参考01背包的来写：
 dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-V[i]][k-m[i]]+value[i]);
 
注意
 
如果j<V[i]或者k<m[j]那么状态转移方程就是：dp[i][j][k]=dp[i-1][j][k]
 
原因
 
这个状态转移方程得到的原因如下：
 
 
 
从第i个考虑，比较选还是不选。如果选择第i个物品，那么背包的体积就要≥这个物体的体积，且背包的重量≥物体的重量，最后再加上这个物体的价值，即：dp[i-1][j-V[i]][k-m[i]]+value[i]；如果此背包不满足：背包的体积≥这个物体的体积，且背包的重量≥物体的重量，则放弃这一个物品，即：dp[i-1][j][k]。
 
 
【边界（初始化）】
 
如果背包的重量或者背包的体积或者选择的物品数量为0，那么背包所能获得的最大价值就是0。所以背包的边界就是dp[i][j][0]=dp[i][0][k]=dp[0][j][k]=0。
 
三、时间复杂度及扩展
 
时间复杂度
 
因为需要使用三重for循环，则可以粗略计算时间复杂度就是O(nVm)
 
扩展
 
如果这个背包的约束不仅仅只有两个而有多个的话，那么时间复杂度也会增长，空间复杂度也会增加，并且没有优化策略 。
 
四、代码
 
#include<iostream>
#include<cstdio>
using namespace std;
int n,V,m,dp[110][1010][1010];
struct node{
	int V,m,val;
}A[110];
void init()
{
	scanf("%d%d%d",&n,&V,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&A[i].V,&A[i].m,&A[i].val);
} 
void solve()
{
	for(int i=0;i<=n;i++)//初始化 
	{
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=n;k++)
				if(i==0||j==0||k==0)
					dp[i][j][k]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<A[i].V;j++)//背包的体积不够 
			for(int k=1;k<=m;k++)
				dp[i][j][k]=dp[i-1][j][k];
		for(int j=A[i].V;j<=V;j++)
		{
			for(int k=1;k<A[i].m;k++)//背包所能承受的重量不够 
				dp[i][j][k]=dp[i-1][j][k];
			for(int k=A[i].m;k<=m;k++)
				dp[i][j][k]=max(dp[i-1][j-A[i].V][k-A[i].m]+A[i].val,dp[i-1][j][k]);
		} 
	}
	printf("%d",dp[n][V][m]);
}
int main()
{
	init();
	solve();
	return 0;
} 

问题描述：1、一个背包，往里装东西，物品重量w(weight)对应为[2,3,4,7] ，价值va(value)对应为[1,4,7,12] ，如果你的最大承重为20，每个物品可装次数不限，求你能装入背包的最大价值。
 2、如果物品可装次数times对应为[4,3,2,1]，求你能装入背包的最大价值。
 3、如果物品体积vo(volume)对应为[3,5,8,17]，最大容量为35，求你能装入背包的最大价值。
 
import pandas as pd

def Knapsack(w, vo, va, times, total_weight, total_volume):

    total_value = 0
    result = [{
                'weight': 0,
                'volume': 0,
                'value': 0,
                'total_value': total_value,  #递增
                'rest_weight': total_weight,  #递减
                'rest_volume':total_volume  #递减
            }]

    y = [0] * len(w)  #用以统计物品装入次数
    for i in range(1000):  #设置尝试装入次数
        k = 0
        for j in range(len(w)):
            if w[k] > total_weight or vo[k] > total_volume or y[k] == times[k]:  #去掉重量超过剩余承重或体积大于剩余容量或装入次数达到上限的物品
                print("重量%d体积%d：共装入%d次" %(w[k], vo[k], y[k]))
                del w[k], vo[k], va[k], times[k], y[k]
            else:
                k += 1

        if len(w) > 0:
            u = [[], []]
            for j in range(len(w)):
                u[0].append(min(times[j] - y[j], (total_weight // w[j]), (total_volume // vo[j])))
                u[1].append(u[0][j] * va[j])  #第一次取整计算物品的最高可装入价值（第一层）

                s = [[], []]
                for k in range(len(w)):
                    if k == j:
                        s[0].append(0)
                    else:
                        s[0].append(min(times[k] - y[k], (total_weight - (w[j] * u[0][j]))// w[k], (total_volume - (vo[j] * u[0][j])) // vo[k]))
                    s[1].append(s[0][k] * va[k])  #对取整后的剩余重量、体积、次数再次取整计算物品的最高可装入价值（第二层）

                    t = [[], []]
                    for l in range(len(w)):
                        if l == j or l == k:
                            t[0].append(0)
                        else:
                            t[0].append(min(times[l] - y[l], (total_weight - (w[j] * u[0][j]) - (w[k] * s[0][k])) // w[l],(total_volume - (vo[j] * u[0][j]) - (vo[k] * s[0][k])) // vo[l]))
                        t[1].append(t[0][l] * va[l])  # 对取整后的剩余重量、体积、次数再次取整计算物品的最高可装入价值（第三层），层数越多，计算越准确，暂时只计算三层
                    s[1][k] += max(t[1])  #将第三次取整计算物品的最高可装入价值的最大值加到第二次的结果中
                u[1][j] += max(s[1])  #将第二次取整计算物品的最高可装入价值的最大值加到第一次的结果中

            if max(u[1]) > 0:   #选择评估价值最高的物品优先装入
                y[u[1].index(max(u[1]))] += 1  #记录物品装入次数
                weight, volume, value = w[u[1].index(max(u[1]))], vo[u[1].index(max(u[1]))], va[u[1].index(max(u[1]))]
                total_weight = total_weight - weight  #计算剩余承重
                total_volume = total_volume - volume  #计算剩余容量
                total_value += value  #计算已装入物品总价值
                result.append({
                    'weight': weight,
                    'volume': volume,
                    'value': value,
                    'total_value': total_value,
                    'rest_weight': total_weight,
                    'rest_volume':total_volume
                })
            else:  #一旦无满足约束的物品可装入，则停止装入
                break

    return pd.DataFrame(result,columns = ['weight', 'volume', 'value', 'total_value', 'rest_weight', 'rest_volume'])

datafile = r'C:\Users\administrator1\Desktop\Knapsack problem.xls'  #输入数据路径
data = pd.read_excel(datafile)  #读取数据
data['unitw_value'] = data['value'] / data['weight']
data = data.sort_values(by = 'unitw_value', ascending = False)

weight = data['weight'].tolist()
volume = data['volume'].tolist()
value = data['value'].tolist()
times = data['times'].tolist()
total_weight = 20
total_volume = 35

if __name__ == "__main__":
    start_time = time.time()
    print("共有%d种物品" %(len(weight)))
    print(Knapsack(weight, volume, value, times, total_weight, total_volume))
    end_time = time.time()
    print(end_time - start_time)